1"""Biconnected components and articulation points."""
2from itertools import chain
3from networkx.utils.decorators import not_implemented_for
4
5__all__ = [
6    "biconnected_components",
7    "biconnected_component_edges",
8    "is_biconnected",
9    "articulation_points",
10]
11
12
13@not_implemented_for("directed")
14def is_biconnected(G):
15    """Returns True if the graph is biconnected, False otherwise.
16
17    A graph is biconnected if, and only if, it cannot be disconnected by
18    removing only one node (and all edges incident on that node).  If
19    removing a node increases the number of disconnected components
20    in the graph, that node is called an articulation point, or cut
21    vertex.  A biconnected graph has no articulation points.
22
23    Parameters
24    ----------
25    G : NetworkX Graph
26        An undirected graph.
27
28    Returns
29    -------
30    biconnected : bool
31        True if the graph is biconnected, False otherwise.
32
33    Raises
34    ------
35    NetworkXNotImplemented
36        If the input graph is not undirected.
37
38    Examples
39    --------
40    >>> G = nx.path_graph(4)
41    >>> print(nx.is_biconnected(G))
42    False
43    >>> G.add_edge(0, 3)
44    >>> print(nx.is_biconnected(G))
45    True
46
47    See Also
48    --------
49    biconnected_components
50    articulation_points
51    biconnected_component_edges
52    is_strongly_connected
53    is_weakly_connected
54    is_connected
55    is_semiconnected
56
57    Notes
58    -----
59    The algorithm to find articulation points and biconnected
60    components is implemented using a non-recursive depth-first-search
61    (DFS) that keeps track of the highest level that back edges reach
62    in the DFS tree.  A node `n` is an articulation point if, and only
63    if, there exists a subtree rooted at `n` such that there is no
64    back edge from any successor of `n` that links to a predecessor of
65    `n` in the DFS tree.  By keeping track of all the edges traversed
66    by the DFS we can obtain the biconnected components because all
67    edges of a bicomponent will be traversed consecutively between
68    articulation points.
69
70    References
71    ----------
72    .. [1] Hopcroft, J.; Tarjan, R. (1973).
73       "Efficient algorithms for graph manipulation".
74       Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
75
76    """
77    bcc = list(biconnected_components(G))
78    if len(bcc) == 1:
79        return len(bcc[0]) == len(G)
80    return False  # Multiple bicomponents or No bicomponents (empty graph?)
81
82
83#    if len(bcc) == 0:  # No bicomponents (it could be an empty graph)
84#        return False
85#    return len(bcc[0]) == len(G)
86
87
88@not_implemented_for("directed")
89def biconnected_component_edges(G):
90    """Returns a generator of lists of edges, one list for each biconnected
91    component of the input graph.
92
93    Biconnected components are maximal subgraphs such that the removal of a
94    node (and all edges incident on that node) will not disconnect the
95    subgraph.  Note that nodes may be part of more than one biconnected
96    component.  Those nodes are articulation points, or cut vertices.
97    However, each edge belongs to one, and only one, biconnected component.
98
99    Notice that by convention a dyad is considered a biconnected component.
100
101    Parameters
102    ----------
103    G : NetworkX Graph
104        An undirected graph.
105
106    Returns
107    -------
108    edges : generator of lists
109        Generator of lists of edges, one list for each bicomponent.
110
111    Raises
112    ------
113    NetworkXNotImplemented
114        If the input graph is not undirected.
115
116    Examples
117    --------
118    >>> G = nx.barbell_graph(4, 2)
119    >>> print(nx.is_biconnected(G))
120    False
121    >>> bicomponents_edges = list(nx.biconnected_component_edges(G))
122    >>> len(bicomponents_edges)
123    5
124    >>> G.add_edge(2, 8)
125    >>> print(nx.is_biconnected(G))
126    True
127    >>> bicomponents_edges = list(nx.biconnected_component_edges(G))
128    >>> len(bicomponents_edges)
129    1
130
131    See Also
132    --------
133    is_biconnected,
134    biconnected_components,
135    articulation_points,
136
137    Notes
138    -----
139    The algorithm to find articulation points and biconnected
140    components is implemented using a non-recursive depth-first-search
141    (DFS) that keeps track of the highest level that back edges reach
142    in the DFS tree.  A node `n` is an articulation point if, and only
143    if, there exists a subtree rooted at `n` such that there is no
144    back edge from any successor of `n` that links to a predecessor of
145    `n` in the DFS tree.  By keeping track of all the edges traversed
146    by the DFS we can obtain the biconnected components because all
147    edges of a bicomponent will be traversed consecutively between
148    articulation points.
149
150    References
151    ----------
152    .. [1] Hopcroft, J.; Tarjan, R. (1973).
153           "Efficient algorithms for graph manipulation".
154           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
155
156    """
157    yield from _biconnected_dfs(G, components=True)
158
159
160@not_implemented_for("directed")
161def biconnected_components(G):
162    """Returns a generator of sets of nodes, one set for each biconnected
163    component of the graph
164
165    Biconnected components are maximal subgraphs such that the removal of a
166    node (and all edges incident on that node) will not disconnect the
167    subgraph. Note that nodes may be part of more than one biconnected
168    component.  Those nodes are articulation points, or cut vertices.  The
169    removal of articulation points will increase the number of connected
170    components of the graph.
171
172    Notice that by convention a dyad is considered a biconnected component.
173
174    Parameters
175    ----------
176    G : NetworkX Graph
177        An undirected graph.
178
179    Returns
180    -------
181    nodes : generator
182        Generator of sets of nodes, one set for each biconnected component.
183
184    Raises
185    ------
186    NetworkXNotImplemented
187        If the input graph is not undirected.
188
189    Examples
190    --------
191    >>> G = nx.lollipop_graph(5, 1)
192    >>> print(nx.is_biconnected(G))
193    False
194    >>> bicomponents = list(nx.biconnected_components(G))
195    >>> len(bicomponents)
196    2
197    >>> G.add_edge(0, 5)
198    >>> print(nx.is_biconnected(G))
199    True
200    >>> bicomponents = list(nx.biconnected_components(G))
201    >>> len(bicomponents)
202    1
203
204    You can generate a sorted list of biconnected components, largest
205    first, using sort.
206
207    >>> G.remove_edge(0, 5)
208    >>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)]
209    [5, 2]
210
211    If you only want the largest connected component, it's more
212    efficient to use max instead of sort.
213
214    >>> Gc = max(nx.biconnected_components(G), key=len)
215
216    To create the components as subgraphs use:
217    ``(G.subgraph(c).copy() for c in biconnected_components(G))``
218
219    See Also
220    --------
221    is_biconnected
222    articulation_points
223    biconnected_component_edges
224    k_components : this function is a special case where k=2
225    bridge_components : similar to this function, but is defined using
226        2-edge-connectivity instead of 2-node-connectivity.
227
228    Notes
229    -----
230    The algorithm to find articulation points and biconnected
231    components is implemented using a non-recursive depth-first-search
232    (DFS) that keeps track of the highest level that back edges reach
233    in the DFS tree.  A node `n` is an articulation point if, and only
234    if, there exists a subtree rooted at `n` such that there is no
235    back edge from any successor of `n` that links to a predecessor of
236    `n` in the DFS tree.  By keeping track of all the edges traversed
237    by the DFS we can obtain the biconnected components because all
238    edges of a bicomponent will be traversed consecutively between
239    articulation points.
240
241    References
242    ----------
243    .. [1] Hopcroft, J.; Tarjan, R. (1973).
244           "Efficient algorithms for graph manipulation".
245           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
246
247    """
248    for comp in _biconnected_dfs(G, components=True):
249        yield set(chain.from_iterable(comp))
250
251
252@not_implemented_for("directed")
253def articulation_points(G):
254    """Yield the articulation points, or cut vertices, of a graph.
255
256    An articulation point or cut vertex is any node whose removal (along with
257    all its incident edges) increases the number of connected components of
258    a graph.  An undirected connected graph without articulation points is
259    biconnected. Articulation points belong to more than one biconnected
260    component of a graph.
261
262    Notice that by convention a dyad is considered a biconnected component.
263
264    Parameters
265    ----------
266    G : NetworkX Graph
267        An undirected graph.
268
269    Yields
270    ------
271    node
272        An articulation point in the graph.
273
274    Raises
275    ------
276    NetworkXNotImplemented
277        If the input graph is not undirected.
278
279    Examples
280    --------
281
282    >>> G = nx.barbell_graph(4, 2)
283    >>> print(nx.is_biconnected(G))
284    False
285    >>> len(list(nx.articulation_points(G)))
286    4
287    >>> G.add_edge(2, 8)
288    >>> print(nx.is_biconnected(G))
289    True
290    >>> len(list(nx.articulation_points(G)))
291    0
292
293    See Also
294    --------
295    is_biconnected
296    biconnected_components
297    biconnected_component_edges
298
299    Notes
300    -----
301    The algorithm to find articulation points and biconnected
302    components is implemented using a non-recursive depth-first-search
303    (DFS) that keeps track of the highest level that back edges reach
304    in the DFS tree.  A node `n` is an articulation point if, and only
305    if, there exists a subtree rooted at `n` such that there is no
306    back edge from any successor of `n` that links to a predecessor of
307    `n` in the DFS tree.  By keeping track of all the edges traversed
308    by the DFS we can obtain the biconnected components because all
309    edges of a bicomponent will be traversed consecutively between
310    articulation points.
311
312    References
313    ----------
314    .. [1] Hopcroft, J.; Tarjan, R. (1973).
315           "Efficient algorithms for graph manipulation".
316           Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
317
318    """
319    seen = set()
320    for articulation in _biconnected_dfs(G, components=False):
321        if articulation not in seen:
322            seen.add(articulation)
323            yield articulation
324
325
326@not_implemented_for("directed")
327def _biconnected_dfs(G, components=True):
328    # depth-first search algorithm to generate articulation points
329    # and biconnected components
330    visited = set()
331    for start in G:
332        if start in visited:
333            continue
334        discovery = {start: 0}  # time of first discovery of node during search
335        low = {start: 0}
336        root_children = 0
337        visited.add(start)
338        edge_stack = []
339        stack = [(start, start, iter(G[start]))]
340        while stack:
341            grandparent, parent, children = stack[-1]
342            try:
343                child = next(children)
344                if grandparent == child:
345                    continue
346                if child in visited:
347                    if discovery[child] <= discovery[parent]:  # back edge
348                        low[parent] = min(low[parent], discovery[child])
349                        if components:
350                            edge_stack.append((parent, child))
351                else:
352                    low[child] = discovery[child] = len(discovery)
353                    visited.add(child)
354                    stack.append((parent, child, iter(G[child])))
355                    if components:
356                        edge_stack.append((parent, child))
357            except StopIteration:
358                stack.pop()
359                if len(stack) > 1:
360                    if low[parent] >= discovery[grandparent]:
361                        if components:
362                            ind = edge_stack.index((grandparent, parent))
363                            yield edge_stack[ind:]
364                            edge_stack = edge_stack[:ind]
365                        else:
366                            yield grandparent
367                    low[grandparent] = min(low[parent], low[grandparent])
368                elif stack:  # length 1 so grandparent is root
369                    root_children += 1
370                    if components:
371                        ind = edge_stack.index((grandparent, parent))
372                        yield edge_stack[ind:]
373        if not components:
374            # root node is articulation point if it has more than 1 child
375            if root_children > 1:
376                yield start
377