Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / components / strongly_connected.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# 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 warnings as _warnings ``` ```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') ``` ```def strongly_connected_components(G): ``` ``` """Generate nodes in strongly connected components of graph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` A 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_ with Nuutila's modifications_. ``` ``` Nonrecursive version of algorithm. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Depth-first search and linear graph algorithms, R. Tarjan ``` ``` SIAM Journal of Computing 1(2):146-160, (1972). ``` ``` ``` ``` ..  On finding the strongly connected components in a directed graph. ``` ``` E. Nuutila and E. Soisalon-Soinen ``` ``` Information Processing Letters 49(1): 9-14, (1994).. ``` ``` ``` ``` """ ``` ``` nbrs = {} ``` ``` 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 ``` ``` if v not in nbrs: ``` ``` nbrs[v] = iter(G[v]) ``` ``` v_nbrs = nbrs[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 G[v]: ``` ``` 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') ``` ```def kosaraju_strongly_connected_components(G, source=None): ``` ``` """Generate nodes in strongly connected components of graph. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` A 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') ``` ```def strongly_connected_components_recursive(G): ``` ``` """Generate nodes in strongly connected components of graph. ``` ``` ``` ``` Recursive version of algorithm. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` A 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_ with Nuutila's modifications_. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Depth-first search and linear graph algorithms, R. Tarjan ``` ``` SIAM Journal of Computing 1(2):146-160, (1972). ``` ``` ``` ``` ..  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') ``` ```def strongly_connected_component_subgraphs(G, copy=True): ``` ``` """DEPRECATED: Use ``(G.subgraph(c) for c in strongly_connected_components(G))`` ``` ``` ``` ``` Or ``(G.subgraph(c).copy() for c in strongly_connected_components(G))`` ``` ``` """ ``` ``` msg = "strongly_connected_component_subgraphs is deprecated and will be removed in 2.2" \ ``` ``` "use (G.subgraph(c).copy() for c in strongly_connected_components(G))" ``` ``` _warnings.warn(msg, DeprecationWarning) ``` ``` for c in strongly_connected_components(G): ``` ``` if copy: ``` ``` yield G.subgraph(c).copy() ``` ``` else: ``` ``` yield G.subgraph(c) ``` ```@not_implemented_for('undirected') ``` ```def number_strongly_connected_components(G): ``` ``` """Returns 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 sum(1 for scc in strongly_connected_components(G)) ``` ```@not_implemented_for('undirected') ``` ```def is_strongly_connected(G): ``` ``` """Test directed graph for strong connectivity. ``` ``` ``` ``` A directed graph is strongly connected if and only if every vertex in ``` ``` the graph is reachable from every other vertex. ``` ``` ``` ``` 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))) == len(G) ``` ```@not_implemented_for('undirected') ``` ```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() ``` ``` # Add mapping dict as graph attribute ``` ``` C.graph['mapping'] = mapping ``` ``` if len(G) == 0: ``` ``` return C ``` ``` 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') ``` ``` return C ```