Skip to content

Instantly share code, notes, and snippets.

@joe-jordan
Created September 13, 2013 08:23
Show Gist options
  • Save joe-jordan/6548029 to your computer and use it in GitHub Desktop.
Save joe-jordan/6548029 to your computer and use it in GitHub Desktop.
Function to find all the cycles in a networkx graph. Health warning: this thing is an NP-complete depth-first search, work hard to make the graphs you put into it small.
def find_all_cycles(G, source=None, cycle_length_limit=None):
"""forked from networkx dfs_edges function. Assumes nodes are integers, or at least
types which work with min() and > ."""
if source is None:
# produce edges for all components
nodes=[i[0] for i in nx.connected_components(G)]
else:
# produce edges for components with source
nodes=[source]
# extra variables for cycle detection:
cycle_stack = []
output_cycles = set()
def get_hashable_cycle(cycle):
"""cycle as a tuple in a deterministic order."""
m = min(cycle)
mi = cycle.index(m)
mi_plus_1 = mi + 1 if mi < len(cycle) - 1 else 0
if cycle[mi-1] > cycle[mi_plus_1]:
result = cycle[mi:] + cycle[:mi]
else:
result = list(reversed(cycle[:mi_plus_1])) + list(reversed(cycle[mi_plus_1:]))
return tuple(result)
for start in nodes:
if start in cycle_stack:
continue
cycle_stack.append(start)
stack = [(start,iter(G[start]))]
while stack:
parent,children = stack[-1]
try:
child = next(children)
if child not in cycle_stack:
cycle_stack.append(child)
stack.append((child,iter(G[child])))
else:
i = cycle_stack.index(child)
if i < len(cycle_stack) - 2:
output_cycles.add(get_hashable_cycle(cycle_stack[i:]))
except StopIteration:
stack.pop()
cycle_stack.pop()
return [list(i) for i in output_cycles]
@mikemhenry
Copy link

Hey Joe,

How is this code licensed?

Thanks!
Mike

@pali08
Copy link

pali08 commented Dec 31, 2020

Thank you very much, this helped a lot, as networkx find_cycle did not find all cycles in some cases.

In line 6 "i[0]" must be changed to "list(i)[0]", otherwise you get "TypeError: 'set' object is not subscriptable"

@ZijianWang-ZW
Copy link

Really helpful. Thank you very much for your share!

@hannahbaumann
Copy link

Hey @joe-jordan ,
this function is very helpful and I would like to use it in some code. How is it licensed?
Best,
Hannah

@vicitori
Copy link

Hey @joe-jordan ,
Really cool solution. How is it licensed?

Thanks for your share!
Victoria

@joe-jordan
Copy link
Author

Hello all.

I don't maintain this code, and it was written for python 2. It also sounds like the networkx interface has changed (see pali08's comment above).

The licensing here is BSD, specifically:

Copyright (c) 2013 Joe F Jordan. All rights reserved.

Redistribution and use in source and binary forms are permitted provided that the above copyright notice and this paragraph are duplicated in all such forms and that any documentation, advertising materials, and other materials related to such distribution and use acknowledge that the software was developed by Joe F Jordan. The name of Joe F Jordan may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED `'AS IS″ AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

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