MikeRand MikeRand -4 years ago 36
Python Question

How to enumerate possible reconstructions of a Hamiltonian cycle without DFS/BFS?

I have a directed Hamiltonian cycle:

[..., a, b, ... , c, d, ..., e, f, ...]


Where
b = next(a)
,
d = next(c)
, and
f = next(e)
.

Say I delete edges (a, b), (c, d), and (e, f).

Question: How do I generate all possible recombinations of the graph such that it remains a Hamiltonian cycle (keeping in mind that I may have to reverse the ordering in one of the pieces to fix direction)?

What I know

I know that the number of new Hamiltonian cycles reachable by removing n-edges is
double-factorial(n-1)
. I also know that if I'm removing two consecutive edges, I'll get duplicate solutions (which I'm fine with ... they should be minimal relative to unique cycles and it keeps the resulting code clean).

What I've tried (in rough Pseudocode)

One way to think about this is that any of the yielded Hamiltonian cycles must preserve the property that you have to travel along the pieces of the disconnected graph before jumping to a new piece.

So, for example, thinking about the cycle above (where
n = 3
), there are the following 3 pieces:

[b, ..., c]
[d, ..., e]
[f, ..., a]


So let's say my new solution starts as follows:

[..., a, d, ...]


I know that e is the vertex that must come next from my list of terminal vertices.

So, using that idea, the Python would be something like this:

from itertools import permutations

def hamiltonian_cycles(l, s=None, r=None):
if s is None:
s = [l[0]]
if r is None:
r = l[1:]
if not r:
yield s
else:
for permutation in permutations(r):
s1 = s[:] + [permutation[0]]
for cycle in hamiltonian_cycles(l, s1, permutation[1:]):
yield cycle
s2 = s[:] + [(permutation[0][1], permutation[0][0])]
for cycle in hamiltonian_cycles(l, s2, permutation[1:]):
yield cycle

>>> l = [('f', 'a'), ('b', 'c'), ('d', 'e')]
>>> for cycle in hamiltonian_cycles(l):
... print(cycle)
[('f', 'a'), ('b', 'c'), ('d', 'e')]
[('f', 'a'), ('b', 'c'), ('e', 'd')]
[('f', 'a'), ('c', 'b'), ('d', 'e')]
[('f', 'a'), ('c', 'b'), ('e', 'd')]
[('f', 'a'), ('d', 'e'), ('b', 'c')]
[('f', 'a'), ('d', 'e'), ('c', 'b')]
[('f', 'a'), ('e', 'd'), ('b', 'c')]
[('f', 'a'), ('e', 'd'), ('c', 'b')]


This seems ugly and stops working past
n=3
, though, hence the question.

Why I don't want to use BFS/DFS

I need a generator that is linear in the number of edges deleted, not in the number of total edges + vertices.

Answer Source

Thanks to this helpful answer here, here's the code that does it.

from itertools import chain, permutations, product

def new_edge_sets(deleted_edges):

    def edges_to_pieces(l):
        new_list = []
        n = len(l)
        for i in xrange(-1,n-1):
            new_list.append((l[i%n][1], l[(i+1)%n][0]))
        return new_list

    def permute(it):
        return product(*(permutations(i) for i in it))

    def permute2(it):
        return chain.from_iterable(permute(p) for p in permutations(it))

    def pieces_to_edges(p):
        new_list = []
        n = len(p)
        for i in xrange(n):
            new_list.append((p[i%n][1], p[(i+1)%n][0]))
        return new_list

    def permute3(s):
        return (pieces_to_edges(s[:1] + list(p)) for p in permute2(s[1:]))

    return permute3(edges_to_pieces(deleted_edges))

Example:

>>> deleted_edges = [('a', 'b'), ('c', 'd'), ('e', 'f'), ('g', 'h')]
>>> l = list(new_edge_sets(deleted_edges))
>>> len(l)
48
>>> for new_edges in l:
...     print(new_edges)
[('a', 'b'), ('c', 'd'), ('e', 'f'), ('g', 'h')]
[('a', 'b'), ('c', 'd'), ('e', 'g'), ('f', 'h')]
[('a', 'b'), ('c', 'e'), ('d', 'f'), ('g', 'h')]
[('a', 'b'), ('c', 'e'), ('d', 'g'), ('f', 'h')]
[('a', 'c'), ('b', 'd'), ('e', 'f'), ('g', 'h')]
[('a', 'c'), ('b', 'd'), ('e', 'g'), ('f', 'h')]
[('a', 'c'), ('b', 'e'), ('d', 'f'), ('g', 'h')]
[('a', 'c'), ('b', 'e'), ('d', 'g'), ('f', 'h')]
[('a', 'b'), ('c', 'f'), ('g', 'd'), ('e', 'h')]
[('a', 'b'), ('c', 'f'), ('g', 'e'), ('d', 'h')]
[('a', 'b'), ('c', 'g'), ('f', 'd'), ('e', 'h')]
[('a', 'b'), ('c', 'g'), ('f', 'e'), ('d', 'h')]
[('a', 'c'), ('b', 'f'), ('g', 'd'), ('e', 'h')]
[('a', 'c'), ('b', 'f'), ('g', 'e'), ('d', 'h')]
[('a', 'c'), ('b', 'g'), ('f', 'd'), ('e', 'h')]
[('a', 'c'), ('b', 'g'), ('f', 'e'), ('d', 'h')]
[('a', 'd'), ('e', 'b'), ('c', 'f'), ('g', 'h')]
[('a', 'd'), ('e', 'b'), ('c', 'g'), ('f', 'h')]
[('a', 'd'), ('e', 'c'), ('b', 'f'), ('g', 'h')]
[('a', 'd'), ('e', 'c'), ('b', 'g'), ('f', 'h')]
[('a', 'e'), ('d', 'b'), ('c', 'f'), ('g', 'h')]
[('a', 'e'), ('d', 'b'), ('c', 'g'), ('f', 'h')]
[('a', 'e'), ('d', 'c'), ('b', 'f'), ('g', 'h')]
[('a', 'e'), ('d', 'c'), ('b', 'g'), ('f', 'h')]
[('a', 'd'), ('e', 'f'), ('g', 'b'), ('c', 'h')]
[('a', 'd'), ('e', 'f'), ('g', 'c'), ('b', 'h')]
[('a', 'd'), ('e', 'g'), ('f', 'b'), ('c', 'h')]
[('a', 'd'), ('e', 'g'), ('f', 'c'), ('b', 'h')]
[('a', 'e'), ('d', 'f'), ('g', 'b'), ('c', 'h')]
[('a', 'e'), ('d', 'f'), ('g', 'c'), ('b', 'h')]
[('a', 'e'), ('d', 'g'), ('f', 'b'), ('c', 'h')]
[('a', 'e'), ('d', 'g'), ('f', 'c'), ('b', 'h')]
[('a', 'f'), ('g', 'b'), ('c', 'd'), ('e', 'h')]
[('a', 'f'), ('g', 'b'), ('c', 'e'), ('d', 'h')]
[('a', 'f'), ('g', 'c'), ('b', 'd'), ('e', 'h')]
[('a', 'f'), ('g', 'c'), ('b', 'e'), ('d', 'h')]
[('a', 'g'), ('f', 'b'), ('c', 'd'), ('e', 'h')]
[('a', 'g'), ('f', 'b'), ('c', 'e'), ('d', 'h')]
[('a', 'g'), ('f', 'c'), ('b', 'd'), ('e', 'h')]
[('a', 'g'), ('f', 'c'), ('b', 'e'), ('d', 'h')]
[('a', 'f'), ('g', 'd'), ('e', 'b'), ('c', 'h')]
[('a', 'f'), ('g', 'd'), ('e', 'c'), ('b', 'h')]
[('a', 'f'), ('g', 'e'), ('d', 'b'), ('c', 'h')]
[('a', 'f'), ('g', 'e'), ('d', 'c'), ('b', 'h')]
[('a', 'g'), ('f', 'd'), ('e', 'b'), ('c', 'h')]
[('a', 'g'), ('f', 'd'), ('e', 'c'), ('b', 'h')]
[('a', 'g'), ('f', 'e'), ('d', 'b'), ('c', 'h')]
[('a', 'g'), ('f', 'e'), ('d', 'c'), ('b', 'h')]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download