A biconnected component of a graph is a connected subgraph that cannot be broken into disconnected pieces by deleting any single node (and its incident links). An articulation point is a node of a graph whose removal would cause an increase in the number of connected components. Articulation points can be important when you analyze any graph that represents a communications network. Consider an articulation point which, if removed, disconnects the graph into two components and . All paths in G between some nodes in and some nodes in must pass through node i. In this sense, articulation points are critical to communication. Examples of where articulation points are important are airline hubs, electric circuits, network wires, protein bonds, traffic routers, and numerous other industrial applications.
In PROC OPTGRAPH, you can find biconnected components and articulation points of an input graph by invoking the BICONCOMP statement. This algorithm works only with undirected graphs.
The results for the biconnected components algorithm are written to the output links data set that is specified in the OUT_LINKS=
option in the PROC OPTGRAPH statement. For each link in the links data set, the variable biconcomp
identifies its component. The component identifiers are numbered sequentially starting from 1. The results for the articulation
points are written to the output nodes data set that is specified in the OUT_NODES= option in the PROC OPTGRAPH statement.
For each node in the nodes data set, the variable artpoint
is either 1 (if the node is an articulation point) or 0 (otherwise).
The biconnected components algorithm reports status information in a macro variable called _OPTGRAPH_BICONCOMP_. See the section Macro Variable _OPTGRAPH_BICONCOMP_ for more information about this macro variable.
The algorithm that PROC OPTGRAPH uses to compute biconnected components is a variant of depth-first search (Tarjan 1972). This algorithm runs in time and therefore should scale to very large graphs.
This section illustrates the use of the biconnected components algorithm on the simple undirected graph G that is shown in Figure 1.17.
Figure 1.17: A Simple Undirected Graph G
The undirected graph G can be represented by the following links data set LinkSetInBiCC
:
data LinkSetInBiCC; input from $ to $ @@; datalines; A B A F A G B C B D B E C D E F G I G H H I ;
The following statements calculate the biconnected components and articulation points and output the results in the data sets
LinkSetOut
and NodeSetOut
:
proc optgraph data_links = LinkSetInBiCC out_links = LinkSetOut out_nodes = NodeSetOut; biconcomp; run;
The data set LinkSetOut
now contains the biconnected components of the input graph, as shown in Figure 1.18.
Figure 1.18: Biconnected Components of a Simple Undirected Graph
In addition, the data set NodeSetOut
contains the articulation points of the input graph, as shown in Figure 1.19.
Figure 1.19: Articulation Points of a Simple Undirected Graph
The biconnected components are shown graphically in Figure 1.20 and Figure 1.21.
Figure 1.20: Biconnected Components and
|
|
|
|
|
|
Figure 1.21: Biconnected Components and
|
|
|
|
|
|
For a more detailed example, see Articulation Points in a Terrorist Network.