3 ms·
I've used recently the networkx algorithm to find Hamiltonian cycles in a graph, in order to generate a Secret Santa with constraints (couples don't send gifts
by rpigab 3y ago
I've used recently the networkx algorithm to find Hamiltonian cycles in a graph, in order to generate a Secret Santa with constraints (couples don't send gifts to each other, and people don't give to the same person as last year), it works great even though the problem is NP-complete, since my number of participants is very low.
I've tried the same in Rust with petgraph which resembles networkx, but it doesn't have the algorithm for Hamiltonian built in and I couldn't wrap my head around the DFS/BFS visitor pattern, but I'll continue this some day.
- samsquire 3y agoIs this similar to graph colouring?
- rpigab 3y agoThey are distinct problems, because if you have a graph with a Hamiltonian cycle inside, you can add as many edges as you want, the cycle will always be there, but some N-colouring solutions might break. They are both NP-complete though.