An undirected graph is called connected if each node is reachable from each other node via a path. The graph from Figure 5.18 is connected. The function

bool Is_Connected(graph& G);

tests whether a graph G (regarded as an undirected graph) is connected.

Figure 5.18. A connected graph that is not biconnected

The graph is connected because each node is reachable from each other node. It is not biconnected. Node 2 is an articulation point. If it is removed, there is no path from 1 to 5 any more; then the graph is no longer connected.

Every graph can be transformed into a connected one with a call of

list<edge> Make_Connected(graph& G);

This function returns a list of the edges that have had to be inserted to make the graph connected. Always a minimal number of edges is inserted.

An articulation point (or cut vertex) in an undirected connected graph is a node by whose removal the graph decomposes into several components, that is, it becomes unconnected; if the graph is regarded as a network, it is a “weak spot”, so to say.

An undirected, connected graph is called biconnected if it has no articulation point. This implies that each node is reachable from each other node via at least two disjoint paths; that is why it is “biconnected”. The graph from Figure 5.18 is not biconnected. The function

bool Is_Biconnected(graph& G, node& ap);

tests whether a graph G (regarded as an undirected graph) is biconnected. If it is not, it returns an articulation point in the variable ap.

The function

list<edge> Make_Biconnected(graph& G);

comes in handy to the Bush administration as it secures the US electricity network, which represents a graph, against terrorists. It inserts a minimal number of edges, so that there is no articulation point any more, and returns the inserted edges in a list.

Frequently, one faces the problem to make an isomorphic copy H of a graph G and to work on with this copy (instead of working on with the original graph). Here “isomorphic” means that exactly one node v' of H corresponds to each node v of G and that exactly one edge (v',w') of H corresponds to each original edge (v,w) (with v' and w' being the node corresponding to v and w, respectively).

The function

void CopyGraph(graph& H, graph& G);

creates an isomorphic copy H of the graph G.

Often it is additionally necessary to know the relationships between the nodes and edges of G and H, because one wants to get from a node (edge) of G to the corresponding node (edge) of H (or vice-versa). A call of

void CopyGraph(GRAPH<node, edge>& H, graph& G);

with a parameterized GRAPH whose node and edge information are of type node and edge additionally stores an item for every node and every edge; this item refers to original node and the original edge of G , respectively. Thus, starting from a node v or an edge e of H, the corresponding node and edge of G can be accessed with

node v_in_G = H[v];
edge e_in_G = H[e];

Conversely, to get from the node of G to the corresponding nodes of H, a copy of G has to be created explicitly and the relationships have to be stored during the creation of H, for example, in a node_array:

graph H;
node_array<node> copy_in_H(G);
// copy all nodes of G
node v;
forall_nodes(v, G) 
  copy_in_H[v] = H.new_node(v);
// copy all edges of G
edge e;
forall_edges(e, G)
  H.new_edge(copy_in_H[G.source(e)], copy_in_H[G.target(e)]);

Then, starting from a node v of G, the corresponding node of H can be accessed with

node v_in_H = copy_in_H[v];

Further functions can be found in graph_misc.h that ease the daily work with graph. Here we present a short selection of them:

Is_Simple() tests whether a graph is simple, that is, whether it has no multiedges.

Is_Acyclic() tests whether a graph is cycle-free.

Is_Bipartite() tests whether a graph is bipartite. A graph is called bipartite if the nodes decompose into two subsets A and B such that the source and target node of every edge is contained in a different subset. See also the graph K3,3 from Figure 5.11 for this.

Delete_Loops() deletes all self-loops and returns a list of the nodes that previously exhibited a self-loop.

The remaining functions from graph_misc.h can be found on the corresponding manual page.