from collections import defaultdict


def bits(n):
    "Generator. All bits, from least to most significant."
    while n > 0:
        yield n & 1
        n >>= 1


def n_bits(n):
    "Number of nodes in the set."
    return sum(bits(n))


def node_sets(n):
    "All node sets that include node 0, sorted by set size."
    bit_sets = set(n for n in range(2, 2**n) if (n & 1) == 1)
    return sorted(bit_sets, key=n_bits)


def active_bits(n):
    "Generator. All nodes in the set."
    return (i for i,bit in enumerate(bits(n)) if bit == 1)


def hamiltonian_cycle(graph, N):
    """
    Predicate. True if the graph consitutes a Hamiltonian cycle -- that is, if
    you can start at a node, visit all nodes in the graph, and end at the start
    node, such that all nodes are visited once (the start node will be visited
    twice).

    All N nodes must be represented by the integers [0, N).

    Since any node can be the start node, we use 0 as the start node.

    This algorithm uses dynamic programming, starting with the node set containing
    just the start node and then building out from there to larger node sets that
    are connected to the start node and that form a Hamiltonian path.
    """
    if N <= 1:
        return True

    paths = defaultdict(bool)
    paths[1 << 0] = True

    for s in node_sets(N):
        for n in (n for n in active_bits(s) if n != 0):
            s2 = s ^ (1 << n)
            # Dynamic programming step: remove all nodes, one at a time, except
            # for the start node, from the proposed set. If the smaller set
            # forms a Hamiltonian path and has an edge to the removed node, then
            # the proposed set also forms a Hamiltonian path.
            if paths[s2]:
                for n2 in active_bits(s2):
                    if n in graph[n2]:
                        paths[s] = True
                        if s == (2**N - 1) and 0 in graph[n]:
                            # All nodes in the graph have formed a Hamiltonian
                            # path, and the last node added to the path has an
                            # edge to the start node, thus forming a Hamiltonian
                            # cycle, using all the graph's nodes.
                            return True

    return False


def tests():
    graph = {
        0: {1, 2},
        1: {0, 3},
        2: {3},
        3: {4},
        4: {1, 2, 3}
    }

    assert hamiltonian_cycle(graph, 5)

    graph = {
        0: {1},
        1: {0, 2},
        2: {1}
    }

    assert not hamiltonian_cycle(graph, 3)

    print('tests done!')


if __name__ == '__main__':
    tests()

@@ -1239,24 +1239,36 @@
 n True%0A%0A    
+hamiltonian_
 paths = defa
@@ -1279,18 +1279,30 @@
 ict(
-bool
+dict
 )%0A    
+hamiltonian_
 path
@@ -1310,23 +1310,26 @@
 %5B1 %3C%3C 0%5D
- = True
+%5B0%5D = (0,)
 %0A%0A    fo
@@ -1750,87 +1750,102 @@
     
-if paths%5Bs2%5D:%0A                for n2 in active_bits(s2):%0A                    if
+for end_point,path in hamiltonian_paths%5Bs2%5D.items():%0A                if end_point in graph and
  n i
@@ -1856,10 +1856,17 @@
 aph%5B
-n2
+end_point
 %5D:%0A 
@@ -1888,121 +1888,93 @@
     
-    paths%5Bs%5D = True%0A                        if s == (2**N - 1) and 0 in graph%5Bn%5D:%0A                            # A
+hamiltonian_paths%5Bs%5D%5Bn%5D = path + (n,)%0A%0A    # 2**N - 1 is the node set that contains a
 ll n
@@ -1970,34 +1970,34 @@
 tains all nodes 
-in
+of
  the graph have 
@@ -1994,180 +1994,112 @@
 raph
- have formed a Hamiltonian%0A                            # path, and the last node added to the path has an%0A                            # edge to the start node, thus
+.%0A    # Each Hamiltonian path in hamiltonian_paths%5B2**N - 1%5D whose endpoint%0A    # has an edge to 0
  form
-ing
+s
  a H
@@ -2112,132 +2112,169 @@
 nian
-%0A                            # cycle, using all the graph's nodes.%0A                            return True%0A%0A    return False
+ cycle.%0A    cycles = (path + (0,)%0A              for path in hamiltonian_paths%5B2**N - 1%5D.values()%0A              if 0 in graph%5Bpath%5B-1%5D%5D)%0A%0A    return tuple(cycles)
 %0A%0A%0Ad
@@ -2401,22 +2401,24 @@
  %7D%0A%0A    
-assert
+cycles =
  hamilto
@@ -2437,16 +2437,74 @@
 raph, 5)
+%0A    assert cycles%0A    assert (0, 2, 3, 4, 1, 0) in cycles
 %0A%0A    gr
@@ -2612,16 +2612,132 @@
 ph, 3)%0A%0A
+    graph = %7B%0A        0: %7B1%7D,%0A        1: %7B2, 3%7D,%0A        2: %7B0%7D,%0A    %7D%0A%0A    assert not hamiltonian_cycle(graph, 4)%0A%0A
     prin
@@ -2749,12 +2749,12 @@
 sts 
-done
+pass
 !')%0A

Update hamiltonian_cycle.py