1<HTML> 2<!-- Copyright 2007 Aaron Windsor 3 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) 7 8 --> 9<Head> 10<Title>Boost Graph Library: make_connected</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><tt>make_connected</tt></H1> 19 20<p> 21 22<pre> 23template <typename Graph, typename VertexIndexMap, typename AddEdgeVisitor> 24make_connected(Graph& g, VertexIndexMap vm, AddEdgeVisitor& vis); 25</pre> 26 27<p> 28 29A 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 32input graph connected. The algorithm first identifies all of the 33<a href="./connected_components.html">connected components</a> in the graph, 34then adds edges to connect those components together in a path. For example, if 35a 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 37of one connecting a vertex in <i>A</i> with a vertex in <i>B</i> and one 38connecting a vertex in <i>B</i> with a vertex in <i>C</i>. 39<p> 40The 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 43behavior can be overriden by providing a vistor as the <tt>AddEdgeVisitor</tt> 44parameter. The only requirement for an <tt>AddEdgeVisitor</tt> is that it 45define a member function with the following signature: 46<pre> 47template <typename Graph, typename Vertex> 48void visit_vertex_pair(Vertex u, Vertex v, Graph& g); 49</pre> 50This event point can also be used as a hook to update the underlying edge 51index map automatically as edges are added. See the 52documentation for the <a href="./AddEdgeVisitor.html">AddEdgeVisitor</a> 53concept for more information. 54 55 56<H3>Where Defined</H3> 57 58<P> 59<a href="../../../boost/graph/make_connected.hpp"> 60<TT>boost/graph/make_connected.hpp</TT> 61</a> 62 63<h3>Parameters</h3> 64 65IN/OUT: <tt>Graph& g</tt> 66 67<blockquote> 68An undirected graph. The graph type must be a model of <a 69href="VertexListGraph.html">Vertex List Graph</a>, <a 70href="IncidenceGraph.html">Incidence Graph</a>, and 71a <a href="MutableGraph.html">Mutable Graph</a><br> 72</blockquote> 73 74IN: <tt>VertexIndexMap vm</tt> 75 76<blockquote> 77A <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> 81</blockquote> 82 83IN: <tt>AddEdgeVisitor</tt> 84 85<blockquote> 86A model of <a href="AddEdgeVisitor.html">AddEdgeVisitor 87</a>.<br> 88<b>Default</b>: <tt>default_add_edge_visitor</tt>, a class defines 89<tt>visit_vertex_pair</tt> to dispatch 90its calls to <tt>add_edge</tt>. 91</blockquote> 92 93 94 95<h3>Complexity</h3> 96 97On a graph with <i>n</i> vertices and <i>m</i> edges, <tt>make_connected</tt> 98runs in time <i>O(n + m)</i> 99 100<H3>Example</H3> 101 102<P> 103<a href="../example/make_connected.cpp"> 104<TT>../example/make_connected.cpp</TT> 105</a> 106 107<h3>See Also</h3> 108 109<a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 110 111<br> 112<HR> 113Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com"> 114aaron.windsor@gmail.com</a>) 115</BODY> 116</HTML> 117
