| """ |
| ======================== |
| Cycle finding algorithms |
| ======================== |
| """ |
| # Copyright (C) 2010-2012 by |
| # Aric Hagberg <hagberg@lanl.gov> |
| # Dan Schult <dschult@colgate.edu> |
| # Pieter Swart <swart@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| import networkx as nx |
| from networkx.utils import * |
| from collections import defaultdict |
| |
| __all__ = ['cycle_basis','simple_cycles','recursive_simple_cycles'] |
| __author__ = "\n".join(['Jon Olav Vik <jonovik@gmail.com>', |
| 'Dan Schult <dschult@colgate.edu>', |
| 'Aric Hagberg <hagberg@lanl.gov>']) |
| |
| @not_implemented_for('directed') |
| @not_implemented_for('multigraph') |
| def cycle_basis(G,root=None): |
| """ Returns a list of cycles which form a basis for cycles of G. |
| |
| A basis for cycles of a network is a minimal collection of |
| cycles such that any cycle in the network can be written |
| as a sum of cycles in the basis. Here summation of cycles |
| is defined as "exclusive or" of the edges. Cycle bases are |
| useful, e.g. when deriving equations for electric circuits |
| using Kirchhoff's Laws. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| root : node, optional |
| Specify starting node for basis. |
| |
| Returns |
| ------- |
| A list of cycle lists. Each cycle list is a list of nodes |
| which forms a cycle (loop) in G. |
| |
| Examples |
| -------- |
| >>> G=nx.Graph() |
| >>> G.add_cycle([0,1,2,3]) |
| >>> G.add_cycle([0,3,4,5]) |
| >>> print(nx.cycle_basis(G,0)) |
| [[3, 4, 5, 0], [1, 2, 3, 0]] |
| |
| Notes |
| ----- |
| This is adapted from algorithm CACM 491 [1]_. |
| |
| References |
| ---------- |
| .. [1] Paton, K. An algorithm for finding a fundamental set of |
| cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518. |
| |
| See Also |
| -------- |
| simple_cycles |
| """ |
| gnodes=set(G.nodes()) |
| cycles=[] |
| while gnodes: # loop over connected components |
| if root is None: |
| root=gnodes.pop() |
| stack=[root] |
| pred={root:root} |
| used={root:set()} |
| while stack: # walk the spanning tree finding cycles |
| z=stack.pop() # use last-in so cycles easier to find |
| zused=used[z] |
| for nbr in G[z]: |
| if nbr not in used: # new node |
| pred[nbr]=z |
| stack.append(nbr) |
| used[nbr]=set([z]) |
| elif nbr == z: # self loops |
| cycles.append([z]) |
| elif nbr not in zused:# found a cycle |
| pn=used[nbr] |
| cycle=[nbr,z] |
| p=pred[z] |
| while p not in pn: |
| cycle.append(p) |
| p=pred[p] |
| cycle.append(p) |
| cycles.append(cycle) |
| used[nbr].add(z) |
| gnodes-=set(pred) |
| root=None |
| return cycles |
| |
| |
| @not_implemented_for('undirected') |
| def simple_cycles(G): |
| """Find simple cycles (elementary circuits) of a directed graph. |
| |
| An simple cycle, or elementary circuit, is a closed path where no |
| node appears twice, except that the first and last node are the same. |
| Two elementary circuits are distinct if they are not cyclic permutations |
| of each other. |
| |
| This is a nonrecursive, iterator/generator version of Johnson's |
| algorithm [1]_. There may be better algorithms for some cases [2]_ [3]_. |
| |
| Parameters |
| ---------- |
| G : NetworkX DiGraph |
| A directed graph |
| |
| Returns |
| ------- |
| cycle_generator: generator |
| A generator that produces elementary cycles of the graph. Each cycle is |
| a list of nodes with the first and last nodes being the same. |
| |
| Examples |
| -------- |
| >>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]) |
| >>> list(nx.simple_cycles(G)) |
| [[2], [2, 1], [2, 0], [2, 0, 1], [0]] |
| |
| Notes |
| ----- |
| The implementation follows pp. 79-80 in [1]_. |
| |
| The time complexity is O((n+e)(c+1)) for n nodes, e edges and c |
| elementary circuits. |
| |
| To filter the cycles so that they don't include certain nodes or edges, |
| copy your graph and eliminate those nodes or edges before calling. |
| >>> copyG = G.copy() |
| >>> copyG.remove_nodes_from([1]) |
| >>> copyG.remove_edges_from([(0,1)]) |
| >>> list(nx.simple_cycles(copyG)) |
| [[2], [2, 0], [0]] |
| |
| References |
| ---------- |
| .. [1] Finding all the elementary circuits of a directed graph. |
| D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. |
| http://dx.doi.org/10.1137/0204007 |
| |
| .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy. |
| G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982. |
| |
| .. [3] A search strategy for the elementary cycles of a directed graph. |
| J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS, |
| v. 16, no. 2, 192-204, 1976. |
| |
| See Also |
| -------- |
| cycle_basis |
| """ |
| 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() |
| |
| # Johnson's algorithm requires some ordering of the nodes. |
| # We assign the arbitrary ordering given by the strongly connected comps |
| # There is no need to track the ordering as each node removed as processed. |
| subG=G.copy() # save the actual graph so we can mutate it here |
| sccs = nx.strongly_connected_components(subG) |
| while sccs: |
| scc=sccs.pop() |
| # order of scc determines ordering of nodes |
| startnode = scc.pop() |
| # Processing node runs "circuit" routine from recursive version |
| path=[startnode] |
| blocked = set() # vertex: blocked from search? |
| closed = set() # nodes involved in a cycle |
| blocked.add(startnode) |
| B=defaultdict(set) # graph portions that yield no elementary circuit |
| stack=[ (startnode,list(subG[startnode])) ] # subG gives component nbrs |
| while stack: |
| thisnode,nbrs = stack[-1] |
| if nbrs: |
| nextnode = nbrs.pop() |
| # print thisnode,nbrs,":",nextnode,blocked,B,path,stack,startnode |
| # f=raw_input("pause") |
| if nextnode == startnode: |
| yield path[:] |
| closed.update(path) |
| # print "Found a cycle",path,closed |
| elif nextnode not in blocked: |
| path.append(nextnode) |
| stack.append( (nextnode,list(subG[nextnode])) ) |
| blocked.add(nextnode) |
| continue |
| # done with nextnode... look for more neighbors |
| if not nbrs: # no more 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() |
| # assert path[-1]==thisnode |
| path.pop() |
| # done processing this node |
| subG.remove_node(startnode) |
| H=subG.subgraph(scc) # make smaller to avoid work in SCC routine |
| sccs.extend(nx.strongly_connected_components(H)) |
| |
| |
| @not_implemented_for('undirected') |
| def recursive_simple_cycles(G): |
| """Find simple cycles (elementary circuits) of a directed graph. |
| |
| A simple cycle, or elementary circuit, is a closed path where no |
| node appears twice, except that the first and last node are the same. |
| Two elementary circuits are distinct if they are not cyclic permutations |
| of each other. |
| |
| This version uses a recursive algorithm to build a list of cycles. |
| You should probably use the iterator version caled simple_cycles(). |
| Warning: This recursive version uses lots of RAM! |
| |
| Parameters |
| ---------- |
| G : NetworkX DiGraph |
| A directed graph |
| |
| Returns |
| ------- |
| A list of circuits, where each circuit is a list of nodes, with the first |
| and last node being the same. |
| |
| Example: |
| >>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]) |
| >>> nx.recursive_simple_cycles(G) |
| [[0], [0, 1, 2], [0, 2], [1, 2], [2]] |
| |
| See Also |
| -------- |
| cycle_basis (for undirected graphs) |
| |
| Notes |
| ----- |
| The implementation follows pp. 79-80 in [1]_. |
| |
| The time complexity is O((n+e)(c+1)) for n nodes, e edges and c |
| elementary circuits. |
| |
| References |
| ---------- |
| .. [1] Finding all the elementary circuits of a directed graph. |
| D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. |
| http://dx.doi.org/10.1137/0204007 |
| |
| See Also |
| -------- |
| simple_cycles, cycle_basis |
| """ |
| # Jon Olav Vik, 2010-08-09 |
| def _unblock(thisnode): |
| """Recursively unblock and remove nodes from B[thisnode].""" |
| if blocked[thisnode]: |
| blocked[thisnode] = False |
| while B[thisnode]: |
| _unblock(B[thisnode].pop()) |
| |
| def circuit(thisnode, startnode, component): |
| closed = False # set to True if elementary path is closed |
| path.append(thisnode) |
| blocked[thisnode] = True |
| for nextnode in component[thisnode]: # direct successors of thisnode |
| if nextnode == startnode: |
| result.append(path[:]) |
| closed = True |
| elif not blocked[nextnode]: |
| if circuit(nextnode, startnode, component): |
| closed = True |
| if closed: |
| _unblock(thisnode) |
| else: |
| for nextnode in component[thisnode]: |
| if thisnode not in B[nextnode]: # TODO: use set for speedup? |
| B[nextnode].append(thisnode) |
| path.pop() # remove thisnode from path |
| return closed |
| |
| path = [] # stack of nodes in current path |
| blocked = defaultdict(bool) # vertex: blocked from search? |
| B = defaultdict(list) # graph portions that yield no elementary circuit |
| result = [] # list to accumulate the circuits found |
| # Johnson's algorithm requires some ordering of the nodes. |
| # They might not be sortable so we assign an arbitrary ordering. |
| ordering=dict(zip(G,range(len(G)))) |
| for s in ordering: |
| # Build the subgraph induced by s and following nodes in the ordering |
| subgraph = G.subgraph(node for node in G |
| if ordering[node] >= ordering[s]) |
| # Find the strongly connected component in the subgraph |
| # that contains the least node according to the ordering |
| strongcomp = nx.strongly_connected_components(subgraph) |
| mincomp=min(strongcomp, |
| key=lambda nodes: min(ordering[n] for n in nodes)) |
| component = G.subgraph(mincomp) |
| if component: |
| # smallest node in the component according to the ordering |
| startnode = min(component,key=ordering.__getitem__) |
| for node in component: |
| blocked[node] = False |
| B[node][:] = [] |
| dummy=circuit(startnode, startnode, component) |
| return result |
