`make_connected`

template <typename Graph, typename VertexIndexMap, typename AddEdgeVisitor>
make_connected(Graph& g, VertexIndexMap vm, AddEdgeVisitor& vis);

A undirected graph *G* is connected if, for every pair of vertices
*u,v* in *G*, there is a path from *u* to *v*.
`make_connected` adds the minimum number of edges needed to make the
input graph connected. The algorithm first identifies all of the
connected components in the graph,
then adds edges to connect those components together in a path. For example, if
a graph contains three connected components *A*, *B*, and *C*,
`make_connected` will add two edges. The two edges added might consist
of one connecting a vertex in *A* with a vertex in *B* and one
connecting a vertex in *B* with a vertex in *C*.

The default behavior of `make_connected` is to modify the graph
`g` by calling `add_edge(u,v,g)` for every pair of vertices
*(u,v)* where an edge needs to be added to connect `g`. This
behavior can be overriden by providing a vistor as the `AddEdgeVisitor`
parameter. The only requirement for an `AddEdgeVisitor` is that it
define a member function with the following signature:

template <typename Graph, typename Vertex>
void visit_vertex_pair(Vertex u, Vertex v, Graph& g);

This event point can also be used as a hook to update the underlying edge
index map automatically as edges are added. See the
documentation for the AddEdgeVisitor
concept for more information.
### Where Defined

`boost/graph/make_connected.hpp`

### Parameters

IN/OUT: `Graph& g`
An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and
a Mutable Graph

IN: `VertexIndexMap vm`
A Readable Property Map
that maps vertices from `g` to distinct integers in the range
`[0, num_vertices(g) )`

**Default**: `get(vertex_index,g)`

IN: `AddEdgeVisitor`
A model of AddEdgeVisitor
.

**Default**: `default_add_edge_visitor`, a class defines
`visit_vertex_pair` to dispatch
its calls to `add_edge`.

### Complexity

On a graph with *n* vertices and *m* edges, `make_connected`
runs in time *O(n + m)*
### Example

`../example/make_connected.cpp`

### See Also

Planar Graphs in the Boost Graph Library

Copyright © 2007 Aaron Windsor (
aaron.windsor@gmail.com)