Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / components / biconnected.py @ 5cef0f13

History | View | Annotate | Download (13.1 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2011-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: Jordi Torrents (jtorrents@milnou.net)
10
#          Dan Schult (dschult@colgate.edu)
11
#          Aric Hagberg (aric.hagberg@gmail.com)
12
"""Biconnected components and articulation points."""
13
import warnings as _warnings
14
from itertools import chain
15
import networkx as nx
16
from networkx.utils.decorators import not_implemented_for
17

    
18
__all__ = [
19
    'biconnected_components',
20
    'biconnected_component_edges',
21
    'biconnected_component_subgraphs',
22
    'is_biconnected',
23
    'articulation_points',
24
]
25

    
26

    
27
@not_implemented_for('directed')
28
def is_biconnected(G):
29
    """Returns True if the graph is biconnected, False otherwise.
30

31
    A graph is biconnected if, and only if, it cannot be disconnected by
32
    removing only one node (and all edges incident on that node).  If
33
    removing a node increases the number of disconnected components
34
    in the graph, that node is called an articulation point, or cut
35
    vertex.  A biconnected graph has no articulation points.
36

37
    Parameters
38
    ----------
39
    G : NetworkX Graph
40
        An undirected graph.
41

42
    Returns
43
    -------
44
    biconnected : bool
45
        True if the graph is biconnected, False otherwise.
46

47
    Raises
48
    ------
49
    NetworkXNotImplemented :
50
        If the input graph is not undirected.
51

52
    Examples
53
    --------
54
    >>> G = nx.path_graph(4)
55
    >>> print(nx.is_biconnected(G))
56
    False
57
    >>> G.add_edge(0, 3)
58
    >>> print(nx.is_biconnected(G))
59
    True
60

61
    See Also
62
    --------
63
    biconnected_components
64
    articulation_points
65
    biconnected_component_edges
66
    is_strongly_connected
67
    is_weakly_connected
68
    is_connected
69
    is_semiconnected
70

71
    Notes
72
    -----
73
    The algorithm to find articulation points and biconnected
74
    components is implemented using a non-recursive depth-first-search
75
    (DFS) that keeps track of the highest level that back edges reach
76
    in the DFS tree.  A node `n` is an articulation point if, and only
77
    if, there exists a subtree rooted at `n` such that there is no
78
    back edge from any successor of `n` that links to a predecessor of
79
    `n` in the DFS tree.  By keeping track of all the edges traversed
80
    by the DFS we can obtain the biconnected components because all
81
    edges of a bicomponent will be traversed consecutively between
82
    articulation points.
83

84
    References
85
    ----------
86
    .. [1] Hopcroft, J.; Tarjan, R. (1973).
87
       "Efficient algorithms for graph manipulation".
88
       Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
89

90
    """
91
    bcc = list(biconnected_components(G))
92
    if len(bcc) == 1:
93
        return len(bcc[0]) == len(G)
94
    return False  # Multiple bicomponents or No bicomponents (empty graph?)
95
#    if len(bcc) == 0:  # No bicomponents (it could be an empty graph)
96
#        return False
97
#    return len(bcc[0]) == len(G)
98

    
99

    
100
@not_implemented_for('directed')
101
def biconnected_component_edges(G):
102
    """Returns a generator of lists of edges, one list for each biconnected
103
    component of the input graph.
104

105
    Biconnected components are maximal subgraphs such that the removal of a
106
    node (and all edges incident on that node) will not disconnect the
107
    subgraph.  Note that nodes may be part of more than one biconnected
108
    component.  Those nodes are articulation points, or cut vertices.
109
    However, each edge belongs to one, and only one, biconnected component.
110

111
    Notice that by convention a dyad is considered a biconnected component.
112

113
    Parameters
114
    ----------
115
    G : NetworkX Graph
116
        An undirected graph.
117

118
    Returns
119
    -------
120
    edges : generator of lists
121
        Generator of lists of edges, one list for each bicomponent.
122

123
    Raises
124
    ------
125
    NetworkXNotImplemented :
126
        If the input graph is not undirected.
127

128
    Examples
129
    --------
130
    >>> G = nx.barbell_graph(4, 2)
131
    >>> print(nx.is_biconnected(G))
132
    False
133
    >>> bicomponents_edges = list(nx.biconnected_component_edges(G))
134
    >>> len(bicomponents_edges)
135
    5
136
    >>> G.add_edge(2, 8)
137
    >>> print(nx.is_biconnected(G))
138
    True
139
    >>> bicomponents_edges = list(nx.biconnected_component_edges(G))
140
    >>> len(bicomponents_edges)
141
    1
142

143
    See Also
144
    --------
145
    is_biconnected,
146
    biconnected_components,
147
    articulation_points,
148

149
    Notes
150
    -----
151
    The algorithm to find articulation points and biconnected
152
    components is implemented using a non-recursive depth-first-search
153
    (DFS) that keeps track of the highest level that back edges reach
154
    in the DFS tree.  A node `n` is an articulation point if, and only
155
    if, there exists a subtree rooted at `n` such that there is no
156
    back edge from any successor of `n` that links to a predecessor of
157
    `n` in the DFS tree.  By keeping track of all the edges traversed
158
    by the DFS we can obtain the biconnected components because all
159
    edges of a bicomponent will be traversed consecutively between
160
    articulation points.
161

162
    References
163
    ----------
164
    .. [1] Hopcroft, J.; Tarjan, R. (1973).
165
           "Efficient algorithms for graph manipulation".
166
           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
167

168
    """
169
    for comp in _biconnected_dfs(G, components=True):
170
        yield comp
171

    
172

    
173
@not_implemented_for('directed')
174
def biconnected_components(G):
175
    """Returns a generator of sets of nodes, one set for each biconnected
176
    component of the graph
177

178
    Biconnected components are maximal subgraphs such that the removal of a
179
    node (and all edges incident on that node) will not disconnect the
180
    subgraph. Note that nodes may be part of more than one biconnected
181
    component.  Those nodes are articulation points, or cut vertices.  The
182
    removal of articulation points will increase the number of connected
183
    components of the graph.
184

185
    Notice that by convention a dyad is considered a biconnected component.
186

187
    Parameters
188
    ----------
189
    G : NetworkX Graph
190
        An undirected graph.
191

192
    Returns
193
    -------
194
    nodes : generator
195
        Generator of sets of nodes, one set for each biconnected component.
196

197
    Raises
198
    ------
199
    NetworkXNotImplemented :
200
        If the input graph is not undirected.
201

202
    See Also
203
    --------
204
    k_components : this function is a special case where k=2
205
    bridge_components : similar to this function, but is defined using
206
        2-edge-connectivity instead of 2-node-connectivity.
207

208

209
    Examples
210
    --------
211
    >>> G = nx.lollipop_graph(5, 1)
212
    >>> print(nx.is_biconnected(G))
213
    False
214
    >>> bicomponents = list(nx.biconnected_components(G))
215
    >>> len(bicomponents)
216
    2
217
    >>> G.add_edge(0, 5)
218
    >>> print(nx.is_biconnected(G))
219
    True
220
    >>> bicomponents = list(nx.biconnected_components(G))
221
    >>> len(bicomponents)
222
    1
223

224
    You can generate a sorted list of biconnected components, largest
225
    first, using sort.
226

227
    >>> G.remove_edge(0, 5)
228
    >>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)]
229
    [5, 2]
230

231
    If you only want the largest connected component, it's more
232
    efficient to use max instead of sort.
233

234
    >>> Gc = max(nx.biconnected_components(G), key=len)
235

236
    See Also
237
    --------
238
    is_biconnected
239
    articulation_points
240
    biconnected_component_edges
241

242
    Notes
243
    -----
244
    The algorithm to find articulation points and biconnected
245
    components is implemented using a non-recursive depth-first-search
246
    (DFS) that keeps track of the highest level that back edges reach
247
    in the DFS tree.  A node `n` is an articulation point if, and only
248
    if, there exists a subtree rooted at `n` such that there is no
249
    back edge from any successor of `n` that links to a predecessor of
250
    `n` in the DFS tree.  By keeping track of all the edges traversed
251
    by the DFS we can obtain the biconnected components because all
252
    edges of a bicomponent will be traversed consecutively between
253
    articulation points.
254

255
    References
256
    ----------
257
    .. [1] Hopcroft, J.; Tarjan, R. (1973).
258
           "Efficient algorithms for graph manipulation".
259
           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
260

261
    """
262
    for comp in _biconnected_dfs(G, components=True):
263
        yield set(chain.from_iterable(comp))
264

    
265

    
266
@not_implemented_for('directed')
267
def biconnected_component_subgraphs(G, copy=True):
268
    """DEPRECATED: Use ``(G.subgraph(c) for c in biconnected_components(G))``
269

270
           Or ``(G.subgraph(c).copy() for c in biconnected_components(G))``
271
    """
272
    msg = "connected_component_subgraphs is deprecated and will be removed" \
273
        "in 2.2. Use (G.subgraph(c).copy() for c in biconnected_components(G))"
274
    _warnings.warn(msg, DeprecationWarning)
275
    for c in biconnected_components(G):
276
        if copy:
277
            yield G.subgraph(c).copy()
278
        else:
279
            yield G.subgraph(c)
280

    
281

    
282
@not_implemented_for('directed')
283
def articulation_points(G):
284
    """Yield the articulation points, or cut vertices, of a graph.
285

286
    An articulation point or cut vertex is any node whose removal (along with
287
    all its incident edges) increases the number of connected components of
288
    a graph.  An undirected connected graph without articulation points is
289
    biconnected. Articulation points belong to more than one biconnected
290
    component of a graph.
291

292
    Notice that by convention a dyad is considered a biconnected component.
293

294
    Parameters
295
    ----------
296
    G : NetworkX Graph
297
        An undirected graph.
298

299
    Yields
300
    ------
301
    node
302
        An articulation point in the graph.
303

304
    Raises
305
    ------
306
    NetworkXNotImplemented :
307
        If the input graph is not undirected.
308

309
    Examples
310
    --------
311

312
    >>> G = nx.barbell_graph(4, 2)
313
    >>> print(nx.is_biconnected(G))
314
    False
315
    >>> len(list(nx.articulation_points(G)))
316
    4
317
    >>> G.add_edge(2, 8)
318
    >>> print(nx.is_biconnected(G))
319
    True
320
    >>> len(list(nx.articulation_points(G)))
321
    0
322

323
    See Also
324
    --------
325
    is_biconnected
326
    biconnected_components
327
    biconnected_component_edges
328

329
    Notes
330
    -----
331
    The algorithm to find articulation points and biconnected
332
    components is implemented using a non-recursive depth-first-search
333
    (DFS) that keeps track of the highest level that back edges reach
334
    in the DFS tree.  A node `n` is an articulation point if, and only
335
    if, there exists a subtree rooted at `n` such that there is no
336
    back edge from any successor of `n` that links to a predecessor of
337
    `n` in the DFS tree.  By keeping track of all the edges traversed
338
    by the DFS we can obtain the biconnected components because all
339
    edges of a bicomponent will be traversed consecutively between
340
    articulation points.
341

342
    References
343
    ----------
344
    .. [1] Hopcroft, J.; Tarjan, R. (1973).
345
           "Efficient algorithms for graph manipulation".
346
           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
347

348
    """
349
    seen = set()
350
    for articulation in _biconnected_dfs(G, components=False):
351
        if articulation not in seen:
352
            seen.add(articulation)
353
            yield articulation
354

    
355

    
356
@not_implemented_for('directed')
357
def _biconnected_dfs(G, components=True):
358
    # depth-first search algorithm to generate articulation points
359
    # and biconnected components
360
    visited = set()
361
    for start in G:
362
        if start in visited:
363
            continue
364
        discovery = {start: 0}  # time of first discovery of node during search
365
        low = {start: 0}
366
        root_children = 0
367
        visited.add(start)
368
        edge_stack = []
369
        stack = [(start, start, iter(G[start]))]
370
        while stack:
371
            grandparent, parent, children = stack[-1]
372
            try:
373
                child = next(children)
374
                if grandparent == child:
375
                    continue
376
                if child in visited:
377
                    if discovery[child] <= discovery[parent]:  # back edge
378
                        low[parent] = min(low[parent], discovery[child])
379
                        if components:
380
                            edge_stack.append((parent, child))
381
                else:
382
                    low[child] = discovery[child] = len(discovery)
383
                    visited.add(child)
384
                    stack.append((parent, child, iter(G[child])))
385
                    if components:
386
                        edge_stack.append((parent, child))
387
            except StopIteration:
388
                stack.pop()
389
                if len(stack) > 1:
390
                    if low[parent] >= discovery[grandparent]:
391
                        if components:
392
                            ind = edge_stack.index((grandparent, parent))
393
                            yield edge_stack[ind:]
394
                            edge_stack = edge_stack[:ind]
395
                        else:
396
                            yield grandparent
397
                    low[grandparent] = min(low[parent], low[grandparent])
398
                elif stack:  # length 1 so grandparent is root
399
                    root_children += 1
400
                    if components:
401
                        ind = edge_stack.index((grandparent, parent))
402
                        yield edge_stack[ind:]
403
        if not components:
404
            # root node is articulation point if it has more than 1 child
405
            if root_children > 1:
406
                yield start