Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (12.7 KB)

1
""" Fast approximation for node connectivity
2
"""
3
#    Copyright (C) 2015 by
4
#    Jordi Torrents <jtorrents@milnou.net>
5
#    All rights reserved.
6
#    BSD license.
7
import itertools
8
from operator import itemgetter
9

    
10
import networkx as nx
11

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

    
14
__all__ = ['local_node_connectivity',
15
           'node_connectivity',
16
           'all_pairs_node_connectivity']
17

    
18
INF = float('inf')
19

    
20

    
21
def local_node_connectivity(G, source, target, cutoff=None):
22
    """Compute node connectivity between source and target.
23

24
    Pairwise or local node connectivity between two distinct and nonadjacent 
25
    nodes is the minimum number of nodes that must be removed (minimum 
26
    separating cutset) to disconnect them. By Menger's theorem, this is equal 
27
    to the number of node independent paths (paths that share no nodes other
28
    than source and target). Which is what we compute in this function.
29

30
    This algorithm is a fast approximation that gives an strict lower
31
    bound on the actual number of node independent paths between two nodes [1]_. 
32
    It works for both directed and undirected graphs.
33

34
    Parameters
35
    ----------
36

37
    G : NetworkX graph
38

39
    source : node
40
        Starting node for node connectivity
41

42
    target : node
43
        Ending node for node connectivity
44

45
    cutoff : integer
46
        Maximum node connectivity to consider. If None, the minimum degree
47
        of source or target is used as a cutoff. Default value None.
48

49
    Returns
50
    -------
51
    k: integer
52
       pairwise node connectivity
53

54
    Examples
55
    --------
56
    >>> # Platonic octahedral graph has node connectivity 4
57
    >>> # for each non adjacent node pair
58
    >>> from networkx.algorithms import approximation as approx
59
    >>> G = nx.octahedral_graph()
60
    >>> approx.local_node_connectivity(G, 0, 5)
61
    4
62

63
    Notes 
64
    -----
65
    This algorithm [1]_ finds node independents paths between two nodes by 
66
    computing their shortest path using BFS, marking the nodes of the path 
67
    found as 'used' and then searching other shortest paths excluding the 
68
    nodes marked as used until no more paths exist. It is not exact because 
69
    a shortest path could use nodes that, if the path were longer, may belong
70
    to two different node independent paths. Thus it only guarantees an
71
    strict lower bound on node connectivity.
72

73
    Note that the authors propose a further refinement, losing accuracy and 
74
    gaining speed, which is not implemented yet.
75

76
    See also
77
    --------
78
    all_pairs_node_connectivity
79
    node_connectivity
80

81
    References
82
    ----------
83
    .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for 
84
        Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
85
        http://eclectic.ss.uci.edu/~drwhite/working.pdf
86

87
    """
88
    if target == source:
89
        raise nx.NetworkXError("source and target have to be different nodes.")
90

    
91
    # Maximum possible node independent paths
92
    if G.is_directed():
93
        possible = min(G.out_degree(source), G.in_degree(target))
94
    else:
95
        possible = min(G.degree(source), G.degree(target))
96

    
97
    K = 0
98
    if not possible:
99
        return K
100

    
101
    if cutoff is None:
102
        cutoff = INF
103

    
104
    exclude = set()
105
    for i in range(min(possible, cutoff)):
106
        try:
107
            path = _bidirectional_shortest_path(G, source, target, exclude)
108
            exclude.update(set(path))
109
            K += 1
110
        except nx.NetworkXNoPath:
111
            break
112

    
113
    return K
