Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / flow / gomory_hu.py @ 5cef0f13

History | View | Annotate | Download (6.25 KB)

1
# -*- coding: utf-8 -*-
2
# gomory_hu.py - function for computing Gomory Hu trees
3
#
4
# Copyright 2017-2019 NetworkX developers.
5
#
6
# This file is part of NetworkX.
7
#
8
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
9
# information.
10
#
11
# Author: Jordi Torrents <jordi.t21@gmail.com>
12
"""
13
Gomory-Hu tree of undirected Graphs.
14
"""
15
import networkx as nx
16
from networkx.utils import not_implemented_for
17

    
18
from .edmondskarp import edmonds_karp
19
from .utils import build_residual_network
20

    
21
default_flow_func = edmonds_karp
22

    
23
__all__ = ['gomory_hu_tree']
24

    
25

    
26
@not_implemented_for('directed')
27
def gomory_hu_tree(G, capacity='capacity', flow_func=None):
28
    r"""Returns the Gomory-Hu tree of an undirected graph G.
29

30
    A Gomory-Hu tree of an undirected graph with capacities is a
31
    weighted tree that represents the minimum s-t cuts for all s-t
32
    pairs in the graph.
33

34
    It only requires `n-1` minimum cut computations instead of the
35
    obvious `n(n-1)/2`. The tree represents all s-t cuts as the
36
    minimum cut value among any pair of nodes is the minimum edge
37
    weight in the shortest path between the two nodes in the
38
    Gomory-Hu tree.
39

40
    The Gomory-Hu tree also has the property that removing the
41
    edge with the minimum weight in the shortest path between
42
    any two nodes leaves two connected components that form
43
    a partition of the nodes in G that defines the minimum s-t
44
    cut.
45

46
    See Examples section below for details.
47

48
    Parameters
49
    ----------
50
    G : NetworkX graph
51
        Undirected graph
52

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

59
    flow_func : function
60
        Function to perform the underlying flow computations. Default value
61
        :func:`edmonds_karp`. This function performs better in sparse graphs
62
        with right tailed degree distributions.
63
        :func:`shortest_augmenting_path` will perform better in denser
64
        graphs.
65

66
    Returns
67
    -------
68
    Tree : NetworkX graph
69
        A NetworkX graph representing the Gomory-Hu tree of the input graph.
70

71
    Raises
72
    ------
73
    NetworkXNotImplemented : Exception
74
        Raised if the input graph is directed.
75

76
    NetworkXError: Exception
77
        Raised if the input graph is an empty Graph.
78

79
    Examples
80
    --------
81
    >>> G = nx.karate_club_graph()
82
    >>> nx.set_edge_attributes(G, 1, 'capacity')
83
    >>> T = nx.gomory_hu_tree(G)
84
    >>> # The value of the minimum cut between any pair
85
    ... # of nodes in G is the minimum edge weight in the
86
    ... # shortest path between the two nodes in the
87
    ... # Gomory-Hu tree.
88
    ... def minimum_edge_weight_in_shortest_path(T, u, v):
89
    ...     path = nx.shortest_path(T, u, v, weight='weight')
90
    ...     return min((T[u][v]['weight'], (u,v)) for (u, v) in zip(path, path[1:]))
91
    >>> u, v = 0, 33
92
    >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
93
    >>> cut_value
94
    10
95
    >>> nx.minimum_cut_value(G, u, v)
96
    10
97
    >>> # The Comory-Hu tree also has the property that removing the
98
    ... # edge with the minimum weight in the shortest path between
99
    ... # any two nodes leaves two connected components that form
100
    ... # a partition of the nodes in G that defines the minimum s-t
101
    ... # cut.
102
    ... cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
103
    >>> T.remove_edge(*edge)
104
    >>> U, V = list(nx.connected_components(T))
105
    >>> # Thus U and V form a partition that defines a minimum cut
106
    ... # between u and v in G. You can compute the edge cut set,
107
    ... # that is, the set of edges that if removed from G will 
108
    ... # disconnect u from v in G, with this information:
109
    ... cutset = set()
110
    >>> for x, nbrs in ((n, G[n]) for n in U):
111
    ...     cutset.update((x, y) for y in nbrs if y in V)
112
    >>> # Because we have set the capacities of all edges to 1
113
    ... # the cutset contains ten edges
114
    ... len(cutset)
115
    10
116
    >>> # You can use any maximum flow algorithm for the underlying
117
    ... # flow computations using the argument flow_func
118
    ... from networkx.algorithms import flow
119
    >>> T = nx.gomory_hu_tree(G, flow_func=flow.boykov_kolmogorov)
120
    >>> cut_value, edge = minimum_edge_weight_in_shortest_path(T, u, v)
121
    >>> cut_value
122
    10
123
    >>> nx.minimum_cut_value(G, u, v, flow_func=flow.boykov_kolmogorov)
124
    10
125

126
    Notes
127
    -----
128
    This implementation is based on Gusfield approach [1]_ to compute
129
    Comory-Hu trees, which does not require node contractions and has
130
    the same computational complexity than the original method.
131

132
    See also
133
    --------
134
    :func:`minimum_cut`
135
    :func:`maximum_flow`
136

137
    References
138
    ----------
139
    .. [1] Gusfield D: Very simple methods for all pairs network flow analysis.
140
           SIAM J Comput 19(1):143-155, 1990.
141

142
    """
143
    if flow_func is None:
144
        flow_func = default_flow_func
145

    
146
    if len(G) == 0:  # empty graph
147
        msg = 'Empty Graph does not have a Gomory-Hu tree representation'
148
        raise nx.NetworkXError(msg)
149

    
150
    # Start the tree as a star graph with an arbitrary node at the center
151
    tree = {}
152
    labels = {}
153
    iter_nodes = iter(G)
154
    root = next(iter_nodes)
155
    for n in iter_nodes:
156
        tree[n] = root
157

    
158
    # Reuse residual network
159
    R = build_residual_network(G, capacity)
160

    
161
    # For all the leaves in the star graph tree (that is n-1 nodes).
162
    for source in tree:
163
        # Find neighbor in the tree
164
        target = tree[source]
165
        # compute minimum cut
166
        cut_value, partition = nx.minimum_cut(G, source, target,
167
                                              capacity=capacity, flow_func=flow_func,
168
                                              residual=R)
169
        labels[(source, target)] = cut_value
170
        # Update the tree
171
        # Source will always be in partition[0] and target in partition[1]
172
        for node in partition[0]:
173
            if node != source and node in tree and tree[node] == target:
174
                tree[node] = source
175
                labels[(node, source)] = labels.get((node, target), cut_value)
176
    # Build the tree
177
    T = nx.Graph()
178
    T.add_nodes_from(G)
179
    T.add_weighted_edges_from(((u, v, labels[(u, v)]) for u, v in tree.items()))
180
    return T