Components

We've seen in the section, ``Graph Subgraph Creation'', that the Graph member function induced_graph can be used to create general subgraphs of a given Graph. The following two algorithms define Graph connected components, that is, subgraphs in which each Vertex is reachable from every other Vertex via some sequence of Edges:

       // version for directed Graphs
       Set<Graph> strong_conn_comps(const Graph& g);
   

       // version for undirected Graphs
       Set<Graph> conn_comps_u(const Graph& g);

Given a Vertex v as a root Vertex, each of the traversals for undirected Graphs discussed in the section, ``Traversals'', that is not terminated by a user-defined function defines the connected component containing that Vertex. strong_conn_comps and conn_comps_u define all such connected components in g, returning a Set<Graph> representing the set of connected components identified. The two algorithms differ only in that strong_conn_comps uses the direction on each Edge to determine reachability while conn_comps_u does not.

Articulation points in an undirected Graph are those Vertices which, when removed, break the current connected component down into new connected components:

       // only for undirected Graphs
       Set_of_p<Vertex> artic_pts(const Graph& g);
       Set_of_p<Vertex> artic_pts(const Graph& g,
           const Set_of_p<Vertex>& vpset);

Given an undirected Graph g, artic_pts(g) finds all Vertices which are articulation points over all of the connected components in g. Given a vpset which contains the Vertices in a connected component of an undirected Graph g, artic_pts(g, vpset) finds all Vertices which are articulation points in that connected component.

artic_pts is very useful in network applications where connectivity after node failure or removal is being inspected. For instance, departing from our manufacturing example for a moment, suppose that we have created an undirected Graph representing a communications network and wish to identify those locations which, if disabled, would result in communication isolation for other locations. An undirected Graph is appropriate for applications where the connectivity is symmetric, as is usually true of communication networks. If our undirected Graph is a Network n and our nodes are Nodes, we can use conn_comps_u and artic_pts in tandem as follows:

       .
       .
       .
       Setiter<Network> si (conn_comps_u(n));
           // identifies the set of connected components
           // in the Network
       Network new_n;
       while (new_n = si.next()) { // get the next
                                   // connected component
           Set_of_p<Node> nset =
               artic_pts(n, new_n.vertices());
               // retrieve the articulation points of new_n
           .
           .
           .
           // some processing on nset
           }
       .
       .
       .

nset will, at each iteration, contain those Nodes whose failure or removal will cause communication loss in the associated component new_n.

Now that we have seen examples of the use of both directed and undirected Graphs, a general note: there are instances where a directed or undirected graph needs no user data on the edges. Rather, the physical adjacency of the vertices suffices to define the relation. Such graphs are quite common in theoretical applications such as binary trees.