114

    
115

    
116
def node_connectivity(G, s=None, t=None):
117
    r"""Returns an approximation for node connectivity for a graph or digraph G.
118

119
    Node connectivity is equal to the minimum number of nodes that
120
    must be removed to disconnect G or render it trivial. By Menger's theorem,
121
    this is equal to the number of node independent paths (paths that 
122
    share no nodes other than source and target).
123

124
    If source and target nodes are provided, this function returns the 
125
    local node connectivity: the minimum number of nodes that must be 
126
    removed to break all paths from source to target in G.
127

128
    This algorithm is based on a fast approximation that gives an strict lower
129
    bound on the actual number of node independent paths between two nodes [1]_. 
130
    It works for both directed and undirected graphs.
131

132
    Parameters
133
    ----------
134
    G : NetworkX graph
135
        Undirected graph
136

137
    s : node
138
        Source node. Optional. Default value: None.
139

140
    t : node
141
        Target node. Optional. Default value: None.
142

143
    Returns
144
    -------
145
    K : integer
146
        Node connectivity of G, or local node connectivity if source
147
        and target are provided.
148

149
    Examples
150
    --------
151
    >>> # Platonic octahedral graph is 4-node-connected 
152
    >>> from networkx.algorithms import approximation as approx
153
    >>> G = nx.octahedral_graph()
154
    >>> approx.node_connectivity(G)
155
    4
156

157
    Notes
158
    -----
159
    This algorithm [1]_ finds node independents paths between two nodes by 
160
    computing their shortest path using BFS, marking the nodes of the path 
161
    found as 'used' and then searching other shortest paths excluding the 
162
    nodes marked as used until no more paths exist. It is not exact because 
163
    a shortest path could use nodes that, if the path were longer, may belong
164
    to two different node independent paths. Thus it only guarantees an
165
    strict lower bound on node connectivity.
166

167
    See also
168
    --------
169
    all_pairs_node_connectivity
170
    local_node_connectivity
171

172
    References
173
    ----------
174
    .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for 
175
        Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
176
        http://eclectic.ss.uci.edu/~drwhite/working.pdf
177

178
    """
179
    if (s is not None and t is None) or (s is None and t is not None):
180
        raise nx.NetworkXError('Both source and target must be specified.')
181

    
182
    # Local node connectivity
183
    if s is not None and t is not None:
184
        if s not in G:
185
            raise nx.NetworkXError('node %s not in graph' % s)
186
        if t not in G:
187
            raise nx.NetworkXError('node %s not in graph' % t)
188
        return local_node_connectivity(G, s, t)
189

    
190
    # Global node connectivity
191
    if G.is_directed():
192
        connected_func = nx.is_weakly_connected
193
        iter_func = itertools.permutations
194

    
195
        def neighbors(v):
196
            return itertools.chain(G.predecessors(v), G.successors(v))
197
    else:
198
        connected_func = nx.is_connected
199
        iter_func = itertools.combinations
200
        neighbors = G.neighbors
201

    
202
    if not connected_func(G):
203
        return 0
204

    
205
    # Choose a node with minimum degree
206
    v, minimum_degree = min(G.degree(), key=itemgetter(1))
207
    # Node connectivity is bounded by minimum degree
208
    K = minimum_degree
209
    # compute local node connectivity with all non-neighbors nodes
210
    # and store the minimum
211
    for w in set(G) - set(neighbors(v)) - set([v]):
212
        K = min(K, local_node_connectivity(G, v, w, cutoff=K))
213
    # Same for non adjacent pairs of neighbors of v
214
    for x, y in iter_func(neighbors(v), 2):
215
        if y not in G[x] and x != y:
216
            K = min(K, local_node_connectivity(G, x, y, cutoff=K))
217
    return K
218

    
219

    
220
def all_pairs_node_connectivity(G, nbunch=None, cutoff=None):
221
    """ Compute node connectivity between all pairs of nodes.
222

223
    Pairwise or local node connectivity between two distinct and nonadjacent 
224
    nodes is the minimum number of nodes that must be removed (minimum 
225
    separating cutset) to disconnect them. By Menger's theorem, this is equal 
226
    to the number of node independent paths (paths that share no nodes other
227
    than source and target). Which is what we compute in this function.
228

229
    This algorithm is a fast approximation that gives an strict lower
230
    bound on the actual number of node independent paths between two nodes [1]_. 
231
    It works for both directed and undirected graphs.
232

233

234
    Parameters
235
    ----------
236
    G : NetworkX graph
237

238
    nbunch: container
239
        Container of nodes. If provided node connectivity will be computed
240
        only over pairs of nodes in nbunch.
241

242
    cutoff : integer
243
        Maximum node connectivity to consider. If None, the minimum degree
244
        of source or target is used as a cutoff in each pair of nodes.
245
        Default value None.
246

247
    Returns
248
    -------
249
    K : dictionary
250
        Dictionary, keyed by source and target, of pairwise node connectivity
251

252
    See Also
253
    --------
254
    local_node_connectivity
255
    all_pairs_node_connectivity
256

257
    References
258
    ----------
259
    .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for 
260
        Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
261
        http://eclectic.ss.uci.edu/~drwhite/working.pdf
262
    """
