NetworkX

Source code for networkx.algorithms.components.biconnected

# -*- coding: utf-8 -*-
"""
Biconnected components and articulation points.
"""
#    Copyright (C) 2011 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
from itertools import chain
import networkx as nx
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>',
                        'Dan Schult <dschult@colgate.edu>',
                        'Aric Hagberg <aric.hagberg@gmail.com>'])
__all__ = ['biconnected_components',
           'biconnected_component_edges',
           'biconnected_component_subgraphs',
           'is_biconnected',
           'articulation_points',
           ]

[docs]def is_biconnected(G): """Return True if the graph is biconnected, False otherwise. A graph is biconnected if, and only if, it cannot be disconnected by removing only one node (and all edges incident on that node). If removing a node increases the number of disconnected components in the graph, that node is called an articulation point, or cut vertex. A biconnected graph has no articulation points. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- biconnected : bool True if the graph is biconnected, False otherwise. Raises ------ NetworkXError : If the input graph is not undirected. Examples -------- >>> G=nx.path_graph(4) >>> print(nx.is_biconnected(G)) False >>> G.add_edge(0,3) >>> print(nx.is_biconnected(G)) True See Also -------- biconnected_components, articulation_points, biconnected_component_edges, biconnected_component_subgraphs Notes ----- The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node `n` is an articulation point if, and only if, there exists a subtree rooted at `n` such that there is no back edge from any successor of `n` that links to a predecessor of `n` in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points. References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 """ bcc = list(biconnected_components(G)) if not bcc: # No bicomponents (it could be an empty graph) return False return len(bcc[0]) == len(G)
[docs]def biconnected_component_edges(G): """Return a generator of lists of edges, one list for each biconnected component of the input graph. Biconnected components are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph. Note that nodes may be part of more than one biconnected component. Those nodes are articulation points, or cut vertices. However, each edge belongs to one, and only one, biconnected component. Notice that by convention a dyad is considered a biconnected component. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- edges : generator Generator of lists of edges, one list for each bicomponent. Raises ------ NetworkXError : If the input graph is not undirected. Examples -------- >>> G = nx.barbell_graph(4,2) >>> print(nx.is_biconnected(G)) False >>> components = nx.biconnected_component_edges(G) >>> G.add_edge(2,8) >>> print(nx.is_biconnected(G)) True >>> components = nx.biconnected_component_edges(G) See Also -------- is_biconnected, biconnected_components, articulation_points, biconnected_component_subgraphs Notes ----- The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node `n` is an articulation point if, and only if, there exists a subtree rooted at `n` such that there is no back edge from any successor of `n` that links to a predecessor of `n` in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points. References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 """ return sorted(_biconnected_dfs(G,components=True), key=len, reverse=True)
[docs]def biconnected_components(G): """Return a generator of sets of nodes, one set for each biconnected component of the graph Biconnected components are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph. Note that nodes may be part of more than one biconnected component. Those nodes are articulation points, or cut vertices. The removal of articulation points will increase the number of connected components of the graph. Notice that by convention a dyad is considered a biconnected component. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- nodes : generator Generator of sets of nodes, one set for each biconnected component. Raises ------ NetworkXError : If the input graph is not undirected. Examples -------- >>> G = nx.barbell_graph(4,2) >>> print(nx.is_biconnected(G)) False >>> components = nx.biconnected_components(G) >>> G.add_edge(2,8) >>> print(nx.is_biconnected(G)) True >>> components = nx.biconnected_components(G) See Also -------- is_biconnected, articulation_points, biconnected_component_edges, biconnected_component_subgraphs Notes ----- The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node `n` is an articulation point if, and only if, there exists a subtree rooted at `n` such that there is no back edge from any successor of `n` that links to a predecessor of `n` in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points. References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 """ bicomponents = (set(chain.from_iterable(comp)) for comp in _biconnected_dfs(G,components=True)) return sorted(bicomponents, key=len, reverse=True)
[docs]def biconnected_component_subgraphs(G): """Return a generator of graphs, one graph for each biconnected component of the input graph. Biconnected components are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph. Note that nodes may be part of more than one biconnected component. Those nodes are articulation points, or cut vertices. The removal of articulation points will increase the number of connected components of the graph. Notice that by convention a dyad is considered a biconnected component. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- graphs : generator Generator of graphs, one graph for each biconnected component. Raises ------ NetworkXError : If the input graph is not undirected. Examples -------- >>> G = nx.barbell_graph(4,2) >>> print(nx.is_biconnected(G)) False >>> subgraphs = nx.biconnected_component_subgraphs(G) See Also -------- is_biconnected, articulation_points, biconnected_component_edges, biconnected_components Notes ----- The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node `n` is an articulation point if, and only if, there exists a subtree rooted at `n` such that there is no back edge from any successor of `n` that links to a predecessor of `n` in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points. Graph, node, and edge attributes are copied to the subgraphs. References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 """ def edge_subgraph(G,edges): # create new graph and copy subgraph into it H = G.__class__() for u,v in edges: H.add_edge(u,v,attr_dict=G[u][v]) for n in H: H.node[n]=G.node[n].copy() H.graph=G.graph.copy() return H return (edge_subgraph(G,edges) for edges in sorted(_biconnected_dfs(G,components=True), key=len, reverse=True))
[docs]def articulation_points(G): """Return a generator of articulation points, or cut vertices, of a graph. An articulation point or cut vertex is any node whose removal (along with all its incident edges) increases the number of connected components of a graph. An undirected connected graph without articulation points is biconnected. Articulation points belong to more than one biconnected component of a graph. Notice that by convention a dyad is considered a biconnected component. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- articulation points : generator generator of nodes Raises ------ NetworkXError : If the input graph is not undirected. Examples -------- >>> G = nx.barbell_graph(4,2) >>> print(nx.is_biconnected(G)) False >>> list(nx.articulation_points(G)) [6, 5, 4, 3] >>> G.add_edge(2,8) >>> print(nx.is_biconnected(G)) True >>> list(nx.articulation_points(G)) [] See Also -------- is_biconnected, biconnected_components, biconnected_component_edges, biconnected_component_subgraphs Notes ----- The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node `n` is an articulation point if, and only if, there exists a subtree rooted at `n` such that there is no back edge from any successor of `n` that links to a predecessor of `n` in the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points. References ---------- .. [1] Hopcroft, J.; Tarjan, R. (1973). "Efficient algorithms for graph manipulation". Communications of the ACM 16: 372–378. doi:10.1145/362248.362272 """ return _biconnected_dfs(G,components=False)
def _biconnected_dfs(G, components=True): # depth-first search algorithm to generate articulation points # and biconnected components if G.is_directed(): raise nx.NetworkXError('Not allowed for directed graph G. ' 'Use UG=G.to_undirected() to create an ' 'undirected graph.') visited = set() for start in G: if start in visited: continue discovery = {start:0} # "time" of first discovery of node during search low = {start:0} root_children = 0 visited.add(start) edge_stack = [] stack = [(start, start, iter(G[start]))] while stack: grandparent, parent, children = stack[-1] try: child = next(children) if grandparent == child: continue if child in visited: if discovery[child] <= discovery[parent]: # back edge low[parent] = min(low[parent],discovery[child]) if components: edge_stack.append((parent,child)) else: low[child] = discovery[child] = len(discovery) visited.add(child) stack.append((parent, child, iter(G[child]))) if components: edge_stack.append((parent,child)) except StopIteration: stack.pop() if len(stack) > 1: if low[parent] >= discovery[grandparent]: if components: ind = edge_stack.index((grandparent,parent)) yield edge_stack[ind:] edge_stack=edge_stack[:ind] else: yield grandparent low[grandparent] = min(low[parent], low[grandparent]) elif stack: # length 1 so grandparent is root root_children += 1 if components: ind = edge_stack.index((grandparent,parent)) yield edge_stack[ind:] if not components: # root node is articulation point if it has more than 1 child if root_children > 1: yield start