projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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> | |
| 26 | template <typename VertexListGraph, | |
| 27 | typename WeightMap, | |
| 28 | typename VertexIndexMap, | |
| 29 | typename TSPVertexVisitor> | |
| 30 | void 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> | |
| 38 | template<typename VertexListGraph, typename OutputIterator> | |
| 39 | void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o) | |
| 40 | ||
| 41 | template<typename VertexListGraph, typename WeightMap, typename OutputIterator> | |
| 42 | void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, | |
| 43 | OutputIterator o) | |
| 44 | ||
| 45 | template<typename VertexListGraph, typename OutputIterator> | |
| 46 | void metric_tsp_approx_tour_from_vertex(VertexListGraph& g, | |
| 47 | typename graph_traits<VertexListGraph>::vertex_descriptor start, | |
| 48 | OutputIterator o) | |
| 49 | ||
| 50 | template<typename VertexListGraph, typename WeightMap, | |
| 51 | typename OutputIterator> | |
| 52 | void 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> | |
| 57 | template<typename VertexListGraph, typename TSPVertexVisitor> | |
| 58 | void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis) | |
| 59 | ||
| 60 | template<typename VertexListGraph, typename Weightmap, | |
| 61 | typename VertexIndexMap, typename TSPVertexVisitor> | |
| 62 | void metric_tsp_approx(VertexListGraph& g, Weightmap w, | |
| 63 | TSPVertexVisitor vis) | |
| 64 | ||
| 65 | template<typename VertexListGraph, typename WeightMap, | |
| 66 | typename VertexIndexMap, typename TSPVertexVisitor> | |
| 67 | void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id, | |
| 68 | TSPVertexVisitor vis) | |
| 69 | ||
| 70 | template<typename VertexListGraph, typename WeightMap, | |
| 71 | typename TSPVertexVisitor> | |
| 72 | void 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> | |
| 79 | This is a traveling salesperson heuristic for generating a tour of vertices | |
| 80 | for a fully connected undirected graph with weighted edges that obey the triangle inequality. | |
| 81 | The current implementation is based off of the algorithm presented in <i>Introduction to Algorithms</i> | |
| 82 | on page 1029. This implementation generates solutions that are twice as long as the optimal tour in the worst case. | |
| 83 | The pseudo-code is listed below. | |
| 84 | </p> | |
| 85 | ||
| 86 | <table> | |
| 87 | <tr> | |
| 88 | <td valign="top"> | |
| 89 | <pre> | |
| 90 | TSP-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 | ||
| 111 | IN: <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 | ||
| 118 | IN: <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 | ||
| 124 | IN: <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 | ||
| 134 | IN: <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 | ||
| 151 | OUT: <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 | ||
| 158 | OUT: <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> | |
| 171 | The time complexity is <i>O(E log V)</i>. | |
| 172 | ||
| 173 | <P> | |
| 174 | ||
| 175 | <H3>Example</H3> | |
| 176 | ||
| 177 | <P> | |
| 178 | The file <a | |
| 179 | href="../test/metric_tsp_approx.cpp"><TT>test/metric_tsp_approx.cpp</TT></a> | |
| 180 | contains 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> | |
| 200 | Matyas Egyhazy | |
| 201 | </TD></TR></TABLE> | |
| 202 | ||
| 203 | </BODY> | |
| 204 | </HTML> |