Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / kcutsets.py @ 5cef0f13

History | View | Annotate | Download (9.53 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Kanevsky all minimum node k cutsets algorithm.
4
"""
5
import copy
6
from collections import defaultdict
7
from itertools import combinations
8
from operator import itemgetter
9

    
10
import networkx as nx
11
from .utils import build_auxiliary_node_connectivity
12
from networkx.algorithms.flow import (
13
    build_residual_network,
14
    edmonds_karp,
15
    shortest_augmenting_path,
16
)
17
default_flow_func = edmonds_karp
18

    
19

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

    
22
__all__ = ['all_node_cuts']
23

    
24

    
25
def all_node_cuts(G, k=None, flow_func=None):
26
    r"""Returns all minimum k cutsets of an undirected graph G. 
27

28
    This implementation is based on Kanevsky's algorithm [1]_ for finding all
29
    minimum-size node cut-sets of an undirected graph G; ie the set (or sets) 
30
    of nodes of cardinality equal to the node connectivity of G. Thus if 
31
    removed, would break G into two or more connected components.
32

33
    Parameters
34
    ----------
35
    G : NetworkX graph
36
        Undirected graph
37

38
    k : Integer
39
        Node connectivity of the input graph. If k is None, then it is 
40
        computed. Default value: None.
41

42
    flow_func : function
43
        Function to perform the underlying flow computations. Default value
44
        edmonds_karp. This function performs better in sparse graphs with
45
        right tailed degree distributions. shortest_augmenting_path will
46
        perform better in denser graphs.
47

48

49
    Returns
50
    -------
51
    cuts : a generator of node cutsets
52
        Each node cutset has cardinality equal to the node connectivity of
53
        the input graph.
54

55
    Examples
56
    --------
57
    >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2
58
    >>> G = nx.grid_2d_graph(5, 5)
59
    >>> cutsets = list(nx.all_node_cuts(G))
60
    >>> len(cutsets)
61
    4
62
    >>> all(2 == len(cutset) for cutset in cutsets)
63
    True
64
    >>> nx.node_connectivity(G)
65
    2
66

67
    Notes
68
    -----
69
    This implementation is based on the sequential algorithm for finding all
70
    minimum-size separating vertex sets in a graph [1]_. The main idea is to
71
    compute minimum cuts using local maximum flow computations among a set 
72
    of nodes of highest degree and all other non-adjacent nodes in the Graph.
73
    Once we find a minimum cut, we add an edge between the high degree
74
    node and the target node of the local maximum flow computation to make 
75
    sure that we will not find that minimum cut again.
76

77
    See also
78
    --------
79
    node_connectivity
80
    edmonds_karp
81
    shortest_augmenting_path
82

83
    References
84
    ----------
85
    .. [1]  Kanevsky, A. (1993). Finding all minimum-size separating vertex 
86
            sets in a graph. Networks 23(6), 533--541.
87
            http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract
88

89
    """
90
    if not nx.is_connected(G):
91
        raise nx.NetworkXError('Input graph is disconnected.')
92

    
93
    # Address some corner cases first.
94
    # For complete Graphs
95
    if nx.density(G) == 1:
96
        for cut_set in combinations(G, len(G) - 1):
97
            yield set(cut_set)
98
        return
99
    # Initialize data structures.
100
    # Keep track of the cuts already computed so we do not repeat them.
101
    seen = []
102
    # Even-Tarjan reduction is what we call auxiliary digraph
103
    # for node connectivity.
104
    H = build_auxiliary_node_connectivity(G)
105
    H_nodes = H.nodes # for speed
106
    mapping = H.graph['mapping']
107
    # Keep a copy of original predecessors, H will be modified later.
108
    # Shallow copy is enough.
109
    original_H_pred = copy.copy(H._pred)
110
    R = build_residual_network(H, 'capacity')
111
    kwargs = dict(capacity='capacity', residual=R)
112
    # Define default flow function
113
    if flow_func is None:
114
        flow_func = default_flow_func
115
    if flow_func is shortest_augmenting_path:
116
        kwargs['two_phase'] = True
117
    # Begin the actual algorithm
118
    # step 1: Find node connectivity k of G
119
    if k is None:
120
        k = nx.node_connectivity(G, flow_func=flow_func)
121
    # step 2:
122
    # Find k nodes with top degree, call it X:
123
    X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]}
124
    # Check if X is a k-node-cutset
125
    if _is_separating_set(G, X):
126
        seen.append(X)
127
        yield X
128

    
129
    for x in X:
130
        # step 3: Compute local connectivity flow of x with all other
131
        # non adjacent nodes in G
132
        non_adjacent = set(G) - X - set(G[x])
133
        for v in non_adjacent:
134
            # step 4: compute maximum flow in an Even-Tarjan reduction H of G
135
            # and step 5: build the associated residual network R
136
            R = flow_func(H, '%sB' % mapping[x], '%sA' % mapping[v], **kwargs)
137
            flow_value = R.graph['flow_value']
138

    
139
            if flow_value == k:
140
                # Find the nodes incident to the flow.
141
                E1 = flowed_edges = [(u, w) for (u, w, d) in
142
                                     R.edges(data=True)
143
                                     if d['flow'] != 0]
144
                VE1 = incident_nodes = set([n for edge in E1 for n in edge])
145
                # Remove saturated edges form the residual network.
146
                # Note that reversed edges are introduced with capacity 0
147
                # in the residual graph and they need to be removed too.
148
                saturated_edges = [(u, w, d) for (u, w, d) in
149
                                   R.edges(data=True)
150
                                   if d['capacity'] == d['flow']
151
                                   or d['capacity'] == 0]
152
                R.remove_edges_from(saturated_edges)
153
                R_closure = nx.transitive_closure(R)
154
                # step 6: shrink the strongly connected components of
155
                # residual flow network R and call it L.
156
                L = nx.condensation(R)
157
                cmap = L.graph['mapping']
158
                inv_cmap = defaultdict(list)
159
                for n, scc in cmap.items():
160
                    inv_cmap[scc].append(n)
161
                # Find the incident nodes in the condensed graph.
162
                VE1 = set([cmap[n] for n in VE1])
163
                # step 7: Compute all antichains of L;
164
                # they map to closed sets in H.
165
                # Any edge in H that links a closed set is part of a cutset.
166
                for antichain in nx.antichains(L):
167
                    # Only antichains that are subsets of incident nodes counts.
168
                    # Lemma 8 in reference.
169
                    if not set(antichain).issubset(VE1):
170
                        continue
171
                    # Nodes in an antichain of the condensation graph of
172
                    # the residual network map to a closed set of nodes that
173
                    # define a node partition of the auxiliary digraph H
174
                    # through taking all of antichain's predecessors in the
175
                    # transitive closure.
176
                    S = set()
177
                    for scc in antichain:
178
                        S.update(inv_cmap[scc])
179
                    S_ancestors = set()
180
                    for n in S:
181
                        S_ancestors.update(R_closure._pred[n])
182
                    S.update(S_ancestors)
183
                    if '%sB' % mapping[x] not in S or '%sA' % mapping[v] in S:
184
                        continue
185
                    # Find the cutset that links the node partition (S,~S) in H
186
                    cutset = set()
187
                    for u in S:
188
                        cutset.update((u, w)
189
                                      for w in original_H_pred[u] if w not in S)
190
                    # The edges in H that form the cutset are internal edges
191
                    # (ie edges that represent a node of the original graph G)
192
                    if any([H_nodes[u]['id'] != H_nodes[w]['id']
193
                            for u, w in cutset]):
194
                        continue
195
                    node_cut = {H_nodes[u]['id'] for u, _ in cutset}
196

    
197
                    if len(node_cut) == k:
198
                        # The cut is invalid if it includes internal edges of
199
                        # end nodes. The other half of Lemma 8 in ref.
200
                        if x in node_cut or v in node_cut:
201
                            continue
202
                        if node_cut not in seen:
203
                            yield node_cut
204
                            seen.append(node_cut)
205

    
206
                # Add an edge (x, v) to make sure that we do not
207
                # find this cutset again. This is equivalent
208
                # of adding the edge in the input graph
209
                # G.add_edge(x, v) and then regenerate H and R:
210
                # Add edges to the auxiliary digraph.
211
                # See build_residual_network for convention we used
212
                # in residual graphs.
213
                H.add_edge('%sB' % mapping[x], '%sA' % mapping[v],
214
                           capacity=1)
215
                H.add_edge('%sB' % mapping[v], '%sA' % mapping[x],
216
                           capacity=1)
217
                # Add edges to the residual network.
218
                R.add_edge('%sB' % mapping[x], '%sA' % mapping[v],
219
                           capacity=1)
220
                R.add_edge('%sA' % mapping[v], '%sB' % mapping[x],
221
                           capacity=0)
222
                R.add_edge('%sB' % mapping[v], '%sA' % mapping[x],
223
                           capacity=1)
224
                R.add_edge('%sA' % mapping[x], '%sB' % mapping[v],
225
                           capacity=0)
226

    
227
                # Add again the saturated edges to reuse the residual network
228
                R.add_edges_from(saturated_edges)
229

    
230

    
231
def _is_separating_set(G, cut):
232
    """Assumes that the input graph is connected"""
233
    if len(cut) == len(G) - 1:
234
        return True
235

    
236
    H = nx.restricted_view(G, cut, [])
237
    if nx.is_connected(H):
238
        return False
239
    return True