python-networkx 1.8.1-0ubuntu3 / usr / lib / python2.7 / dist-packages / networkx / algorithms / components / strongly_connected.py

# -*- 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