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);

Where Defined

boost/graph/make_connected.hpp

Parameters

An undirected graph. The graph type must be a model of Vertex List Graph, Incidence Graph, and a Mutable Graph

A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g) )
Default: get(vertex_index,g)

A model of AddEdgeVisitor .
Default: default_add_edge_visitor, a class defines visit_vertex_pair to dispatch its calls to add_edge.

Complexity

Example

../example/make_connected.cpp

See Also