Last active
September 3, 2017 14:27
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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))) |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Not working