| # -*- coding: utf-8 -*- |
| """ |
| Strongly connected components. |
| """ |
| # Copyright (C) 2004-2011 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 |
| __authors__ = "\n".join(['Eben Kenah', |
| 'Aric Hagberg (hagberg@lanl.gov)' |
| 'Christopher Ellison', |
| 'Ben Edwards (bedwards@cs.unm.edu)']) |
| |
| __all__ = ['number_strongly_connected_components', |
| 'strongly_connected_components', |
| 'strongly_connected_component_subgraphs', |
| 'is_strongly_connected', |
| 'strongly_connected_components_recursive', |
| 'kosaraju_strongly_connected_components', |
| 'condensation'] |
| |
| def strongly_connected_components(G): |
| """Return nodes in strongly connected components of graph. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| An directed graph. |
| |
| Returns |
| ------- |
| comp : list of lists |
| A list of nodes for each component of G. |
| The list is ordered from largest connected component to smallest. |
| |
| Raises |
| ------ |
| NetworkXError: If G is undirected. |
| |
| See Also |
| -------- |
| connected_components, weakly_connected_components |
| |
| Notes |
| ----- |
| Uses Tarjan's algorithm with Nuutila's modifications. |
| Nonrecursive version of algorithm. |
| |
| References |
| ---------- |
| .. [1] Depth-first search and linear graph algorithms, R. Tarjan |
| SIAM Journal of Computing 1(2):146-160, (1972). |
| |
| .. [2] On finding the strongly connected components in a directed graph. |
| E. Nuutila and E. Soisalon-Soinen |
| Information Processing Letters 49(1): 9-14, (1994).. |
| """ |
| if not G.is_directed(): |
| raise nx.NetworkXError("""Not allowed for undirected graph G. |
| Use connected_components() """) |
| preorder={} |
| lowlink={} |
| scc_found={} |
| scc_queue = [] |
| scc_list=[] |
| i=0 # Preorder counter |
| for source in G: |
| if source not in scc_found: |
| queue=[source] |
| while queue: |
| v=queue[-1] |
| if v not in preorder: |
| i=i+1 |
| preorder[v]=i |
| done=1 |
| v_nbrs=G[v] |
| for w in v_nbrs: |
| if w not in preorder: |
| queue.append(w) |
| done=0 |
| break |
| if done==1: |
| lowlink[v]=preorder[v] |
| for w in v_nbrs: |
| if w not in scc_found: |
| if preorder[w]>preorder[v]: |
| lowlink[v]=min([lowlink[v],lowlink[w]]) |
| else: |
| lowlink[v]=min([lowlink[v],preorder[w]]) |
| queue.pop() |
| if lowlink[v]==preorder[v]: |
| scc_found[v]=True |
| scc=[v] |
| while scc_queue and preorder[scc_queue[-1]]>preorder[v]: |
| k=scc_queue.pop() |
| scc_found[k]=True |
| scc.append(k) |
| scc_list.append(scc) |
| else: |
| scc_queue.append(v) |
| scc_list.sort(key=len,reverse=True) |
| return scc_list |
| |
| |
| def kosaraju_strongly_connected_components(G,source=None): |
| """Return nodes in strongly connected components of graph. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| An directed graph. |
| |
| Returns |
| ------- |
| comp : list of lists |
| A list of nodes for each component of G. |
| The list is ordered from largest connected component to smallest. |
| |
| Raises |
| ------ |
| NetworkXError: If G is undirected |
| |
| See Also |
| -------- |
| connected_components |
| |
| Notes |
| ----- |
| Uses Kosaraju's algorithm. |
| """ |
| if not G.is_directed(): |
| raise nx.NetworkXError("""Not allowed for undirected graph G. |
| Use connected_components() """) |
| components=[] |
| G=G.reverse(copy=False) |
| post=list(nx.dfs_postorder_nodes(G,source=source)) |
| G=G.reverse(copy=False) |
| seen={} |
| while post: |
| r=post.pop() |
| if r in seen: |
| continue |
| c=nx.dfs_preorder_nodes(G,r) |
| new=[v for v in c if v not in seen] |
| seen.update([(u,True) for u in new]) |
| components.append(new) |
| components.sort(key=len,reverse=True) |
| return components |
| |
| |
| def strongly_connected_components_recursive(G): |
| """Return nodes in strongly connected components of graph. |
| |
| Recursive version of algorithm. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| An directed graph. |
| |
| Returns |
| ------- |
| comp : list of lists |
| A list of nodes for each component of G. |
| The list is ordered from largest connected component to smallest. |
| |
| Raises |
| ------ |
| NetworkXError : If G is undirected |
| |
| See Also |
| -------- |
| connected_components |
| |
| Notes |
| ----- |
| Uses Tarjan's algorithm with Nuutila's modifications. |
| |
| References |
| ---------- |
| .. [1] Depth-first search and linear graph algorithms, R. Tarjan |
| SIAM Journal of Computing 1(2):146-160, (1972). |
| |
| .. [2] On finding the strongly connected components in a directed graph. |
| E. Nuutila and E. Soisalon-Soinen |
| Information Processing Letters 49(1): 9-14, (1994).. |
| """ |
| def visit(v,cnt): |
| root[v]=cnt |
| visited[v]=cnt |
| cnt+=1 |
| stack.append(v) |
| for w in G[v]: |
| if w not in visited: visit(w,cnt) |
| if w not in component: |
| root[v]=min(root[v],root[w]) |
| if root[v]==visited[v]: |
| component[v]=root[v] |
| tmpc=[v] # hold nodes in this component |
| while stack[-1]!=v: |
| w=stack.pop() |
| component[w]=root[v] |
| tmpc.append(w) |
| stack.remove(v) |
| scc.append(tmpc) # add to scc list |
| |
| if not G.is_directed(): |
| raise nx.NetworkXError("""Not allowed for undirected graph G. |
| Use connected_components() """) |
| |
| scc=[] |
| visited={} |
| component={} |
| root={} |
| cnt=0 |
| stack=[] |
| for source in G: |
| if source not in visited: |
| visit(source,cnt) |
| |
| scc.sort(key=len,reverse=True) |
| return scc |
| |
| |
| def strongly_connected_component_subgraphs(G): |
| """Return strongly connected components as subgraphs. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| A graph. |
| |
| Returns |
| ------- |
| glist : list |
| A list of graphs, one for each strongly connected component of G. |
| |
| See Also |
| -------- |
| connected_component_subgraphs |
| |
| Notes |
| ----- |
| The list is ordered from largest strongly connected component to smallest. |
| |
| Graph, node, and edge attributes are copied to the subgraphs. |
| """ |
| cc=strongly_connected_components(G) |
| graph_list=[] |
| for c in cc: |
| graph_list.append(G.subgraph(c).copy()) |
| return graph_list |
| |
| |
| def number_strongly_connected_components(G): |
| """Return number of strongly connected components in graph. |
| |
| Parameters |
| ---------- |
| G : NetworkX graph |
| A directed graph. |
| |
| Returns |
| ------- |
| n : integer |
| Number of strongly connected components |
| |
| See Also |
| -------- |
| connected_components |
| |
| Notes |
| ----- |
| For directed graphs only. |
| """ |
| return len(strongly_connected_components(G)) |
| |
| |
| def is_strongly_connected(G): |
| """Test directed graph for strong connectivity. |
| |
| Parameters |
| ---------- |
| G : NetworkX Graph |
| A directed graph. |
| |
| Returns |
| ------- |
| connected : bool |
| True if the graph is strongly connected, False otherwise. |
| |
| See Also |
| -------- |
| strongly_connected_components |
| |
| Notes |
| ----- |
| For directed graphs only. |
| """ |
| if not G.is_directed(): |
| raise nx.NetworkXError("""Not allowed for undirected graph G. |
| See is_connected() for connectivity test.""") |
| |
| if len(G)==0: |
| raise nx.NetworkXPointlessConcept( |
| """Connectivity is undefined for the null graph.""") |
| |
| return len(strongly_connected_components(G)[0])==len(G) |
| |
| def condensation(G, scc=None): |
| """Returns the condensation of G. |
| |
| The condensation of G is the graph with each of the strongly connected |
| components contracted into a single node. |
| |
| Parameters |
| ---------- |
| G : NetworkX DiGraph |
| A directed graph. |
| |
| scc: list (optional, default=None) |
| A list of strongly connected components. If provided, the elements in |
| `scc` must partition the nodes in `G`. If not provided, it will be |
| calculated as scc=nx.strongly_connected_components(G). |
| |
| Returns |
| ------- |
| C : NetworkX DiGraph |
| The condensation of G. The node labels are integers corresponding |
| to the index of the component in the list of strongly connected |
| components. |
| |
| Raises |
| ------ |
| NetworkXError: If G is not directed |
| |
| Notes |
| ----- |
| After contracting all strongly connected components to a single node, |
| the resulting graph is a directed acyclic graph. |
| """ |
| if not G.is_directed(): |
| raise nx.NetworkXError("""Not allowed for undirected graph G. |
| See is_connected() for connectivity test.""") |
| if scc is None: |
| scc = nx.strongly_connected_components(G) |
| mapping = {} |
| C = nx.DiGraph() |
| for i,component in enumerate(scc): |
| for n in component: |
| mapping[n] = i |
| C.add_nodes_from(range(len(scc))) |
| for u,v in G.edges(): |
| if mapping[u] != mapping[v]: |
| C.add_edge(mapping[u],mapping[v]) |
| return C |
