path: root/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/connectivity/cuts.py

# -*- coding: utf-8 -*-
"""
Flow based cut algorithms
"""
# http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
# http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
import itertools
from operator import itemgetter
import networkx as nx
from networkx.algorithms.connectivity.connectivity import \
    _aux_digraph_node_connectivity, _aux_digraph_edge_connectivity, \
    dominating_set, node_connectivity

__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>'])

__all__ = [ 'minimum_st_node_cut',
            'minimum_node_cut',
            'minimum_st_edge_cut',
            'minimum_edge_cut',
            ]

def minimum_st_edge_cut(G, s, t, capacity='capacity'):
    """Returns the edges of the cut-set of a minimum (s, t)-cut.

    We use the max-flow min-cut theorem, i.e., the capacity of a minimum
    capacity cut is equal to the flow value of a maximum flow.

    Parameters
    ----------
    G : NetworkX graph
        Edges of the graph are expected to have an attribute called
        'capacity'. If this attribute is not present, the edge is
        considered to have infinite capacity.

    s : node
        Source node for the flow.

    t : node
        Sink node for the flow.

    capacity: string
        Edges of the graph G are expected to have an attribute capacity
        that indicates how much flow the edge can support. If this
        attribute is not present, the edge is considered to have
        infinite capacity. Default value: 'capacity'.

    Returns
    -------
    cutset : set
        Set of edges that, if removed from the graph, will disconnect it
    
    Raises
    ------
    NetworkXUnbounded
        If the graph has a path of infinite capacity, all cuts have
        infinite capacity and the function raises a NetworkXError.
    
    Examples
    --------
    >>> G = nx.DiGraph()
    >>> G.add_edge('x','a', capacity = 3.0)
    >>> G.add_edge('x','b', capacity = 1.0)
    >>> G.add_edge('a','c', capacity = 3.0)
    >>> G.add_edge('b','c', capacity = 5.0)
    >>> G.add_edge('b','d', capacity = 4.0)
    >>> G.add_edge('d','e', capacity = 2.0)
    >>> G.add_edge('c','y', capacity = 2.0)
    >>> G.add_edge('e','y', capacity = 3.0)
    >>> sorted(nx.minimum_edge_cut(G, 'x', 'y'))
    [('c', 'y'), ('x', 'b')]
    >>> nx.min_cut(G, 'x', 'y')
    3.0
    """
    try:
        flow, H = nx.ford_fulkerson_flow_and_auxiliary(G, s, t, capacity=capacity)
        cutset = set()
        # Compute reachable nodes from source in the residual network
        reachable = set(nx.single_source_shortest_path(H,s)) 
        # And unreachable nodes
        others = set(H) - reachable # - set([s])
        # Any edge in the original network linking these two partitions
        # is part of the edge cutset
        for u, nbrs in ((n, G[n]) for n in reachable):
            cutset.update((u,v) for v in nbrs if v in others)
        return cutset
    except nx.NetworkXUnbounded:
        # Should we raise any other exception or just let ford_fulkerson 
        # propagate nx.NetworkXUnbounded ?
        raise nx.NetworkXUnbounded("Infinite capacity path, no minimum cut.")

def minimum_st_node_cut(G, s, t, aux_digraph=None, mapping=None):
    r"""Returns a set of nodes of minimum cardinality that disconnect source
    from target in G.

    This function returns the set of nodes of minimum cardinality that, 
    if removed, would destroy all paths among source and target in G. 
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node.

    t : node
        Target node.

    Returns
    -------
    cutset : set
        Set of nodes that, if removed, would destroy all paths between 
        source and target in G.

    Examples
    --------
    >>> # Platonic icosahedral graph has node connectivity 5 
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_node_cut(G, 0, 6))
    5

    Notes
    -----
    This is a flow based implementation of minimum node cut. The algorithm 
    is based in solving a number of max-flow problems (ie local st-node
    connectivity, see local_node_connectivity) to determine the capacity 
    of the minimum cut on an auxiliary directed network that corresponds 
    to the minimum node cut of G. It handles both directed and undirected 
    graphs.

    This implementation is based on algorithm 11 in [1]_. We use the Ford 
    and Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_edge_cut
    max_flow
    ford_fulkerson 

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. 
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

    """
    if aux_digraph is None or mapping is None:
        H, mapping = _aux_digraph_node_connectivity(G)
    else:
        H = aux_digraph
    edge_cut = minimum_st_edge_cut(H, '%sB' % mapping[s], '%sA' % mapping[t])
    # Each node in the original graph maps to two nodes of the auxiliary graph
    node_cut = set(H.node[node]['id'] for edge in edge_cut for node in edge)
    return node_cut - set([s,t])

