Given n nodes enumerate all possible rings

[Siddharth Jain]

Hello,

I am given n nodes e.g., n = 3. I am interested in enumerating all possible rings that can be created from the n nodes. A ring should include all n nodes in it. E.g., if n = 3 there is only 1 possible ring. 

For n = 4, I think there are 3 possible rings.

• Can the networkx library do this for me? How?
• also curious, what is the formula for the total # of rings as function of n?

Thanks,

Sid

[Dan Schult]

Take a look at the wikipedia article for Hamiltonian Cycle (and the related Hamiltonian path).

This is one of the long standing problems of classical Graph Theory. You should probably

get familiar with the problem and approaches people have come up with and try to map

them onto what you actually want to do.

Another useful search phrase for a similar problem is "the Traveling Salesman Problem"

which searches for the smallest weighted hamiltonian cycle.

A related question is whether a cycle exists that can visit every **edge** in the graph.

That is called an eulerian cycle.  

For networkx, we have more for eulerian cycles than for hamiltonian cycles.

We have functions to find cycles. Perhaps the `find_cycle` function is the place to start.

None of these restrict to finding hamiltonian cycles, so you will likely have to develop something.

The 2.6 version about to come out (and available on github) has a set of functions for 

approximating solutions to the traveling_salesman_problem.