*Leaning objectives*

Algorithms from `graph_misc.h` |

Connected and biconnected graphs |

As the name suggests, the header file * graph_misc.h*
declares several “small-sized” graph algorithms, that is,
quite simple functions that are used again and again in the daily
programming with the class

`graph`

. We have
already discussed the functions `Is_Planar()`

and `Is_Planar_Map()`

therefrom.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.

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.

| How many and which edges have to be inserted
in Figure 5.18 to make the graph
biconnected? Call |