1<HTML> 2<!-- 3 Copyright (c) Matyas Egyhazy 2008 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: Metric Traveling Salesperson Approximation</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 19 20<H1><A NAME="sec:metric_tsp_approx"></A> 21<TT>metric_tsp_approx</TT> 22</H1> 23 24<P> 25<PRE> 26template <typename VertexListGraph, 27 typename WeightMap, 28 typename VertexIndexMap, 29 typename TSPVertexVisitor> 30void metric_tsp_approx_from_vertex( 31 const VertexListGraph& g, 32 typename graph_traits<VertexListGraph>::vertex_descriptor start, 33 WeightMap weightmap, 34 VertexIndexMap indexmap, 35 TSPVertexVisitor vis) 36 37<i>// Overloads</i> 38template<typename VertexListGraph, typename OutputIterator> 39void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o) 40 41template<typename VertexListGraph, typename WeightMap, typename OutputIterator> 42void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, 43 OutputIterator o) 44 45template<typename VertexListGraph, typename OutputIterator> 46void metric_tsp_approx_tour_from_vertex(VertexListGraph& g, 47 typename graph_traits<VertexListGraph>::vertex_descriptor start, 48 OutputIterator o) 49 50template<typename VertexListGraph, typename WeightMap, 51 typename OutputIterator> 52void metric_tsp_approx_tour_from_vertex(VertexListGraph& g, 53 typename graph_traits<VertexListGraph>::vertex_descriptor start, 54 WeightMap w, OutputIterator o) 55 56<i>// visitor versions</i> 57template<typename VertexListGraph, typename TSPVertexVisitor> 58void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis) 59 60template<typename VertexListGraph, typename Weightmap, 61 typename VertexIndexMap, typename TSPVertexVisitor> 62void metric_tsp_approx(VertexListGraph& g, Weightmap w, 63 TSPVertexVisitor vis) 64 65template<typename VertexListGraph, typename WeightMap, 66 typename VertexIndexMap, typename TSPVertexVisitor> 67void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id, 68 TSPVertexVisitor vis) 69 70template<typename VertexListGraph, typename WeightMap, 71 typename TSPVertexVisitor> 72void metric_tsp_approx_from_vertex(VertexListGraph& g, 73 typename graph_traits<VertexListGraph>::vertex_descriptor start, 74 WeightMap w, TSPVertexVisitor vis) 75 76</PRE> 77 78<P> 79This is a traveling salesperson heuristic for generating a tour of vertices 80for a fully connected undirected graph with weighted edges that obey the triangle inequality. 81The current implementation is based off of the algorithm presented in <i>Introduction to Algorithms</i> 82on page 1029. This implementation generates solutions that are twice as long as the optimal tour in the worst case. 83The pseudo-code is listed below. 84</p> 85 86<table> 87<tr> 88<td valign="top"> 89<pre> 90TSP-APPROX(<i>G</i>, <i>w</i>) 91 select a vertex <i>r</i> <i>in</i> <i>V[G]</i> 92 compute a minimum spanning tree <i>T</i> for <i>G</i> from root <i>r</i> 93 using PRIM-MST(<i>G</i>, <i>r</i>, <i>w</i>) 94 let <i>L</i> be the list of vertices visited in a preorder traversal of <i>T</i> 95 <b>return</b> (the Hamiltonian cycle <i>H</i> that visites the vertices in the order <i>L</i>) 96</pre> 97</td> 98</tr> 99</table> 100 101 102<H3>Where Defined</H3> 103 104<P> 105<a href="../../../boost/graph/metric_tsp_approx.hpp"><TT>boost/graph/metric_tsp_approx.hpp</TT></a> 106 107<P> 108 109<h3>Parameters</h3> 110 111IN: <tt>const Graph& g</tt> 112<blockquote> 113 An undirected graph. The type <tt>Graph</tt> must be a 114 model of <a href="./VertexListGraph.html">Vertex List Graph</a> 115 and <a href="./IncidenceGraph.html">Incidence Graph</a> <a href="#2">[2]</a>.<br> 116</blockquote> 117 118IN: <tt>vertex_descriptor start</tt> 119<blockquote> 120 The vertex that will be the start (and end) of the tour.<br> 121 <b>Default:</b> <tt>*vertices(g).first</tt> 122</blockquote> 123 124IN: <tt>WeightMap weightmap</tt> 125<blockquote> 126 The weight of each edge in the graph. 127 The type <tt>WeightMap</tt> must be a model of 128 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of 129 the graph needs to be usable as the key type for the weight 130 map.<br> 131 <b>Default:</b> <tt>get(edge_weight, g)</tt><br> 132</blockquote> 133 134IN: <tt>VertexIndexMap indexmap</tt> 135<blockquote> 136 This maps each vertex to an integer in the range <tt>[0, 137 num_vertices(g))</tt>. This is necessary for efficient updates of the 138 heap data structure when an edge is relaxed. The type 139 <tt>VertexIndexMap</tt> must be a model of 140 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an 141 integer type. The vertex descriptor type of the graph needs to be 142 usable as the key type of the map.<br> 143 <b>Default:</b> <tt>get(vertex_index, g)</tt> 144 Note: if you use this default, make sure your graph has 145 an internal <tt>vertex_index</tt> property. For example, 146 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 147 not have an internal <tt>vertex_index</tt> property. 148 <br> 149</blockquote> 150 151OUT: <tt>OutputIterator o</tt> 152<blockquote> 153 The OutputIterator holds the vertices of the tour. 154 The type <tt>OutputIterator</tt> must be a model of the 155 OutputIterator concept. 156</blockquote> 157 158OUT: <tt>TSPTourVisitor vis</tt> 159<blockquote> 160 Use this to specify actions that you would like to happen 161 when the algorithm visits a vertex of the tour. 162 The type <tt>TSPTourVisitor</tt> must be a model of the <a href="./TSPTourVisitor.html">TSP Tour Visitor</a> 163 concept. 164 The visitor object is passed by value <a 165 href="#1">[1]</a>.<br> 166</blockquote> 167 168<H3>Complexity</H3> 169 170<P> 171The time complexity is <i>O(E log V)</i>. 172 173<P> 174 175<H3>Example</H3> 176 177<P> 178The file <a 179href="../test/metric_tsp_approx.cpp"><TT>test/metric_tsp_approx.cpp</TT></a> 180contains an example of using this TSP approximation algorithm. 181 182 183<h3>Notes</h3> 184 185<p><a name="1">[1]</a> 186 Since the visitor parameter is passed by value, if your visitor 187 contains state then any changes to the state during the algorithm 188 will be made to a copy of the visitor object, not the visitor object 189 passed in. Therefore you may want the visitor to hold this state by 190 pointer or reference. 191</p> 192<p><a name="2">[2]</a> 193 Passing an <tt>adjacency_list</tt> with a vertex <em>not</em> set selected by 194 <tt>vecS</tt> will result in <i>O(n<sup>2</sup>)</i> performance. 195</p> 196<HR> 197<TABLE> 198<TR valign=top> 199<TD nowrap>Copyright © 2008</TD><TD> 200Matyas Egyhazy 201</TD></TR></TABLE> 202 203</BODY> 204</HTML> 205
