2 <!-- Copyright 2007 Aaron Windsor
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
10 <Title>Boost Graph Library: make_connected
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><tt>make_connected
</tt></H1>
23 template
<typename Graph, typename VertexIndexMap, typename AddEdgeVisitor
>
24 make_connected(Graph& g, VertexIndexMap vm, AddEdgeVisitor& vis);
29 A undirected graph
<i>G
</i> is connected if, for every pair of vertices
30 <i>u,v
</i> in
<i>G
</i>, there is a path from
<i>u
</i> to
<i>v
</i>.
31 <tt>make_connected
</tt> adds the minimum number of edges needed to make the
32 input graph connected. The algorithm first identifies all of the
33 <a href=
"./connected_components.html">connected components
</a> in the graph,
34 then adds edges to connect those components together in a path. For example, if
35 a graph contains three connected components
<i>A
</i>,
<i>B
</i>, and
<i>C
</i>,
36 <tt>make_connected
</tt> will add two edges. The two edges added might consist
37 of one connecting a vertex in
<i>A
</i> with a vertex in
<i>B
</i> and one
38 connecting a vertex in
<i>B
</i> with a vertex in
<i>C
</i>.
40 The default behavior of
<tt>make_connected
</tt> is to modify the graph
41 <tt>g
</tt> by calling
<tt>add_edge(u,v,g)
</tt> for every pair of vertices
42 <i>(u,v)
</i> where an edge needs to be added to connect
<tt>g
</tt>. This
43 behavior can be overriden by providing a vistor as the
<tt>AddEdgeVisitor
</tt>
44 parameter. The only requirement for an
<tt>AddEdgeVisitor
</tt> is that it
45 define a member function with the following signature:
47 template
<typename Graph, typename Vertex
>
48 void visit_vertex_pair(Vertex u, Vertex v, Graph& g);
50 This event point can also be used as a hook to update the underlying edge
51 index map automatically as edges are added. See the
52 documentation for the
<a href=
"./AddEdgeVisitor.html">AddEdgeVisitor
</a>
53 concept for more information.
56 <H3>Where Defined
</H3>
59 <a href=
"../../../boost/graph/make_connected.hpp">
60 <TT>boost/graph/make_connected.hpp
</TT>
65 IN/OUT:
<tt>Graph
& g
</tt>
68 An undirected graph. The graph type must be a model of
<a
69 href=
"VertexListGraph.html">Vertex List Graph
</a>,
<a
70 href=
"IncidenceGraph.html">Incidence Graph
</a>, and
71 a
<a href=
"MutableGraph.html">Mutable Graph
</a><br>
74 IN:
<tt>VertexIndexMap vm
</tt>
77 A
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property Map
78 </a> that maps vertices from
<tt>g
</tt> to distinct integers in the range
79 <tt>[
0, num_vertices(g) )
</tt><br>
80 <b>Default
</b>:
<tt>get(vertex_index,g)
</tt><br>
83 IN:
<tt>AddEdgeVisitor
</tt>
86 A model of
<a href=
"AddEdgeVisitor.html">AddEdgeVisitor
88 <b>Default
</b>:
<tt>default_add_edge_visitor
</tt>, a class defines
89 <tt>visit_vertex_pair
</tt> to dispatch
90 its calls to
<tt>add_edge
</tt>.
97 On a graph with
<i>n
</i> vertices and
<i>m
</i> edges,
<tt>make_connected
</tt>
98 runs in time
<i>O(n + m)
</i>
103 <a href=
"../example/make_connected.cpp">
104 <TT>../example/make_connected.cpp
</TT>
109 <a href=
"planar_graphs.html">Planar Graphs in the Boost Graph Library
</a>
113 Copyright
© 2007 Aaron Windsor (
<a href=
"mailto:aaron.windsor@gmail.com">
114 aaron.windsor@gmail.com
</a>)