Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (20.6 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2004-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Authors: Jon Crall (erotemic@gmail.com)
10
"""
11
Algorithms for finding k-edge-connected components and subgraphs.
12

13
A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such
14
that all pairs of node have an edge-connectivity of at least k.
15

16
A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G,
17
such that the subgraph of G defined by the nodes has an edge-connectivity at
18
least k.
19
"""
20
import networkx as nx
21
from networkx.utils import arbitrary_element
22
from networkx.utils import not_implemented_for
23
from networkx.algorithms import bridges
24
from functools import partial
25
import itertools as it
26

    
27
__all__ = [
28
    'k_edge_components',
29
    'k_edge_subgraphs',
30
    'bridge_components',
31
    'EdgeComponentAuxGraph',
32
]
33

    
34

    
35
@not_implemented_for('multigraph')
36
def k_edge_components(G, k):
37
    """Generates nodes in each maximal k-edge-connected component in G.
38

39
    Parameters
40
    ----------
41
    G : NetworkX graph
42

43
    k : Integer
44
        Desired edge connectivity
45

46
    Returns
47
    -------
48
    k_edge_components : a generator of k-edge-ccs. Each set of returned nodes
49
       will have k-edge-connectivity in the graph G.
50

51
    See Also
52
    -------
53
    :func:`local_edge_connectivity`
54
    :func:`k_edge_subgraphs` : similar to this function, but the subgraph
55
        defined by the nodes must also have k-edge-connectivity.
56
    :func:`k_components` : similar to this function, but uses node-connectivity
57
        instead of edge-connectivity
58

59
    Raises
60
    ------
61
    NetworkXNotImplemented:
62
        If the input graph is a multigraph.
63

64
    ValueError:
65
        If k is less than 1
66

67
    Notes
68
    -----
69
    Attempts to use the most efficient implementation available based on k.
70
    If k=1, this is simply simply connected components for directed graphs and
71
    connected components for undirected graphs.
72
    If k=2 on an efficient bridge connected component algorithm from _[1] is
73
    run based on the chain decomposition.
74
    Otherwise, the algorithm from _[2] is used.
75

76
    Example
77
    -------
78
    >>> import itertools as it
79
    >>> from networkx.utils import pairwise
80
    >>> paths = [
81
    ...     (1, 2, 4, 3, 1, 4),
82
    ...     (5, 6, 7, 8, 5, 7, 8, 6),
83
    ... ]
84
    >>> G = nx.Graph()
85
    >>> G.add_nodes_from(it.chain(*paths))
86
    >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
87
    >>> # note this returns {1, 4} unlike k_edge_subgraphs
88
    >>> sorted(map(sorted, nx.k_edge_components(G, k=3)))
89
    [[1, 4], [2], [3], [5, 6, 7, 8]]
90

91
    References
92
    ----------
93
    .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29
94
    .. [2] Wang, Tianhao, et al. (2015) A simple algorithm for finding all
95
        k-edge-connected components.
96
        http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264
97
    """
98
    # Compute k-edge-ccs using the most efficient algorithms available.
99
    if k < 1:
100
        raise ValueError('k cannot be less than 1')
101
    if G.is_directed():
102
        if k == 1:
103
            return nx.strongly_connected_components(G)
104
        else:
105
            # TODO: investigate https://arxiv.org/abs/1412.6466 for k=2
106
            aux_graph = EdgeComponentAuxGraph.construct(G)
107
            return aux_graph.k_edge_components(k)
108
    else:
109
        if k == 1:
110
            return nx.connected_components(G)
111
        elif k == 2:
112
            return bridge_components(G)
113
        else:
114
            aux_graph = EdgeComponentAuxGraph.construct(G)
115
            return aux_graph.k_edge_components(k)
116

    
117

    
118
@not_implemented_for('multigraph')
119
def k_edge_subgraphs(G, k):
120
    """Generates nodes in each maximal k-edge-connected subgraph in G.
121

122
    Parameters
123
    ----------
124
    G : NetworkX graph
125

126
    k : Integer
127
        Desired edge connectivity
128

129
    Returns
130
    -------
131
    k_edge_subgraphs : a generator of k-edge-subgraphs
132
        Each k-edge-subgraph is a maximal set of nodes that defines a subgraph
133
        of G that is k-edge-connected.
134

135
    See Also
136
    -------
137
    :func:`edge_connectivity`
138
    :func:`k_edge_components` : similar to this function, but nodes only
139
        need to have k-edge-connctivity within the graph G and the subgraphs
140
        might not be k-edge-connected.
141

142
    Raises
143
    ------
144
    NetworkXNotImplemented:
145
        If the input graph is a multigraph.
146

147
    ValueError:
148
        If k is less than 1
149

150
    Notes
151
    -----
152
    Attempts to use the most efficient implementation available based on k.
153
    If k=1, or k=2 and the graph is undirected, then this simply calls
154
    `k_edge_components`.  Otherwise the algorithm from _[1] is used.
155

156
    Example
157
    -------
158
    >>> import itertools as it
159
    >>> from networkx.utils import pairwise
160
    >>> paths = [
161
    ...     (1, 2, 4, 3, 1, 4),
162
    ...     (5, 6, 7, 8, 5, 7, 8, 6),
163
    ... ]
164
    >>> G = nx.Graph()
165
    >>> G.add_nodes_from(it.chain(*paths))
166
    >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
167
    >>> # note this does not return {1, 4} unlike k_edge_components
168
    >>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3)))
169
    [[1], [2], [3], [4], [5, 6, 7, 8]]
170

171
    References
172
    ----------
173
    .. [1] Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs
174
        from a large graph.  ACM International Conference on Extending Database
175
        Technology 2012 480-–491.
176
        https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf
177
    """
178
    if k < 1:
179
        raise ValueError('k cannot be less than 1')
180
    if G.is_directed():
181
        if k <= 1:
182
            # For directed graphs ,
183
            # When k == 1, k-edge-ccs and k-edge-subgraphs are the same
184
            return k_edge_components(G, k)
185
        else:
186
            return _k_edge_subgraphs_nodes(G, k)
187
    else:
188
        if k <= 2:
189
            # For undirected graphs,
190
            # when k <= 2, k-edge-ccs and k-edge-subgraphs are the same
191
            return k_edge_components(G, k)
192
        else:
193
            return _k_edge_subgraphs_nodes(G, k)
194

    
195

    
196
def _k_edge_subgraphs_nodes(G, k):
197
    """Helper to get the nodes from the subgraphs.
198

199
    This allows k_edge_subgraphs to return a generator.
200
    """
201
    for C in general_k_edge_subgraphs(G, k):
202
        yield set(C.nodes())
203

    
204

    
205
@not_implemented_for('directed')
206
@not_implemented_for('multigraph')
207
def bridge_components(G):
208
    """Finds all bridge-connected components G.
209

210
    Parameters
211
    ----------
212
    G : NetworkX undirected graph
213

214
    Returns
215
    -------
216
    bridge_components : a generator of 2-edge-connected components
217

218

219
    See Also
220
    --------
221
    :func:`k_edge_subgraphs` : this function is a special case for an
222
        undirected graph where k=2.
223
    :func:`biconnected_components` : similar to this function, but is defined
224
        using 2-node-connectivity instead of 2-edge-connectivity.
225

226
    Raises
227
    ------
228
    NetworkXNotImplemented:
229
        If the input graph is directed or a multigraph.
230

231
    Notes
232
    -----
233
    Bridge-connected components are also known as 2-edge-connected components.
234

235
    Example
236
    -------
237
    >>> # The barbell graph with parameter zero has a single bridge
238
    >>> G = nx.barbell_graph(5, 0)
239
    >>> from networkx.algorithms.connectivity.edge_kcomponents import bridge_components
240
    >>> sorted(map(sorted, bridge_components(G)))
241
    [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]
242
    """
243
    H = G.copy()
244
    H.remove_edges_from(bridges(G))
245
    for cc in nx.connected_components(H):
246
        yield cc
247

    
248

    
249
class EdgeComponentAuxGraph(object):
250
    r"""A simple algorithm to find all k-edge-connected components in a graph.
251

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

255
    Notes
256
    -----
257
    This implementation is based on [1]_. The idea is to construct an auxiliary
258
    graph from which the k-edge-ccs can be extracted in linear time. The
259
    auxiliary graph is constructed in $O(|V|\cdot F)$ operations, where F is the
260
    complexity of max flow. Querying the components takes an additional $O(|V|)$
261
    operations. This algorithm can be slow for large graphs, but it handles an
262
    arbitrary k and works for both directed and undirected inputs.
263

264
    The undirected case for k=1 is exactly connected components.
265
    The undirected case for k=2 is exactly bridge connected components.
266
    The directed case for k=1 is exactly strongly connected components.
267

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

274
    Example
275
    -------
276
    >>> import itertools as it
277
    >>> from networkx.utils import pairwise
278
    >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
279
    >>> # Build an interesting graph with multiple levels of k-edge-ccs
280
    >>> paths = [
281
    ...     (1, 2, 3, 4, 1, 3, 4, 2),  # a 3-edge-cc (a 4 clique)
282
    ...     (5, 6, 7, 5),  # a 2-edge-cc (a 3 clique)
283
    ...     (1, 5),  # combine first two ccs into a 1-edge-cc
284
    ...     (0,),  # add an additional disconnected 1-edge-cc
285
    ... ]
286
    >>> G = nx.Graph()
287
    >>> G.add_nodes_from(it.chain(*paths))
288
    >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
289
    >>> # Constructing the AuxGraph takes about O(n ** 4)
290
    >>> aux_graph = EdgeComponentAuxGraph.construct(G)
291
    >>> # Once constructed, querying takes O(n)
292
    >>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))
293
    [[0], [1, 2, 3, 4, 5, 6, 7]]
294
    >>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))
295
    [[0], [1, 2, 3, 4], [5, 6, 7]]
296
    >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
297
    [[0], [1, 2, 3, 4], [5], [6], [7]]
298
    >>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))
299
    [[0], [1], [2], [3], [4], [5], [6], [7]]
300

301
    Example
302
    -------
303
    >>> # The auxiliary graph is primarilly used for k-edge-ccs but it
304
    >>> # can also speed up the queries of k-edge-subgraphs by refining the
305
    >>> # search space.
306
    >>> import itertools as it
307
    >>> from networkx.utils import pairwise
308
    >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
309
    >>> paths = [
310
    ...     (1, 2, 4, 3, 1, 4),
311
    ... ]
312
    >>> G = nx.Graph()
313
    >>> G.add_nodes_from(it.chain(*paths))
314
    >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
315
    >>> aux_graph = EdgeComponentAuxGraph.construct(G)
316
    >>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))
317
    [[1], [2], [3], [4]]
318
    >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
319
    [[1, 4], [2], [3]]
320
    """
321

    
322
    # @not_implemented_for('multigraph')  # TODO: fix decor for classmethods
323
    @classmethod
324
    def construct(EdgeComponentAuxGraph, G):
325
        """Builds an auxiliary graph encoding edge-connectivity between nodes.
326

327
        Notes
328
        -----
329
        Given G=(V, E), initialize an empty auxiliary graph A.
330
        Choose an arbitrary source node s.  Initialize a set N of available
331
        nodes (that can be used as the sink). The algorithm picks an
332
        arbitrary node t from N - {s}, and then computes the minimum st-cut
333
        (S, T) with value w. If G is directed the the minimum of the st-cut or
334
        the ts-cut is used instead. Then, the edge (s, t) is added to the
335
        auxiliary graph with weight w. The algorithm is called recursively
336
        first using S as the available nodes and s as the source, and then
337
        using T and t. Recursion stops when the source is the only available
338
        node.
339

340
        Parameters
341
        ----------
342
        G : NetworkX graph
343
        """
344
        # workaround for classmethod decorator
345
        not_implemented_for('multigraph')(lambda G: G)(G)
346

    
347
        def _recursive_build(H, A, source, avail):
348
            # Terminate once the flow has been compute to every node.
349
            if {source} == avail:
350
                return
351
            # pick an arbitrary node as the sink
352
            sink = arbitrary_element(avail - {source})
353
            # find the minimum cut and its weight
354
            value, (S, T) = nx.minimum_cut(H, source, sink)
355
            if H.is_directed():
356
                # check if the reverse direction has a smaller cut
357
                value_, (T_, S_) = nx.minimum_cut(H, sink, source)
358
                if value_ < value:
359
                    value, S, T = value_, S_, T_
360
            # add edge with weight of cut to the aux graph
361
            A.add_edge(source, sink, weight=value)
362
            # recursively call until all but one node is used
363
            _recursive_build(H, A, source, avail.intersection(S))
364
            _recursive_build(H, A, sink, avail.intersection(T))
365

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

    
371
        # A is the auxiliary graph to be constructed
372
        # It is a weighted undirected tree
373
        A = nx.Graph()
374

    
375
        # Pick an arbitrary node as the source
376
        if H.number_of_nodes() > 0:
377
            source = arbitrary_element(H.nodes())
378
            # Initialize a set of elements that can be chosen as the sink
379
            avail = set(H.nodes())
380

    
381
            # This constructs A
382
            _recursive_build(H, A, source, avail)
383

    
384
        # This class is a container the holds the auxiliary graph A and
385
        # provides access the the k_edge_components function.
386
        self = EdgeComponentAuxGraph()
387
        self.A = A
388
        self.H = H
389
        return self
390

    
391
    def k_edge_components(self, k):
392
        """Queries the auxiliary graph for k-edge-connected components.
393

394
        Parameters
395
        ----------
396
        k : Integer
397
            Desired edge connectivity
398

399
        Returns
400
        -------
401
        k_edge_components : a generator of k-edge-ccs
402

403
        Notes
404
        -----
405
        Given the auxiliary graph, the k-edge-connected components can be
406
        determined in linear time by removing all edges with weights less than
407
        k from the auxiliary graph.  The resulting connected components are the
408
        k-edge-ccs in the original graph.
409
        """
410
        if k < 1:
411
            raise ValueError('k cannot be less than 1')
412
        A = self.A
413
        # "traverse the auxiliary graph A and delete all edges with weights less
414
        # than k"
415
        aux_weights = nx.get_edge_attributes(A, 'weight')
416
        # Create a relevant graph with the auxiliary edges with weights >= k
417
        R = nx.Graph()
418
        R.add_nodes_from(A.nodes())
419
        R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
420

    
421
        # Return the nodes that are k-edge-connected in the original graph
422
        for cc in nx.connected_components(R):
423
            yield cc
424

    
425
    def k_edge_subgraphs(self, k):
426
        """Queries the auxiliary graph for k-edge-connected subgraphs.
427

428
        Parameters
429
        ----------
430
        k : Integer
431
            Desired edge connectivity
432

433
        Returns
434
        -------
435
        k_edge_subgraphs : a generator of k-edge-subgraphs
436

437
        Notes
438
        -----
439
        Refines the k-edge-ccs into k-edge-subgraphs. The running time is more
440
        than $O(|V|)$.
441

442
        For single values of k it is faster to use `nx.k_edge_subgraphs`.
443
        But for multiple values of k, it can be faster to build AuxGraph and
444
        then use this method.
445
        """
446
        if k < 1:
447
            raise ValueError('k cannot be less than 1')
448
        H = self.H
449
        A = self.A
450
        # "traverse the auxiliary graph A and delete all edges with weights less
451
        # than k"
452
        aux_weights = nx.get_edge_attributes(A, 'weight')
453
        # Create a relevant graph with the auxiliary edges with weights >= k
454
        R = nx.Graph()
455
        R.add_nodes_from(A.nodes())
456
        R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
457

    
458
        # Return the components whose subgraphs are k-edge-connected
459
        for cc in nx.connected_components(R):
460
            if len(cc) < k:
461
                # Early return optimization
462
                for node in cc:
463
                    yield {node}
464
            else:
465
                # Call subgraph solution to refine the results
466
                C = H.subgraph(cc)
467
                for sub_cc in k_edge_subgraphs(C, k):
468
                    yield sub_cc
469

    
470

    
471
def _low_degree_nodes(G, k, nbunch=None):
472
    """Helper for finding nodes with degree less than k."""
473
    # Nodes with degree less than k cannot be k-edge-connected.
474
    if G.is_directed():
475
        # Consider both in and out degree in the directed case
476
        seen = set()
477
        for node, degree in G.out_degree(nbunch):
478
            if degree < k:
479
                seen.add(node)
480
                yield node
481
        for node, degree in G.in_degree(nbunch):
482
            if node not in seen and degree < k:
483
                seen.add(node)
484
                yield node
485
    else:
486
        # Only the degree matters in the undirected case
487
        for node, degree in G.degree(nbunch):
488
            if degree < k:
489
                yield node
490

    
491

    
492
def _high_degree_components(G, k):
493
    """Helper for filtering components that can't be k-edge-connected.
494

495
    Removes and generates each node with degree less than k.  Then generates
496
    remaining components where all nodes have degree at least k.
497
    """
498
    # Iteravely remove parts of the graph that are not k-edge-connected
499
    H = G.copy()
500
    singletons = set(_low_degree_nodes(H, k))
501
    while singletons:
502
        # Only search neighbors of removed nodes
503
        nbunch = set(it.chain.from_iterable(map(H.neighbors, singletons)))
504
        nbunch.difference_update(singletons)
505
        H.remove_nodes_from(singletons)
506
        for node in singletons:
507
            yield {node}
508
        singletons = set(_low_degree_nodes(H, k, nbunch))
509

    
510
    # Note: remaining connected components may not be k-edge-connected
511
    if G.is_directed():
512
        for cc in nx.strongly_connected_components(H):
513
            yield cc
514
    else:
515
        for cc in nx.connected_components(H):
516
            yield cc
517

    
518

    
519
def general_k_edge_subgraphs(G, k):
520
    """General algorithm to find all maximal k-edge-connected subgraphs in G.
521

522
    Returns
523
    -------
524
    k_edge_subgraphs : a generator of nx.Graphs that are k-edge-subgraphs
525
        Each k-edge-subgraph is a maximal set of nodes that defines a subgraph
526
        of G that is k-edge-connected.
527

528
    Notes
529
    -----
530
    Implementation of the basic algorithm from _[1].  The basic idea is to find
531
    a global minimum cut of the graph. If the cut value is at least k, then the
532
    graph is a k-edge-connected subgraph and can be added to the results.
533
    Otherwise, the cut is used to split the graph in two and the procedure is
534
    applied recursively. If the graph is just a single node, then it is also
535
    added to the results. At the end, each result is either guaranteed to be
536
    a single node or a subgraph of G that is k-edge-connected.
537

538
    This implementation contains optimizations for reducing the number of calls
539
    to max-flow, but there are other optimizations in _[1] that could be
540
    implemented.
541

542
    References
543
    ----------
544
    .. [1] Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs
545
        from a large graph.  ACM International Conference on Extending Database
546
        Technology 2012 480-–491.
547
        https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf
548

549
    Example
550
    -------
551
    >>> from networkx.utils import pairwise
552
    >>> paths = [
553
    ...     (11, 12, 13, 14, 11, 13, 14, 12),  # a 4-clique
554
    ...     (21, 22, 23, 24, 21, 23, 24, 22),  # another 4-clique
555
    ...     # connect the cliques with high degree but low connectivity
556
    ...     (50, 13),
557
    ...     (12, 50, 22),
558
    ...     (13, 102, 23),
559
    ...     (14, 101, 24),
560
    ... ]
561
    >>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))
562
    >>> sorted(map(len, k_edge_subgraphs(G, k=3)))
563
    [1, 1, 1, 4, 4]
564
    """
565
    if k < 1:
566
        raise ValueError('k cannot be less than 1')
567

    
568
    # Node pruning optimization (incorporates early return)
569
    # find_ccs is either connected_components/strongly_connected_components
570
    find_ccs = partial(_high_degree_components, k=k)
571

    
572
    # Quick return optimization
573
    if G.number_of_nodes() < k:
574
        for node in G.nodes():
575
            yield G.subgraph([node]).copy()
576
        return
577

    
578
    # Intermediate results
579
    R0 = {G.subgraph(cc).copy() for cc in find_ccs(G)}
580
    # Subdivide CCs in the intermediate results until they are k-conn
581
    while R0:
582
        G1 = R0.pop()
583
        if G1.number_of_nodes() == 1:
584
            yield G1
585
        else:
586
            # Find a global minimum cut
587
            cut_edges = nx.minimum_edge_cut(G1)
588
            cut_value = len(cut_edges)
589
            if cut_value < k:
590
                # G1 is not k-edge-connected, so subdivide it
591
                G1.remove_edges_from(cut_edges)
592
                for cc in find_ccs(G1):
593
                    R0.add(G1.subgraph(cc).copy())
594
            else:
595
                # Otherwise we found a k-edge-connected subgraph
596
                yield G1