Skip to content

Instantly share code, notes, and snippets.

@qpwo
Last active September 3, 2017 14:27
Show Gist options
  • Select an option

  • Save qpwo/272df112928391b2c83a3b67732a5c25 to your computer and use it in GitHub Desktop.

Select an option

Save qpwo/272df112928391b2c83a3b67732a5c25 to your computer and use it in GitHub Desktop.
common python form of networkx's implementation of Johnson's cycle finding algorithm
from collections import defaultdict
def simple_cycles(G):
def _unblock(thisnode,blocked,B):
stack = set([thisnode])
while stack:
node = stack.pop()
if node in blocked:
blocked.remove(node)
stack.update(B[node])
B[node].clear()
startnode = G.keys()[0]
path=[startnode]
blocked = set()
closed = set()
blocked.add(startnode)
B=defaultdict(set)
stack=[ (startnode,list(G[startnode])) ]
while stack:
thisnode, nbrs = stack[-1]
if nbrs:
nextnode = nbrs.pop()
if nextnode == startnode:
yield path[:]
closed.update(path)
elif nextnode not in blocked:
path.append(nextnode)
stack.append( (nextnode,list(G[nextnode])) )
closed.discard(nextnode)
blocked.add(nextnode)
continue
if not nbrs:
if thisnode in closed:
_unblock(thisnode,blocked,B)
else:
for nbr in G[thisnode]:
if thisnode not in B[nbr]:
B[nbr].add(thisnode)
stack.pop()
path.pop()
graph = {0: [7, 3, 5], 1: [2], 2: [7, 1], 3: [0, 5], 4: [6, 8], 5: [0, 3, 7], 6: [4, 8], 7: [0, 2, 5, 8], 8: [4, 6, 7]}
print(tuple(simple_cycles(graph)))
@qpwo

qpwo commented Sep 3, 2017

Copy link
Copy Markdown
Author

Not working

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment