Algorithms for finding k-edge-connected compoments

kedgeconn.py

# -*- coding: utf-8 -*-
"""
Algorithms for finding k-edge-connected compoments.
"""
import networkx as nx
from networkx.utils import arbitrary_element


class EdgeComponentAuxGraph(object):
    """
    A simple algorithm to find all k-edge-connected compoments in a graph.

    Constructing the AuxillaryGraph (which may take some time) allows for the
    k-edge-ccs to be found in linear time for arbitrary k.

    Notes
    -----
    This implementation is based on [1]_. The idea is to construct an auxillary
    graph from which the k-edge-ccs can be extracted in linear time. The
    auxillary graph is constructed in O(|V|F) operations, where F is the
    complexity of max flow. Querying the compoments takes an additional O(|V|)
    operations. This algorithm can be slow for large graphs, but it handles an
    arbitrary k and works for both directed and undirected inputs.

    The undirected case for k=1 is exactly connected compoments.
    The directed case for k=1 is exactly strongly connected compoments.

    Multigraph inputs are not supported, but could be once there is a
    multigraph mincut implementation.

    References
    ----------
    .. [1] Wang, Tianhao, et al. A simple algorithm for finding all
        k-edge-connected components.
        http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

    Example
    -------
    >>> import networkx as nx
    >>> from itertools import chain
    >>> from networkx.utils import pairwise
    >>> # Build an interesting graph with multiple levels of k-edge-ccs
    >>> a, b, c, d, e, f, g, x = range(1, 9)
    >>> paths = [
    >>>     (1, 2, 3, 4, 1, 3, 4, 2), # a 3-edge-cc (a 4 clique)
    >>>     (5, 6, 7, 5), # a 2-edge-cc (a 3 clique)
    >>>     (1, 5),  # combine first two ccs into a 1-edge-cc
    >>>     (0,), # add an additional disconnected 1-edge-cc
    >>> ]
    >>> G = nx.Graph()
    >>> G.add_nodes_from(chain(*paths))
    >>> G.add_edges_from(chain(*[pairwise(path) for path in paths]))
    >>> # Constructing the AuxGraph takes about O(n ** 4)
    >>> aux_graph = EdgeComponentAuxGraph.construct(G)
    >>> # Once constructed, querying takes O(n)
    >>> one_compoments = list(aux_graph.k_edge_components(k=1))
    [{0}, {1, 2, 3, 4, 5, 6, 7}]
    >>> two_compoments = list(aux_graph.k_edge_components(k=2))
    [{0}, {1, 2, 3, 4}, {5, 6, 7}]
    >>> three_compoments = list(aux_graph.k_edge_components(k=3))
    [{0}, {1, 2, 3, 4}, {5}, {6}, {7}]
    >>> four_compoments = list(aux_graph.k_edge_components(k=4))
    [{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}]
    """

    # @not_implemented_for('multi')
    @classmethod
    def construct(EdgeComponentAuxGraph, G):
        """Builds the auxillary graph

        Notes
        -----
        Given G=(V, E), initialize an empty auxillary graph A.
        Choose an arbitrary source vertex s.  Initialize a set N of available
        vertices (that can be used as the sink). The algorithm picks an
        arbitrary vertex t from N - {s}, and then computes the minimum st-cut
        (S, T) with value w. If G is directed the the minimum of the st-cut or
        the ts-cut is used instead. Then, the edge (s, t) is added to the
        auxillary graph with weight w. The algorithm is called recursively
        first using S as the available vertices and s as the source, and then
        using T and t. Recusion stops when the source is the only available
        node.

        Parameters
        ----------
        G : NetworkX graph

        >>> import networkx as nx
        >>> from itertools import chain
        >>> from networkx.utils import pairwise
        >>> paths = [
        >>>     (1, 2, 4, 3, 1, 4),
        >>> ]
        >>> G = nx.Graph()
        >>> G.add_nodes_from(chain(*paths))
        >>> G.add_edges_from(chain(*[pairwise(path) for path in paths]))
        >>> aux_graph = EdgeComponentAuxGraph.construct(G)

        """

        def _recursive_build(H, A, source, avail):
            # Terminate once the flow has been compute to every node.
            if {source} == avail:
                return
            # pick an arbitrary vertex as the sink
            sink = arbitrary_element(avail - {source})
            # find the minimum cut and its weight
            value, (S, T) = nx.minimum_cut(H, source, sink)
            if H.is_directed():
                # check if the reverse direction has a smaller cut
                value_, (T_, S_) = nx.minimum_cut(H, sink, source)
                if value_ < value:
                    value, S, T = value_, S_, T_
            print('---')
            print('source, sink, val = {}, {}, {}'.format(source, sink, value))
            # add edge with weight of cut to the aux graph
            A.add_edge(source, sink, weight=value)
            # recursively call until all but one node is used
            _recursive_build(H, A, source, avail.intersection(S))
            _recursive_build(H, A, sink, avail.intersection(T))

        # Copy input to ensure all edges have unit capacity
        H = G.__class__()
        H.add_nodes_from(G.nodes())
        H.add_edges_from(G.edges(), capacity=1)

        # A is the auxillary graph to be constructed
        # It is a weighted undirected tree
        A = nx.Graph()

        # Pick an arbitrary vertex as the source
        source = arbitrary_element(H.nodes())
        # Initialize a set of elements that can be chosen as the sink
        avail = set(H.nodes())

        # This constructs A
        _recursive_build(H, A, source, avail)

        # This class is a container the holds the auxillary graph A and
        # provides access the the k_edge_components function.
        self = EdgeComponentAuxGraph()
        self.A = A
        return self

    def k_edge_components(self, k):
        """Queries the auxillary graph

        Notes
        -----
        Given the auxillary graph, the k-edge-connected components can be
        determined in linear time by removing all edges with weights less than
        k from the auxillary graph.  The resulting connected components are the
        k-edge-ccs in the original graph.

        Parameters
        ----------
        k : Integer
            Desired edge connectivity

        Returns
        -------
        k_edge_compoments : a generator of k-edge-connected compoments
            Each k-edge-cc is a maximal set of nodes in G with edge
            connectivity at least `k`.

        Raises
        ------
        ValueError:
            If k is less than 1
        """
        if k < 1:
            raise ValueError('k cannot be less than 1')
        A = self.A
        aux_weights = nx.get_edge_attributes(A, 'weight')

        # "traverse the auxiliary graph A and delete all edges with weights less
        # than k"
        R = A.copy()
        R.remove_edges_from([e for e, w in aux_weights.items() if w < k])

        # Create a relevant graph with the auxillary edges with weights >= k
        # R = nx.Graph()
        # R.add_nodes_from(A.nodes())
        # R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
        # Return the connected components of the relevant graph
        return nx.connected_components(R)