Skip to content

Instantly share code, notes, and snippets.

View ZijianWang-ZW's full-sized avatar

Zijian Wang ZijianWang-ZW

View GitHub Profile
@joe-jordan
joe-jordan / cycles.py
Created September 13, 2013 08:23
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: