|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49561 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: asutton_at_[hidden]
Date: 2008-11-03 10:35:59
Author: asutton
Date: 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
New Revision: 49561
URL: http://svn.boost.org/trac/boost/changeset/49561
Log:
Added metric_tsp_approx by Matt Egahazy. Import includes the algorithm,
documentation and tests. Integrated the test into the unit tests, and
the documentation into the TOC under a new subsection named Paths and Tours.
Also added a new bad_graph exception in exception.hpp.
Added:
trunk/boost/graph/metric_tsp_approx.hpp (contents, props changed)
trunk/libs/graph/doc/TSPTourVisitor.html (contents, props changed)
trunk/libs/graph/doc/metric_tsp_approx.html (contents, props changed)
trunk/libs/graph/doc/tsp_tour_len_visitor.html (contents, props changed)
trunk/libs/graph/doc/tsp_tour_visitor.html (contents, props changed)
trunk/libs/graph/test/metric_tsp_approx.cpp (contents, props changed)
trunk/libs/graph/test/metric_tsp_approx.txt (contents, props changed)
Text files modified:
trunk/boost/graph/exception.hpp | 57 ++++++++++++--------
trunk/libs/graph/doc/table_of_contents.html | 108 +++++++++++++++++++++------------------
trunk/libs/graph/test/Jamfile.v2 | 60 +++++++---------------
3 files changed, 111 insertions(+), 114 deletions(-)
Modified: trunk/boost/graph/exception.hpp
==============================================================================
--- trunk/boost/graph/exception.hpp (original)
+++ trunk/boost/graph/exception.hpp 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -15,29 +15,40 @@
namespace boost {
- struct bad_graph : public std::invalid_argument {
- bad_graph(const std::string& what_arg)
- : std::invalid_argument(what_arg) { }
- };
-
- struct not_a_dag : public bad_graph {
- not_a_dag()
- : bad_graph("The graph must be a DAG.") { }
- };
-
- struct negative_edge : public bad_graph {
- negative_edge()
- : bad_graph("The graph may not contain an edge with negative weight."){ }
- };
-
- struct negative_cycle : public bad_graph {
- negative_cycle()
- : bad_graph("The graph may not contain negative cycles.") { }
- };
- struct not_connected : public bad_graph {
- not_connected()
- : bad_graph("The graph must be connected.") { }
- };
+ struct bad_graph : public std::invalid_argument {
+ bad_graph(const std::string& what_arg)
+ : std::invalid_argument(what_arg) { }
+ };
+
+ struct not_a_dag : public bad_graph {
+ not_a_dag()
+ : bad_graph("The graph must be a DAG.")
+ { }
+ };
+
+ struct negative_edge : public bad_graph {
+ negative_edge()
+ : bad_graph("The graph may not contain an edge with negative weight.")
+ { }
+ };
+
+ struct negative_cycle : public bad_graph {
+ negative_cycle()
+ : bad_graph("The graph may not contain negative cycles.")
+ { }
+ };
+
+ struct not_connected : public bad_graph {
+ not_connected()
+ : bad_graph("The graph must be connected.")
+ { }
+ };
+
+ struct not_complete : public bad_graph {
+ not_complete()
+ : bad_graph("The graph must be complete.")
+ { }
+ };
} // namespace boost
Added: trunk/boost/graph/metric_tsp_approx.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/metric_tsp_approx.hpp 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,313 @@
+
+//=======================================================================
+// Copyright 2008
+// Author: Matyas W Egyhazy
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_GRAPH_METRIC_TSP_APPROX_HPP
+#define BOOST_GRAPH_METRIC_TSP_APPROX_HPP
+
+// metric_tsp_approx
+// Generates an approximate tour solution for the traveling salesperson
+// problem in polynomial time. The current algorithm guarantees a tour with a
+// length at most as long as 2x optimal solution. The graph should have
+// 'natural' (metric) weights such that the triangle inequality is maintained.
+// Graphs must be fully interconnected.
+
+// TODO:
+// There are a couple of improvements that could be made.
+// 1) Change implementation to lower uppper bound Christofides heuristic
+// 2) Implement a less restrictive TSP heuristic (one that does not rely on
+// triangle inequality).
+// 3) Determine if the algorithm can be implemented without creating a new
+// graph.
+
+#include <vector>
+
+#include <boost/shared_ptr.hpp>
+#include <boost/concept_check.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_as_tree.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/prim_minimum_spanning_tree.hpp>
+
+
+namespace boost
+{
+ // Define a concept for the concept-checking library.
+ template <typename Visitor, typename Graph>
+ struct TSPVertexVisitorConcept
+ {
+ private:
+ Visitor vis_;
+ public:
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept)
+ {
+ Visitor vis(vis_); // require copy construction
+ Graph g(1);
+ Vertex v(*vertices(g).first);
+ vis_.visit_vertex(v, g); // require visit_vertex
+ }
+ };
+
+ // Tree visitor that keeps track of a preorder traversal of a tree
+ // TODO: Consider migrating this to the graph_as_tree header.
+ // TODO: Parameterize the underlying stores o it doesn't have to be a vector.
+ template<typename Node, typename Tree> class PreorderTraverser
+ {
+ private:
+ std::vector<Node>& path_;
+ public:
+ typedef typename std::vector<Node>::const_iterator const_iterator;
+
+ PreorderTraverser(std::vector<Node>& p) : path_(p) {}
+
+ void preorder(Node n, const Tree& t)
+ { path_.push_back(n); }
+
+ void inorder(Node n, const Tree& t) const {}
+ void postorder(Node, const Tree& t) const {}
+
+ const_iterator begin() const { return path_.begin(); }
+ const_iterator end() const { return path_.end(); }
+ };
+
+ // Forward declarations
+ template <typename> class tsp_tour_visitor;
+ template <typename, typename, typename, typename> class tsp_tour_len_visitor;
+
+ template<typename VertexListGraph, typename OutputIterator>
+ void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o)
+ {
+ metric_tsp_approx_from_vertex(g, *vertices(g).first,
+ get(edge_weight, g), get(vertex_index, g),
+ tsp_tour_visitor<OutputIterator>(o));
+ }
+
+ template<typename VertexListGraph, typename WeightMap, typename OutputIterator>
+ void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o)
+ {
+ metric_tsp_approx_from_vertex(g, *vertices(g).first,
+ w, tsp_tour_visitor<OutputIterator>(o));
+ }
+
+ template<typename VertexListGraph, typename OutputIterator>
+ void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ OutputIterator o)
+ {
+ metric_tsp_approx_from_vertex(g, start, get(edge_weight, g),
+ get(vertex_index, g), tsp_tour_visitor<OutputIterator>(o));
+ }
+
+ template<typename VertexListGraph, typename WeightMap,
+ typename OutputIterator>
+ void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap w, OutputIterator o)
+ {
+ metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g),
+ tsp_tour_visitor<OutputIterator>(o));
+ }
+
+ template<typename VertexListGraph, typename TSPVertexVisitor>
+ void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)
+ {
+ metric_tsp_approx_from_vertex(g, *vertices(g).first,
+ get(edge_weight, g), get(vertex_index, g), vis);
+ }
+
+ template<typename VertexListGraph, typename Weightmap,
+ typename VertexIndexMap, typename TSPVertexVisitor>
+ void metric_tsp_approx(VertexListGraph& g, Weightmap w,
+ TSPVertexVisitor vis)
+ {
+ metric_tsp_approx_from_vertex(g, *vertices(g).first, w,
+ get(vertex_index, g), vis);
+ }
+
+ template<typename VertexListGraph, typename WeightMap,
+ typename VertexIndexMap, typename TSPVertexVisitor>
+ void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id,
+ TSPVertexVisitor vis)
+ {
+ metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis);
+ }
+
+ template<typename VertexListGraph, typename WeightMap,
+ typename TSPVertexVisitor>
+ void metric_tsp_approx_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap w, TSPVertexVisitor vis)
+ {
+ metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), vis);
+ }
+
+ template <
+ typename VertexListGraph,
+ typename WeightMap,
+ typename VertexIndexMap,
+ typename TSPVertexVisitor>
+ void metric_tsp_approx_from_vertex(const VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap weightmap,
+ VertexIndexMap indexmap,
+ TSPVertexVisitor vis)
+ {
+ using namespace boost;
+ using namespace std;
+
+ BOOST_CONCEPT_ASSERT((VertexListGraphConcept<VertexListGraph>));
+ BOOST_CONCEPT_ASSERT((TSPVertexVisitorConcept<TSPVertexVisitor, VertexListGraph>));
+
+ // Types related to the input graph (GVertex is a template parameter).
+ typedef typename graph_traits<VertexListGraph>::vertex_descriptor GVertex;
+ typedef typename graph_traits<VertexListGraph>::vertex_iterator GVItr;
+
+ // We build a custom graph in this algorithm.
+ typedef adjacency_list <vecS, vecS, directedS, no_property, no_property > MSTImpl;
+ typedef graph_traits<MSTImpl>::edge_descriptor Edge;
+ typedef graph_traits<MSTImpl>::vertex_descriptor Vertex;
+ typedef graph_traits<MSTImpl>::vertex_iterator VItr;
+
+ // And then re-cast it as a tree.
+ typedef iterator_property_map<vector<Vertex>::iterator, property_map<MSTImpl, vertex_index_t>::type> ParentMap;
+ typedef graph_as_tree<MSTImpl, ParentMap> Tree;
+ typedef tree_traits<Tree>::node_descriptor Node;
+
+ // A predecessor map.
+ typedef vector<GVertex> PredMap;
+ typedef iterator_property_map<typename PredMap::iterator, VertexIndexMap> PredPMap;
+
+ PredMap preds(num_vertices(g));
+ PredPMap pred_pmap(preds.begin(), indexmap);
+
+ // Compute a spanning tree over the in put g.
+ prim_minimum_spanning_tree(g, pred_pmap,
+ root_vertex(start)
+ .vertex_index_map(indexmap)
+ .weight_map(weightmap));
+
+ // Build a MST using the predecessor map from prim mst
+ MSTImpl mst(num_vertices(g));
+ std::size_t cnt = 0;
+ pair<VItr, VItr> mst_verts(vertices(mst));
+ for(typename PredMap::iterator vi(preds.begin()); vi != preds.end(); ++vi, ++cnt)
+ {
+ if(indexmap[*vi] != cnt) {
+ add_edge(*next(mst_verts.first, indexmap[*vi]),
+ *next(mst_verts.first, cnt), mst);
+ }
+ }
+
+ // Build a tree abstraction over the MST.
+ vector<Vertex> parent(num_vertices(mst));
+ Tree t(mst, *vertices(mst).first,
+ make_iterator_property_map(parent.begin(),
+ get(vertex_index, mst)));
+
+ // Create tour using a preorder traversal of the mst
+ vector<Node> tour;
+ PreorderTraverser<Node, Tree> tvis(tour);
+ traverse_tree(0, t, tvis);
+
+ pair<GVItr, GVItr> g_verts(vertices(g));
+ for(PreorderTraverser<Node, Tree>::const_iterator curr(tvis.begin());
+ curr != tvis.end(); ++curr)
+ {
+ // TODO: This is will be O(n^2) if vertex storage of g != vecS.
+ GVertex v = *next(g_verts.first, get(vertex_index, mst)[*curr]);
+ vis.visit_vertex(v, g);
+ }
+
+ // Connect back to the start of the tour
+ vis.visit_vertex(*g_verts.first, g);
+ }
+
+ // Default tsp tour visitor that puts the tour in an OutputIterator
+ template <typename OutItr>
+ class tsp_tour_visitor
+ {
+ OutItr itr_;
+ public:
+ tsp_tour_visitor(OutItr itr)
+ : itr_(itr)
+ { }
+
+ template <typename Vertex, typename Graph>
+ void visit_vertex(Vertex v, const Graph& g)
+ {
+ BOOST_CONCEPT_ASSERT((OutputIterator<OutItr, Vertex>));
+ *itr_++ = v;
+ }
+
+ };
+
+ // Tsp tour visitor that adds the total tour length.
+ template<typename Graph, typename WeightMap, typename OutIter, typename Length>
+ class tsp_tour_len_visitor
+ {
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ BOOST_CONCEPT_ASSERT((OutputIterator<OutIter, Vertex>));
+
+ OutIter iter_;
+ Length& tourlen_;
+ WeightMap& wmap_;
+ Vertex previous_;
+
+ // Helper function for getting the null vertex.
+ Vertex null()
+ { return graph_traits<Graph>::null_vertex(); }
+
+ public:
+ tsp_tour_len_visitor(Graph const&, OutIter iter, Length& l, WeightMap map)
+ : iter_(iter), tourlen_(l), wmap_(map), previous_(null())
+ { }
+
+ void visit_vertex(Vertex v, const Graph& g)
+ {
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ // If it is not the start, then there is a
+ // previous vertex
+ if(previous_ != null())
+ {
+ // NOTE: For non-adjacency matrix graphs g, this bit of code
+ // will be linear in the degree of previous_ or v. A better
+ // solution would be to visit edges of the graph, but that
+ // would require revisiting the core algorithm.
+ Edge e;
+ bool found;
+ tie(e, found) = edge(previous_, v, g);
+ if(!found) {
+ throw not_complete();
+ }
+
+ tourlen_ += wmap_[e];
+ }
+
+ previous_ = v;
+ *iter_++ = v;
+ }
+ };
+
+ // Object generator(s)
+ template <typename OutIter>
+ inline tsp_tour_visitor<OutIter>
+ make_tsp_tour_visitor(OutIter iter)
+ { return tsp_tour_visitor<OutIter>(iter); }
+
+ template <typename Graph, typename WeightMap, typename OutIter, typename Length>
+ inline tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length>
+ make_tsp_tour_len_visitor(Graph const& g, OutIter iter, Length& l, WeightMap map)
+ { return tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length>(g, iter, l, map); }
+
+} //boost
+
+#endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP
\ No newline at end of file
Added: trunk/libs/graph/doc/TSPTourVisitor.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/TSPTourVisitor.html 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,99 @@
+<HTML>
+<!--
+ Copyright (c) Matyas Egyhazy 2008
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+ -->
+<Head>
+<Title>Boost Graph Library: TSP Tour Visitor</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1>TSP Tour Visitor concept</H1>
+
+This concept defines the visitor interface for <a
+href="./metric_tsp_approx.html"><tt>metric_tsp_approx()</tt></a>
+and related algorithms. The user can create a class that matches this
+interface, and then pass objects of the class into
+<tt>metric_tsp_approx()</tt> to augment the actions taken during
+the search.
+
+<h3>Refinement of</h3>
+
+none
+
+<h3>Notation</h3>
+
+<Table>
+<TR>
+<TD><tt>V</tt></TD>
+<TD>A type that is a model of Dijkstra Visitor.</TD>
+</TR>
+
+<TR>
+<TD><tt>vis</tt></TD>
+<TD>An object of type <tt>V</tt>.</TD>
+</TR>
+
+<TR>
+<TD><tt>G</tt></TD>
+<TD>A type that is a model of Graph.</TD>
+</TR>
+
+<TR>
+<TD><tt>g</tt></TD>
+<TD>An object of type <tt>G</tt>.</TD>
+</TR>
+
+<TR>
+<TD><tt>v</tt></TD>
+<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
+</TR>
+
+</table>
+
+<h3>Associated Types</h3>
+
+none
+
+<p>
+
+<h3>Valid Expressions</h3>
+
+<table border>
+<tr>
+<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
+</tr>
+
+<tr>
+<td>Visit Vertex</td>
+<td><tt>vis.visit_vertex(v, g)</tt></td>
+<td><tt>void</tt></td>
+<td>
+This is invoked on each vertex of the graph when it is visited as part of the TSP tour.
+</td>
+</tr>
+
+</table>
+
+<h3>Models</h3>
+
+<ul>
+ <li>tsp_tour_visitor
+ <li>tsp_tour_len_tsp_visitor
+</ul>
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2008</TD><TD>
+Matyas Egyhazy</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Added: trunk/libs/graph/doc/metric_tsp_approx.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/metric_tsp_approx.html 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,204 @@
+<HTML>
+<!--
+ -- Copyright (c) Matyas Egyhazy 2008
+ --
+ -- Distributed under the Boost Software License, Version 1.0.
+ -- (See accompanying file LICENSE_1_0.txt or copy at
+ -- http://www.boost.org/LICENSE_1_0.txt)
+ -->
+<Head>
+<Title>Boost Graph Library: Metric Traveling Salesperson Approximation</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+
+
+<H1><A NAME="sec:metric_tsp_approx"></A>
+<TT>metric_tsp_approx</TT>
+</H1>
+
+<P>
+<PRE>
+template <typename VertexListGraph,
+ typename WeightMap,
+ typename VertexIndexMap,
+ typename TSPVertexVisitor>
+void metric_tsp_approx_from_vertex(
+ const VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap weightmap,
+ VertexIndexMap indexmap,
+ TSPVertexVisitor vis)
+
+<i>// Overloads</i>
+template<typename VertexListGraph, typename OutputIterator>
+void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o)
+
+template<typename VertexListGraph, typename WeightMap, typename OutputIterator>
+void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w,
+ OutputIterator o)
+
+template<typename VertexListGraph, typename OutputIterator>
+void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ OutputIterator o)
+
+template<typename VertexListGraph, typename WeightMap,
+ typename OutputIterator>
+void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap w, OutputIterator o)
+
+<i>// visitor versions</i>
+template<typename VertexListGraph, typename TSPVertexVisitor>
+void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)
+
+template<typename VertexListGraph, typename Weightmap,
+ typename VertexIndexMap, typename TSPVertexVisitor>
+void metric_tsp_approx(VertexListGraph& g, Weightmap w,
+ TSPVertexVisitor vis)
+
+template<typename VertexListGraph, typename WeightMap,
+ typename VertexIndexMap, typename TSPVertexVisitor>
+void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id,
+ TSPVertexVisitor vis)
+
+template<typename VertexListGraph, typename WeightMap,
+ typename TSPVertexVisitor>
+void metric_tsp_approx_from_vertex(VertexListGraph& g,
+ typename graph_traits<VertexListGraph>::vertex_descriptor start,
+ WeightMap w, TSPVertexVisitor vis)
+
+</PRE>
+
+<P>
+This is a traveling salesperson heuristic for generating a tour of vertices
+for a fully connected undirected graph with weighted edges that obey the triangle inequality.
+The current implementation is based off of the algorithm presented in <i>Introduction to Algorithms</i>
+on page 1029. This implementation generates solutions that are twice as long as the optimal tour in the worst case.
+The pseudo-code is listed below.
+</p>
+
+<table>
+<tr>
+<td valign="top">
+<pre>
+TSP-APPROX(<i>G</i>, <i>w</i>)
+ select a vertex <i>r</i> <i>in</i> <i>V[G]</i>
+ compute a minimum spanning tree <i>T</i> for <i>G</i> from root <i>r</i>
+ using PRIM-MST(<i>G</i>, <i>r</i>, <i>w</i>)
+ let <i>L</i> be the list of vertices visited in a preorder traversal of <i>T</i>
+ <b>return</b> (the Hamiltonian cycle <i>H</i> that visites the vertices in the order <i>L</i>)
+</pre>
+</td>
+</tr>
+</table>
+
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/metric_tsp_approx.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph& g</tt>
+<blockquote>
+ An undirected graph. The type <tt>Graph</tt> must be a
+ model of Vertex List Graph
+ and Incidence Graph [2].<br>
+</blockquote>
+
+IN: <tt>vertex_descriptor start</tt>
+<blockquote>
+ The vertex that will be the start (and end) of the tour.<br>
+ <b>Default:</b> <tt>*vertices(g).first</tt>
+</blockquote>
+
+IN: <tt>WeightMap weightmap</tt>
+<blockquote>
+ The weight of each edge in the graph.
+ The type <tt>WeightMap</tt> must be a model of
+ Readable Property Map. The edge descriptor type of
+ the graph needs to be usable as the key type for the weight
+ map.<br>
+ <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+</blockquote>
+
+IN: <tt>VertexIndexMap indexmap</tt>
+<blockquote>
+ This maps each vertex to an integer in the range <tt>[0,
+ num_vertices(g))</tt>. This is necessary for efficient updates of the
+ heap data structure when an edge is relaxed. The type
+ <tt>VertexIndexMap</tt> must be a model of
+ Readable Property Map. The value type of the map must be an
+ integer type. The vertex descriptor type of the graph needs to be
+ usable as the key type of the map.<br>
+ <b>Default:</b> <tt>get(vertex_index, g)</tt>
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+ <br>
+</blockquote>
+
+OUT: <tt>OutputIterator o</tt>
+<blockquote>
+ The OutputIterator holds the vertices of the tour.
+ The type <tt>OutputIterator</tt> must be a model of the
+ OutputIterator concept.
+</blockquote>
+
+OUT: <tt>TSPTourVisitor vis</tt>
+<blockquote>
+ Use this to specify actions that you would like to happen
+ when the algorithm visits a vertex of the tour.
+ The type <tt>TSPTourVisitor</tt> must be a model of the TSP Tour Visitor
+ concept.
+ The visitor object is passed by value <a
+ href="#1">[1]</a>.<br>
+</blockquote>
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(E log V)</i>.
+
+<P>
+
+<H3>Example</H3>
+
+<P>
+The file <a
+href="../example/metric_tsp_approx_example.cpp"><TT>examples/metric_tsp_approx_example.cpp</TT></a>
+contains an example of using this TSP approximation algorithm.
+
+
+<h3>Notes</h3>
+
+<p><a name="1">[1]</a>
+ Since the visitor parameter is passed by value, if your visitor
+ contains state then any changes to the state during the algorithm
+ will be made to a copy of the visitor object, not the visitor object
+ passed in. Therefore you may want the visitor to hold this state by
+ pointer or reference.
+</p>
+<p><a name="2">[2]</a>
+ Passing an <tt>adjacency_list</tt> with a vertex <em>not</em> set selected by
+ <tt>vecS</tt> will result in <i>O(n<sup>2</sup>)</i> performance.
+</p>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2008</TD><TD>
+Matyas Egyhazy
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -8,10 +8,10 @@
-->
<Head>
<Title>Table of Contents: Boost Graph Library</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
<BR Clear>
@@ -70,25 +70,28 @@
<LI>DFS Visitor
<LI>Dijkstra Visitor
<LI>Bellman Ford Visitor
- <LI>A* Visitor</LI>
+ <LI>A* Visitor</LI>
<LI>Event Visitor
- <LI>Planar Face Visitor
+ <LI>Planar Face Visitor
+ <li>TSP Tour Visitor</li>
</OL>
<li>EventVisitorList Adaptors
<OL>
- <LI>Event Visitor List
- <LI>bfs_visitor
- <LI>dfs_visitor
- <LI>dijkstra_visitor
- <LI>bellman_visitor
- <li>astar_visitor</li>
+ <LI>Event Visitor List
+ <LI>bfs_visitor
+ <LI>dfs_visitor
+ <LI>dijkstra_visitor
+ <LI>bellman_visitor
+ <li>astar_visitor</li>
</OL>
<li>Event Visitors
<OL>
- <LI>predecessor_recorder
- <LI>distance_recorder
- <LI>time_stamper
- <LI>property_writer
+ <LI>predecessor_recorder
+ <LI>distance_recorder
+ <LI>time_stamper
+ <LI>property_writer
+ <li>tsp_tour_visitor</li>
+ <li>tsp_tour_len_visitor</li>
</OL>
<LI>Graph classes
<OL>
@@ -152,28 +155,28 @@
<LI><A
href="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></A>
</OL>
- <LI>Connected Components Algorithms
- <OL>
- <LI>connected_components
- <LI>strong_components
-
- <LI>biconnected_components
- <LI>articulation_points
- <LI>Incremental Connected Components
- <OL>
- <LI>initialize_incremental_components
- <LI>incremental_components
- <LI><A
- href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A>
- <LI>component_index
- </OL>
- </OL></LI>
+ <LI>Connected Components Algorithms
+ <OL>
+ <LI>connected_components
+ <LI>strong_components
+
+ <LI>biconnected_components
+ <LI>articulation_points
+ <LI>Incremental Connected Components
+ <OL>
+ <LI>initialize_incremental_components
+ <LI>incremental_components
+ <LI><A
+ href="./incremental_components.html#sec:same-component"><tt>same_component</tt></A>
+ <LI>component_index
+ </OL>
+ </OL></LI>
<LI>Maximum Flow and Matching Algorithms
<OL>
<LI>edmunds_karp_max_flow
<LI>push_relabel_max_flow
<li>kolmogorov_max_flow</li>
- <LI>edmonds_maximum_cardinality_matching
+ <LI>edmonds_maximum_cardinality_matching
</OL>
<li>Sparse Matrix Ordering Algorithms
@@ -184,34 +187,39 @@
<LI>minimum_degree_ordering
</ol>
</li>
- <LI>topological_sort
- <li>transitive_closure
- <LI>copy_graph
- <LI>transpose_graph
- <LI>isomorphism
-
- <LI><A
- href="sequential_vertex_coloring.html"><tt>sequential_vertex_coloring</tt></A>
- <li>sloan_ordering</li>
+ <LI>topological_sort
+ <li>transitive_closure
+ <LI>copy_graph
+ <LI>transpose_graph
+ <LI>isomorphism
+
+ <li>Path and Tour Algorithms
+ <ol>
+ <li>metric_tsp_approx</li>
+ </ol>
+ </li>
+
+ <LI>sequential_vertex_coloring
+ <li>sloan_ordering</li>
<li>sloan_start_end_vertices</li>
<LI>ith_wavefront, max_wavefront, aver_wavefront, and rms_wavefront</LI>
<LI>brandes_betweenness_centrality</LI>
<li>Layout algorithms
<ol>
- <li>random_graph_layout</li>
+ <li>random_graph_layout</li>
<li>circle_layout</li>
<li>kamada_kawai_spring_layout</li>
- <li>fruchterman_reingold_force_directed_layout</li>
+ <li>fruchterman_reingold_force_directed_layout</li>
<li>gursoy_atun_layout</li>
- </ol>
- </li>
+ </ol>
+ </li>
<li>Clustering algorithms
- <ol>
+ <ol>
<li>betweenness_centrality_clustering</li>
- </ol>
+ </ol>
</li>
- <li>astar_search</li>
+ <li>astar_search</li>
<li>lengauer_tarjan_dominator_tree</li>
<li>minimum_cycle_ratio and maximum_cycle_ratio</li>
<li>Planar Graph Algorithms
@@ -293,4 +301,4 @@
</TD></TR></TABLE>
</BODY>
-</HTML>
+</HTML>
Added: trunk/libs/graph/doc/tsp_tour_len_visitor.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/tsp_tour_len_visitor.html 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,123 @@
+<HTML>
+<!--
+ Copyright (c) Matyas Egyhazy 2008
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+ -->
+<Head>
+<Title>Boost Graph Library: tsp_tour_len_visitor</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1>
+<pre>
+tsp_tour_len_visitor<Graph, WeightMap, OutputIterator, Length>
+</pre>
+</H1>
+
+This type is a TSP tour visitor. It supplies the OutputIterator with the vertices of the tour and
+records the total length of the tour.
+
+<h3>Example</h3>
+
+<pre>
+double d(0.0);
+std::vector<Vertex> c;
+boost::metric_tsp_approx
+ (g, get(edge_weight, g),
+ make_tsp_tour_len_visitor(g, std::back_inserter(c), d, get(edge_weight, g)));
+</pre>
+
+
+<h3>Model of</h3>
+
+TSP Tour Visitor
+
+<H3>Template Parameters</H3>
+
+<P>
+<TABLE border>
+<TR>
+<th>Parameter</th><th>Description</th><th>Default</th>
+</tr>
+
+<TR><TD><TT>Graph</TT></TD>
+<TD>
+The graph type
+</TD>
+<TD>None</TD>
+</TR>
+
+<TR><TD><TT>WeightMap</TT></TD>
+<TD>
+The weight of each edge in the graph.
+The type <tt>WeightMap</tt> must be a model of
+Readable Property Map.
+The edge descriptor type of the graph needs to be usable as the key type for the weight map.
+</TD>
+<TD>None</TD>
+</TR>
+
+<TR><TD><TT>OutputIterator</TT></TD>
+<TD>
+An OutputIterator
+</TD>
+<TD>None</TD>
+</TR>
+
+<TR><TD><TT>Length</TT></TD>
+<TD>
+A suitable container for the length of the tour. It must implement additive operators.
+</TD>
+<TD>None</TD>
+</TR>
+
+</table>
+
+<H3>Where Defined</H3>
+
+<P>
+<a href="../../../boost/graph/metric_tsp_approx.hpp">
+<TT>boost/graph/metric_tsp_approx.hpp</TT></a>
+
+<h3>Member Functions</h3>
+
+This class implements all of the member functions required by <a
+href="./TSPTourVisitor.html">TSPTourVisitor</a>.
+
+<h3>Non-Member Functions</h3>
+
+<table border>
+<tr>
+<th>Function</th><th>Description</th>
+</tr>
+
+<tr><td><tt>
+template <typename Graph, typename WeightMap, typename OutputIterator, typename Length><br>
+tsp_tour_len_visitor<OutputIterator><br>
+make_tsp_tour_len_visitor(Graph const& g, OutIter iter, Length& l, WeightMap map)
+</tt></td><td>
+Returns a tour_len_visitor that records the TSP tour in the OutputIterator parameter and the tour's length in the Length parameter.
+</td></tr>
+
+</table>
+
+<h3>See Also</h3>
+
+None
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2008</TD><TD>
+Matyas Egyhazy
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Added: trunk/libs/graph/doc/tsp_tour_visitor.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/tsp_tour_visitor.html 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,96 @@
+<HTML>
+<!--
+ Copyright (c) Matyas Egyhazy 2008
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+ -->
+<Head>
+<Title>Boost Graph Library: tsp_tour_visitor</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1>
+<pre>
+tsp_tour_visitor<OutputIterator>
+</pre>
+</H1>
+
+This type is a simple TSP tour visitor. It supplies the OutputIterator with the vertices of the tour.
+
+<h3>Example</h3>
+
+<pre>
+std::vector<Vertex> c;
+boost::metric_tsp_approx
+ (g, get(edge_weight, g), make_tsp_tour_visitor(std::back_inserter(c));
+</pre>
+
+
+<h3>Model of</h3>
+
+TSP Tour Visitor
+
+<H3>Template Parameters</H3>
+
+<P>
+<TABLE border>
+<TR>
+<th>Parameter</th><th>Description</th><th>Default</th>
+</tr>
+
+<TR><TD><TT>OutputIterator</TT></TD>
+<TD>
+An OutputIterator
+</TD>
+<TD>None</TD>
+</TR>
+
+</table>
+
+<H3>Where Defined</H3>
+
+<P>
+<a href="../../../boost/graph/metric_tsp_approx.hpp">
+<TT>boost/graph/metric_tsp_approx.hpp</TT></a>
+
+<h3>Member Functions</h3>
+
+This class implements all of the member functions required by <a
+href="./TSPTourVisitor.html">TSPTourVisitor</a>.
+
+<h3>Non-Member Functions</h3>
+
+<table border>
+<tr>
+<th>Function</th><th>Description</th>
+</tr>
+
+<tr><td><tt>
+template <typename OutputIterator><br>
+tsp_tour_visitor<OutputIterator><br>
+make_tsp_tour_visitor(OutputIterator iter)
+</tt></td><td>
+Returns a simple tsp_tour_visitor that records the TSP tour in the OutputIterator parameter
+</td></tr>
+
+</table>
+
+<h3>See Also</h3>
+
+None
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2008</TD><TD>
+Matyas Egyhazy
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -4,7 +4,7 @@
# (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)
-# Define SGB (stanford graph base top level directory) and
+# Define SGB (stanford graph base top level directory) and
# LEDA (also top level directory) at the command line of jam using -s
import modules ;
@@ -20,66 +20,44 @@
optional_tests += [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ] ;
}
-test-suite graph_test :
+test-suite graph_test :
[ run transitive_closure_test.cpp ]
-
[ compile adj_list_cc.cpp ]
# adj_list_test needs some work -JGS
# unit-test adj_list_test : adj_list_test.cpp ;
[ run adj_list_edge_list_set.cpp ]
-
[ compile adj_matrix_cc.cpp ]
-
[ run bfs.cpp ../../test/build//boost_test_exec_monitor ]
-
[ compile bfs_cc.cpp ]
-
[ run bellman-test.cpp ]
-
- [ run betweenness_centrality_test.cpp ]
-
+ [ run betweenness_centrality_test.cpp ]
[ run bidir_remove_edge.cpp ]
-
[ run csr_graph_test.cpp : : : : : <variant>release ]
-
[ run dag_longest_paths.cpp ]
-
[ run dfs.cpp ../../test/build//boost_test_exec_monitor ]
-
[ compile dfs_cc.cpp ]
-
[ compile dijkstra_cc.cpp ]
-
[ run dijkstra_heap_performance.cpp : 10000 ]
-
[ run dominator_tree_test.cpp ]
-
[ run relaxed_heap_test.cpp : 5000 15000 ]
-
[ compile edge_list_cc.cpp ]
-
[ compile filtered_graph_cc.cpp ]
-
[ run graph.cpp ]
-
[ compile graph_concepts.cpp ]
-
- [ run graphviz_test.cpp
- /boost/test//boost_test_exec_monitor/<link>static
+ [ run graphviz_test.cpp
+ /boost/test//boost_test_exec_monitor/<link>static
../build//boost_graph ]
-
[ run gursoy_atun_layout_test.cpp ]
-
[ run layout_test.cpp : : : <test-info>always_show_run_output <toolset>intel:<debug-symbols>off ]
- [ run serialize.cpp
+ [ run serialize.cpp
../../serialization/build//boost_serialization
: : : ]
- [ compile reverse_graph_cc.cpp ]
+ [ compile reverse_graph_cc.cpp ]
[ run sequential_vertex_coloring.cpp ]
@@ -87,13 +65,13 @@
[ run isomorphism.cpp ../../test/build//boost_test_exec_monitor ]
- [ run adjacency_matrix_test.cpp ]
+ [ run adjacency_matrix_test.cpp ]
[ compile vector_graph_cc.cpp ]
[ compile copy.cpp ]
-
- [ compile property_iter.cpp ]
+
+ [ compile property_iter.cpp ]
[ run bundled_properties.cpp ]
@@ -125,19 +103,19 @@
[ run named_vertices_test.cpp ]
- [ run all_planar_input_files_test.cpp
- ../../filesystem/build
+ [ run all_planar_input_files_test.cpp
+ ../../filesystem/build
../../system/build
: $(PLANAR_INPUT_FILES) ]
- [ run parallel_edges_loops_test.cpp
- ../../filesystem/build
+ [ run parallel_edges_loops_test.cpp
+ ../../filesystem/build
../../system/build
: $(PLANAR_INPUT_FILES) ]
[ run r_c_shortest_paths_test.cpp ]
-
[ run is_straight_line_draw_test.cpp ]
+ [ run metric_tsp_approx.cpp : metric_tsp_approx.txt ]
$(optional_tests)
;
@@ -148,18 +126,18 @@
local SDB_DEPENDCIES =
<include>$(SGB) <library-file>$(SGB)/libgb.a ;
- compile stanford_graph_cc.cpp
+ compile stanford_graph_cc.cpp
$(SDB_DEPENDCIES) ;
}
# Run LEDA tests only when -sLEDA= is set.
if [ modules.peek : LEDA ] != ""
{
- local LEDA_DEPENDENCIES =
- <include>$(LEDA)/incl
+ local LEDA_DEPENDENCIES =
+ <include>$(LEDA)/incl
<library-file>$(LEDA)/libG.a
;
- compile leda_graph_cc.cpp
+ compile leda_graph_cc.cpp
$(LEDA_DEPENDENCIES) ;
}
Added: trunk/libs/graph/test/metric_tsp_approx.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/metric_tsp_approx.cpp 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,319 @@
+//=======================================================================
+// Copyright 2008
+// Author: Matyas W Egyhazy
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#include <iostream>
+#include <vector>
+#include <fstream>
+#include <set>
+#include <ctime>
+
+#include <boost/assert.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/random.hpp>
+#include <boost/timer.hpp>
+#include <boost/integer_traits.hpp>
+#include <boost/graph/adjacency_matrix.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/simple_point.hpp>
+#include <boost/graph/metric_tsp_approx.hpp>
+#include <boost/graph/graphviz.hpp>
+
+template<typename PointType>
+struct cmpPnt
+{
+ bool operator()(const boost::simple_point<PointType>& l,
+ const boost::simple_point<PointType>& r) const
+ { return (l.x > r.x); }
+};
+
+//add edges to the graph (for each node connect it to all other nodes)
+template<typename VertexListGraph, typename PointContainer,
+ typename WeightMap, typename VertexIndexMap>
+void connectAllEuclidean(VertexListGraph& g,
+ const PointContainer& points,
+ WeightMap wmap, // Property maps passed by value
+ VertexIndexMap vmap, // Property maps passed by value
+ int sz)
+{
+ using namespace boost;
+ using namespace std;
+ typedef typename graph_traits<VertexListGraph>::edge_descriptor Edge;
+ typedef typename graph_traits<VertexListGraph>::vertex_iterator VItr;
+
+ Edge e;
+ bool inserted;
+
+ pair<VItr, VItr> verts(vertices(g));
+ for (VItr src(verts.first); src != verts.second; src++)
+ {
+ for (VItr dest(src); dest != verts.second; dest++)
+ {
+ if (dest != src)
+ {
+ double weight(sqrt(pow(
+ static_cast<double>(points[vmap[*src]].x -
+ points[vmap[*dest]].x), 2.0) +
+ pow(static_cast<double>(points[vmap[*dest]].y -
+ points[vmap[*src]].y), 2.0)));
+
+ tie(e, inserted) = add_edge(*src, *dest, g);
+
+ wmap[e] = weight;
+ }
+
+ }
+
+ }
+}
+
+// Create a randomly generated point
+// scatter time execution
+void testScalability(unsigned numpts)
+{
+ using namespace boost;
+ using namespace std;
+
+ typedef adjacency_matrix<undirectedS, no_property,
+ property <edge_weight_t, double,
+ property<edge_index_t, int> > > Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits <Graph>::edge_descriptor Edge;
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ typedef set<simple_point<double>, cmpPnt<double> > PointSet;
+ typedef vector< Vertex > Container;
+
+ mt19937 rng(time(0));
+ uniform_int<> range(0.01, (numpts * 2));
+ variate_generator<mt19937&, uniform_int<> >
+ pnt_gen(rng, range);
+
+ PointSet points;
+ simple_point<double> pnt;
+
+ while (points.size() < numpts)
+ {
+ pnt.x = pnt_gen();
+ pnt.y = pnt_gen();
+ points.insert(pnt);
+ }
+
+ Graph g(numpts);
+ WeightMap weight_map(get(edge_weight, g));
+ vector<simple_point<double> > point_vec(points.begin(), points.end());
+
+ connectAllEuclidean(g, point_vec, weight_map, get(vertex_index, g), numpts);
+
+ Container c;
+ timer t;
+ double len = 0.0;
+
+ // Run the TSP approx, creating the visitor on the fly.
+ metric_tsp_approx(g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map));
+
+ cout << "Number of points: " << num_vertices(g) << endl;
+ cout << "Number of edges: " << num_edges(g) << endl;
+ cout << "Length of tour: " << len << endl;
+ cout << "Elapsed: " << t.elapsed() << endl;
+}
+
+template <typename PositionVec>
+void checkAdjList(PositionVec v)
+{
+ using namespace std;
+ using namespace boost;
+
+ typedef adjacency_list<listS, listS, undirectedS> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits <Graph>::edge_descriptor Edge;
+ typedef vector<Vertex> Container;
+ typedef map<Vertex, std::size_t> VertexIndexMap;
+ typedef map<Edge, double> EdgeWeightMap;
+ typedef associative_property_map<VertexIndexMap> VPropertyMap;
+ typedef associative_property_map<EdgeWeightMap> EWeightPropertyMap;
+ typedef graph_traits<Graph>::vertex_iterator VItr;
+
+ Container c;
+ EdgeWeightMap w_map;
+ VertexIndexMap v_map;
+ VPropertyMap v_pmap(v_map);
+ EWeightPropertyMap w_pmap(w_map);
+
+ Graph g(v.size());
+
+ //create vertex index map
+ VItr vi, ve;
+ int idx(0);
+ for (tie(vi, ve) = vertices(g); vi != ve; ++vi)
+ {
+ Vertex v(*vi);
+ v_pmap[v] = idx;
+ idx++;
+ }
+
+ connectAllEuclidean(g, v, w_pmap,
+ v_pmap, v.size());
+
+ metric_tsp_approx_from_vertex(g,
+ *vertices(g).first,
+ w_pmap,
+ v_pmap,
+ tsp_tour_visitor<back_insert_iterator<Container > >
+ (back_inserter(c)));
+
+ cout << "adj_list" << endl;
+ for (Container::iterator itr = c.begin(); itr != c.end(); ++itr) {
+ cout << v_map[*itr] << " ";
+ }
+ cout << endl << endl;
+
+ c.clear();
+}
+
+static void usage()
+{
+ using namespace std;
+ cerr << "To run this program properly please place a "
+ << "file called graph.txt"
+ << endl << "into the current working directory." << endl
+ << "Each line of this file should be a coordinate specifying the"
+ << endl << "location of a vertex" << endl
+ << "For example: " << endl << "1,2" << endl << "20,4" << endl
+ << "15,7" << endl << endl;
+}
+
+int main(int argc, char* argv[])
+{
+ using namespace boost;
+ using namespace std;
+
+ typedef vector<simple_point<double> > PositionVec;
+ typedef adjacency_matrix<undirectedS, no_property,
+ property <edge_weight_t, double> > Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef graph_traits <Graph>::edge_descriptor Edge;
+ typedef vector<Vertex> Container;
+ typedef property_map<Graph, edge_weight_t>::type WeightMap;
+ typedef property_map<Graph, vertex_index_t>::type VertexMap;
+
+ // Make sure that the the we can parse the given file.
+ if(argc < 2) {
+ usage();
+ return -1;
+ }
+
+ // Open the graph file, failing if one isn't given on the command line.
+ ifstream fin(argv[1]);
+ if (!fin)
+ {
+ usage();
+ return -1;
+ }
+
+ string line;
+ PositionVec position_vec;
+
+ int n(0);
+ while (getline(fin, line))
+ {
+ simple_point<double> vertex;
+
+ size_t idx(line.find(","));
+ string xStr(line.substr(0, idx));
+ string yStr(line.substr(idx + 1, line.size() - idx));
+
+ vertex.x = lexical_cast<double>(xStr);
+ vertex.y = lexical_cast<double>(yStr);
+
+ position_vec.push_back(vertex);
+ n++;
+ }
+
+ fin.close();
+
+ Container c;
+ Graph g(position_vec.size());
+ WeightMap weight_map(get(edge_weight, g));
+ VertexMap v_map = get(vertex_index, g);
+
+ connectAllEuclidean(g, position_vec, weight_map, v_map, n);
+
+ metric_tsp_approx_tour(g, back_inserter(c));
+
+ for (vector<Vertex>::iterator itr = c.begin(); itr != c.end(); ++itr)
+ {
+ cout << *itr << " ";
+ }
+ cout << endl << endl;
+
+ c.clear();
+
+ checkAdjList(position_vec);
+
+ metric_tsp_approx_from_vertex(g, *vertices(g).first,
+ get(edge_weight, g), get(vertex_index, g),
+ tsp_tour_visitor<back_insert_iterator<vector<Vertex> > >
+ (back_inserter(c)));
+
+ for (vector<Vertex>::iterator itr = c.begin(); itr != c.end(); ++itr)
+ {
+ cout << *itr << " ";
+ }
+ cout << endl << endl;
+
+ c.clear();
+
+ double len(0.0);
+ try {
+ metric_tsp_approx(g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map));
+ }
+ catch (const bad_graph& e) {
+ cerr << "bad_graph: " << e.what() << endl;
+ return -1;
+ }
+
+ cout << "Number of points: " << num_vertices(g) << endl;
+ cout << "Number of edges: " << num_edges(g) << endl;
+ cout << "Length of Tour: " << len << endl;
+
+ int cnt(0);
+ pair<Vertex,Vertex> triangleEdge;
+ for (vector<Vertex>::iterator itr = c.begin(); itr != c.end();
+ ++itr, ++cnt)
+ {
+ cout << *itr << " ";
+
+ if (cnt == 2)
+ {
+ triangleEdge.first = *itr;
+ }
+ if (cnt == 3)
+ {
+ triangleEdge.second = *itr;
+ }
+ }
+ cout << endl << endl;
+ c.clear();
+
+ testScalability(1000);
+
+ // if the graph is not fully connected then some of the
+ // assumed triangle-inequality edges may not exist
+ remove_edge(edge(triangleEdge.first, triangleEdge.second, g).first, g);
+
+ // Make sure that we can actually trap incomplete graphs.
+ bool caught = false;
+ try {
+ double len = 0.0;
+ metric_tsp_approx(g, make_tsp_tour_len_visitor(g, back_inserter(c), len, weight_map));
+ }
+ catch (const bad_graph& e) { caught = true; }
+ BOOST_ASSERT(caught);
+
+ return 0;
+}
Added: trunk/libs/graph/test/metric_tsp_approx.txt
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/metric_tsp_approx.txt 2008-11-03 10:35:58 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,8 @@
+2,5
+2,3
+1,2
+4,5
+5,4
+4,3
+6,3
+3,1
\ No newline at end of file
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk