### 5.3.1. Algorithms for basic properties

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.

#### Connected and biconnected graphs

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.

#### Copying graphs

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

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.

#### Further information

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

#### Exercises

 Exercise 63. How many and which edges have to be inserted in Figure 5.18 to make the graph biconnected? Call `Make_Biconnected()` to insert the edges and visualize the result with a GraphWin.