263
    if nbunch is None:
264
        nbunch = G
265
    else:
266
        nbunch = set(nbunch)
267

    
268
    directed = G.is_directed()
269
    if directed:
270
        iter_func = itertools.permutations
271
    else:
272
        iter_func = itertools.combinations
273

    
274
    all_pairs = {n: {} for n in nbunch}
275

    
276
    for u, v in iter_func(nbunch, 2):
277
        k = local_node_connectivity(G, u, v, cutoff=cutoff)
278
        all_pairs[u][v] = k
279
        if not directed:
280
            all_pairs[v][u] = k
281

    
282
    return all_pairs
283

    
284

    
285
def _bidirectional_shortest_path(G, source, target, exclude):
286
    """Returns shortest path between source and target ignoring nodes in the
287
    container 'exclude'.
288

289
    Parameters
290
    ----------
291

292
    G : NetworkX graph
293

294
    source : node
295
        Starting node for path
296

297
    target : node
298
        Ending node for path
299

300
    exclude: container
301
        Container for nodes to exclude from the search for shortest paths
302

303
    Returns
304
    -------
305
    path: list
306
        Shortest path between source and target ignoring nodes in 'exclude'
307

308
    Raises
309
    ------
310
    NetworkXNoPath: exception
311
        If there is no path or if nodes are adjacent and have only one path
312
        between them
313

314
    Notes
315
    -----
316
    This function and its helper are originally from
317
    networkx.algorithms.shortest_paths.unweighted and are modified to 
318
    accept the extra parameter 'exclude', which is a container for nodes 
319
    already used in other paths that should be ignored.
320

321
    References
322
    ----------
323
    .. [1] White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for 
324
        Node-Independent Paths. Santa Fe Institute Working Paper #01-07-035
325
        http://eclectic.ss.uci.edu/~drwhite/working.pdf
326

327
    """
328
    # call helper to do the real work
329
    results = _bidirectional_pred_succ(G, source, target, exclude)
330
    pred, succ, w = results
331

    
332
    # build path from pred+w+succ
333
    path = []
334
    # from source to w
335
    while w is not None:
336
        path.append(w)
337
        w = pred[w]
338
    path.reverse()
339
    # from w to target
340
    w = succ[path[-1]]
341
    while w is not None:
342
        path.append(w)
343
        w = succ[w]
344

    
345
    return path
346

    
347

    
348
def _bidirectional_pred_succ(G, source, target, exclude):
349
    # does BFS from both source and target and meets in the middle
350
    # excludes nodes in the container "exclude" from the search
351
    if source is None or target is None:
352
        raise nx.NetworkXException(
353
            "Bidirectional shortest path called without source or target")
354
    if target == source:
355
        return ({target: None}, {source: None}, source)
356

    
357
    # handle either directed or undirected
358
    if G.is_directed():
359
        Gpred = G.predecessors
360
        Gsucc = G.successors
361
    else:
362
        Gpred = G.neighbors
363
        Gsucc = G.neighbors
364

    
365
    # predecesssor and successors in search
366
    pred = {source: None}
367
    succ = {target: None}
368

    
369
    # initialize fringes, start with forward
370
    forward_fringe = [source]
371
    reverse_fringe = [target]
372

    
373
    level = 0
374

    
375
    while forward_fringe and reverse_fringe:
376
        # Make sure that we iterate one step forward and one step backwards
377
        # thus source and target will only trigger "found path" when they are
378
        # adjacent and then they can be safely included in the container 'exclude'
379
        level += 1
380
        if not level % 2 == 0:
381
            this_level = forward_fringe
382
            forward_fringe = []
383
            for v in this_level:
384
                for w in Gsucc(v):
385
                    if w in exclude:
386
                        continue
387
                    if w not in pred:
388
                        forward_fringe.append(w)
389
                        pred[w] = v
390
                    if w in succ:
391
                        return pred, succ, w  # found path
392
        else:
393
            this_level = reverse_fringe
394
            reverse_fringe = []
395
            for v in this_level:
396
                for w in Gpred(v):
397
                    if w in exclude:
398
                        continue
399
                    if w not in succ:
400
                        succ[w] = v
401
                        reverse_fringe.append(w)
402
                    if w in pred:
403
                        return pred, succ, w  # found path
404

    
405
    raise nx.NetworkXNoPath("No path between %s and %s." % (source, target))