def minimum_node_cut(G, s=None, t=None):
    r"""Returns a set of nodes of minimum cardinality that disconnects G.

    If source and target nodes are provided, this function returns the 
    set of nodes of minimum cardinality that, if removed, would destroy 
    all paths among source and target in G. If not, it returns a set 
    of nodes of minimum cardinality that disconnects G.
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node. Optional (default=None)

    t : node
        Target node. Optional (default=None)

    Returns
    -------
    cutset : set
        Set of nodes that, if removed, would disconnect G. If source 
        and target nodes are provided, the set contians the nodes that
        if removed, would destroy all paths between source and target.

    Examples
    --------
    >>> # Platonic icosahedral graph has node connectivity 5 
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_node_cut(G))
    5
    >>> # this is the minimum over any pair of non adjacent nodes
    >>> from itertools import combinations
    >>> for u,v in combinations(G, 2):
    ...     if v not in G[u]:
    ...         assert(len(nx.minimum_node_cut(G,u,v)) == 5)
    ... 

    Notes
    -----
    This is a flow based implementation of minimum node cut. The algorithm 
    is based in solving a number of max-flow problems (ie local st-node
    connectivity, see local_node_connectivity) to determine the capacity 
    of the minimum cut on an auxiliary directed network that corresponds 
    to the minimum node cut of G. It handles both directed and undirected 
    graphs.

    This implementation is based on algorithm 11 in [1]_. We use the Ford 
    and Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_edge_cut
    max_flow
    ford_fulkerson 

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. 
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

    """
    # Local minimum node cut
    if s is not None and t is not None:
        if s not in G:
            raise nx.NetworkXError('node %s not in graph' % s)
        if t not in G:
            raise nx.NetworkXError('node %s not in graph' % t)
        return minimum_st_node_cut(G, s, t)
    # Global minimum node cut
    # Analog to the algoritm 11 for global node connectivity in [1]
    if G.is_directed():
        if not nx.is_weakly_connected(G):
            raise nx.NetworkXError('Input graph is not connected')
        iter_func = itertools.permutations
        def neighbors(v):
            return itertools.chain.from_iterable([G.predecessors_iter(v),
                                                  G.successors_iter(v)])
    else:
        if not nx.is_connected(G):
            raise nx.NetworkXError('Input graph is not connected')
        iter_func = itertools.combinations
        neighbors = G.neighbors_iter
    # Choose a node with minimum degree
    deg = G.degree()
    min_deg = min(deg.values())
    v = next(n for n,d in deg.items() if d == min_deg)
    # Initial node cutset is all neighbors of the node with minimum degree
    min_cut = set(G[v])
    # Reuse the auxiliary digraph
    H, mapping = _aux_digraph_node_connectivity(G)
    # compute st node cuts between v and all its non-neighbors nodes in G
    # and store the minimum
    for w in set(G) - set(neighbors(v)) - set([v]):
        this_cut = minimum_st_node_cut(G, v, w, aux_digraph=H, mapping=mapping)
        if len(min_cut) >= len(this_cut):
            min_cut = this_cut
    # Same for non adjacent pairs of neighbors of v
    for x,y in iter_func(neighbors(v),2):
        if y in G[x]: continue
        this_cut = minimum_st_node_cut(G, x, y, aux_digraph=H, mapping=mapping)
        if len(min_cut) >= len(this_cut):
            min_cut = this_cut
    return min_cut

