Source code for networkx.algorithms.components.strongly_connected

# -*- coding: utf-8 -*-
#    Copyright (C) 2004-2016 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
#
# Authors: Eben Kenah
#          Aric Hagberg (hagberg@lanl.gov)
#          Christopher Ellison
#          Ben Edwards (bedwards@cs.unm.edu)
"""Strongly connected components."""
import networkx as nx
from networkx.utils.decorators import not_implemented_for

__all__ = ['number_strongly_connected_components',
           'strongly_connected_components',
           'strongly_connected_component_subgraphs',
           'is_strongly_connected',
           'strongly_connected_components_recursive',
           'kosaraju_strongly_connected_components',
           'condensation']


@not_implemented_for('undirected')
[docs]def strongly_connected_components(G): """Generate nodes in strongly connected components of graph. Parameters ---------- G : NetworkX Graph An directed graph. Returns ------- comp : generator of sets A generator of sets of nodes, one for each strongly connected component of G. Raises ------ NetworkXNotImplemented : If G is undirected. Examples -------- Generate a sorted list of strongly connected components, largest first. >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) >>> nx.add_cycle(G, [10, 11, 12]) >>> [len(c) for c in sorted(nx.strongly_connected_components(G), ... key=len, reverse=True)] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort. >>> largest = max(nx.strongly_connected_components(G), key=len) See Also -------- connected_components weakly_connected_components kosaraju_strongly_connected_components Notes ----- Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_. 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).. """ preorder = {} lowlink = {} scc_found = {} scc_queue = [] 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.add(k) yield scc else: scc_queue.append(v)
@not_implemented_for('undirected')
[docs]def kosaraju_strongly_connected_components(G, source=None): """Generate nodes in strongly connected components of graph. Parameters ---------- G : NetworkX Graph An directed graph. Returns ------- comp : generator of sets A genrator of sets of nodes, one for each strongly connected component of G. Raises ------ NetworkXNotImplemented: If G is undirected. Examples -------- Generate a sorted list of strongly connected components, largest first. >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) >>> nx.add_cycle(G, [10, 11, 12]) >>> [len(c) for c in sorted(nx.kosaraju_strongly_connected_components(G), ... key=len, reverse=True)] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort. >>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len) See Also -------- strongly_connected_components Notes ----- Uses Kosaraju's algorithm. """ with nx.utils.reversed(G): post = list(nx.dfs_postorder_nodes(G, source=source)) seen = set() 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} yield new seen.update(new)
@not_implemented_for('undirected')
[docs]def strongly_connected_components_recursive(G): """Generate nodes in strongly connected components of graph. Recursive version of algorithm. Parameters ---------- G : NetworkX Graph An directed graph. Returns ------- comp : generator of sets A generator of sets of nodes, one for each strongly connected component of G. Raises ------ NetworkXNotImplemented : If G is undirected. Examples -------- Generate a sorted list of strongly connected components, largest first. >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) >>> nx.add_cycle(G, [10, 11, 12]) >>> [len(c) for c in sorted(nx.strongly_connected_components_recursive(G), ... key=len, reverse=True)] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort. >>> largest = max(nx.strongly_connected_components_recursive(G), key=len) See Also -------- connected_components Notes ----- Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_. 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: for c in visit(w, cnt): yield c 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.add(w) stack.remove(v) yield tmpc visited = {} component = {} root = {} cnt = 0 stack = [] for source in G: if source not in visited: for c in visit(source, cnt): yield c
@not_implemented_for('undirected')
[docs]def strongly_connected_component_subgraphs(G, copy=True): """Generate strongly connected components as subgraphs. Parameters ---------- G : NetworkX Graph A directed graph. copy : boolean, optional if copy is True, Graph, node, and edge attributes are copied to the subgraphs. Returns ------- comp : generator of graphs A generator of graphs, one for each strongly connected component of G. Raises ------ NetworkXNotImplemented: If G is undirected. Examples -------- Generate a sorted list of strongly connected components, largest first. >>> G = nx.cycle_graph(4, create_using=nx.DiGraph()) >>> nx.add_cycle(G, [10, 11, 12]) >>> [len(Gc) for Gc in sorted(nx.strongly_connected_component_subgraphs(G), ... key=len, reverse=True)] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort. >>> Gc = max(nx.strongly_connected_component_subgraphs(G), key=len) See Also -------- strongly_connected_components connected_component_subgraphs weakly_connected_component_subgraphs """ for comp in strongly_connected_components(G): if copy: yield G.subgraph(comp).copy() else: yield G.subgraph(comp)
@not_implemented_for('undirected')
[docs]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 Raises ------ NetworkXNotImplemented: If G is undirected. See Also -------- strongly_connected_components number_connected_components number_weakly_connected_components Notes ----- For directed graphs only. """ return len(list(strongly_connected_components(G)))
@not_implemented_for('undirected')
[docs]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. Raises ------ NetworkXNotImplemented: If G is undirected. See Also -------- is_weakly_connected is_semiconnected is_connected is_biconnected strongly_connected_components Notes ----- For directed graphs only. """ if len(G) == 0: raise nx.NetworkXPointlessConcept( """Connectivity is undefined for the null graph.""") return len(list(strongly_connected_components(G))[0]) == len(G)
@not_implemented_for('undirected')
[docs]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 or generator (optional, default=None) 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 graph C of G. The node labels are integers corresponding to the index of the component in the list of strongly connected components of G. C has a graph attribute named 'mapping' with a dictionary mapping the original nodes to the nodes in C to which they belong. Each node in C also has a node attribute 'members' with the set of original nodes in G that form the SCC that the node in C represents. Raises ------ NetworkXNotImplemented: If G is undirected. Notes ----- After contracting all strongly connected components to a single node, the resulting graph is a directed acyclic graph. """ if scc is None: scc = nx.strongly_connected_components(G) mapping = {} members = {} C = nx.DiGraph() i = 0 # required if G is empty for i, component in enumerate(scc): members[i] = component mapping.update((n, i) for n in component) number_of_components = i + 1 C.add_nodes_from(range(number_of_components)) C.add_edges_from((mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v]) # Add a list of members (ie original nodes) to each node (ie scc) in C. nx.set_node_attributes(C, 'members', members) # Add mapping dict as graph attribute C.graph['mapping'] = mapping return C