def minimum_edge_cut(G, s=None, t=None):
    r"""Returns a set of edges of minimum cardinality that disconnects G.

    If source and target nodes are provided, this function returns the 
    set of edges of minimum cardinality that, if removed, would break 
    all paths among source and target in G. If not, it returns a set of 
    edges of minimum cardinality that disconnects G.
    
    Parameters
    ----------
    G : NetworkX graph

    s : node
        Source node. Optional (default=None)

    t : node
        Target node. Optional (default=None)

    Returns
    -------
    cutset : set
        Set of edges that, if removed, would disconnect G. If source 
        and target nodes are provided, the set contians the edges that
        if removed, would destroy all paths between source and target.

    Examples
    --------
    >>> # Platonic icosahedral graph has edge connectivity 5
    >>> G = nx.icosahedral_graph()
    >>> len(nx.minimum_edge_cut(G))
    5
    >>> # this is the minimum over any pair of nodes
    >>> from itertools import combinations
    >>> for u,v in combinations(G, 2):
    ...     assert(len(nx.minimum_edge_cut(G,u,v)) == 5)
    ... 

    Notes
    -----
    This is a flow based implementation of minimum edge cut. For
    undirected graphs the algorithm works by finding a 'small' dominating
    set of nodes of G (see algorithm 7 in [1]_) and computing the maximum
    flow between an arbitrary node in the dominating set and the rest of
    nodes in it. This is an implementation of algorithm 6 in [1]_.

    For directed graphs, the algorithm does n calls to the max flow function.
    This is an implementation of algorithm 8 in [1]_. We use the Ford and
    Fulkerson algorithm to compute max flow (see ford_fulkerson).

    See also
    --------
    node_connectivity
    edge_connectivity
    minimum_node_cut
    max_flow
    ford_fulkerson

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms.
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

    """
    # reuse auxiliary digraph
    H = _aux_digraph_edge_connectivity(G)
    # Local minimum edge cut if s and t are not None
    if s is not None and t is not None:
        if s not in G:
            raise nx.NetworkXError('node %s not in graph' % s)
        if t not in G:
            raise nx.NetworkXError('node %s not in graph' % t)
        return minimum_st_edge_cut(H, s, t)
    # Global minimum edge cut
    # Analog to the algoritm for global edge connectivity
    if G.is_directed():
        # Based on algorithm 8 in [1]
        if not nx.is_weakly_connected(G):
            raise nx.NetworkXError('Input graph is not connected')
        # Initial cutset is all edges of a node with minimum degree
        deg = G.degree()
        min_deg = min(deg.values())
        node = next(n for n,d in deg.items() if d==min_deg)
        min_cut = G.edges(node)
        nodes = G.nodes()
        n = len(nodes)
        for i in range(n):
            try:
                this_cut = minimum_st_edge_cut(H, nodes[i], nodes[i+1])
                if len(this_cut) <= len(min_cut):
                    min_cut = this_cut
            except IndexError: # Last node!
                this_cut = minimum_st_edge_cut(H, nodes[i], nodes[0])
                if len(this_cut) <= len(min_cut):
                    min_cut = this_cut
        return min_cut
    else: # undirected
        # Based on algorithm 6 in [1]
        if not nx.is_connected(G):
            raise nx.NetworkXError('Input graph is not connected')
        # Initial cutset is all edges of a node with minimum degree
        deg = G.degree()
        min_deg = min(deg.values())
        node = next(n for n,d in deg.items() if d==min_deg)
        min_cut = G.edges(node)
        # A dominating set is \lambda-covering
        # We need a dominating set with at least two nodes
        for node in G:
            D = dominating_set(G, start_with=node)
            v = D.pop()
            if D: break
        else:
            # in complete graphs the dominating set will always be of one node
            # thus we return min_cut, which now contains the edges of a node
            # with minimum degree
            return min_cut
        for w in D:
            this_cut = minimum_st_edge_cut(H, v, w)
            if len(this_cut) <= len(min_cut):
                min_cut = this_cut
        return min_cut