Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r85571 - trunk/libs/graph/test
From: jewillco_at_[hidden]
Date: 2013-09-05 08:57:15


Author: jewillco
Date: 2013-09-05 08:57:15 EDT (Thu, 05 Sep 2013)
New Revision: 85571
URL: http://svn.boost.org/trac/boost/changeset/85571

Log:
Added new test from potato_research of custom vertex index map in r_c_shortest_paths

Added:
   trunk/libs/graph/test/rcsp_custom_vertex_id.cpp (contents, props changed)
Text files modified:
   trunk/libs/graph/test/Jamfile.v2 | 1
   trunk/libs/graph/test/rcsp_custom_vertex_id.cpp | 109 ++++++++++++++++++++++++++++++++++++++++
   2 files changed, 110 insertions(+), 0 deletions(-)

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 Thu Sep 5 04:28:24 2013 (r85570)
+++ trunk/libs/graph/test/Jamfile.v2 2013-09-05 08:57:15 EDT (Thu, 05 Sep 2013) (r85571)
@@ -104,6 +104,7 @@
         ../../system/build
         : $(PLANAR_INPUT_FILES) ]
     [ run r_c_shortest_paths_test.cpp ]
+ [ run rcsp_custom_vertex_id.cpp ]
     [ run is_straight_line_draw_test.cpp ]
     [ run metric_tsp_approx.cpp : metric_tsp_approx.graph ]
     [ compile dimacs.cpp ]

Added: trunk/libs/graph/test/rcsp_custom_vertex_id.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/test/rcsp_custom_vertex_id.cpp 2013-09-05 08:57:15 EDT (Thu, 05 Sep 2013) (r85571)
@@ -0,0 +1,109 @@
+//=======================================================================
+// Author: Alberto Santini <alberto_at_[hidden]>
+//
+// 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 <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/r_c_shortest_paths.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <vector>
+#include <memory>
+
+using std::vector;
+using std::allocator;
+using namespace boost;
+
+class VertexProperty {
+public:
+ int property1;
+ int property2;
+ int id;
+ VertexProperty() {}
+ VertexProperty(const int property1, const int property2) : property1(property1), property2(property2) {}
+};
+
+class EdgeProperty {
+public:
+ int cost;
+ int id;
+ EdgeProperty() {}
+ EdgeProperty(const int cost) : cost(cost) {}
+};
+
+typedef adjacency_list<listS, listS, bidirectionalS, VertexProperty, EdgeProperty> Graph;
+typedef graph_traits<Graph>::vertex_descriptor Vertex;
+typedef graph_traits<Graph>::edge_descriptor Edge;
+
+class ResourceCont {
+public:
+ int res;
+ ResourceCont(const int res = 5) : res(res) {}
+ bool operator==(const ResourceCont& rc) const { return (res == rc.res); }
+ bool operator<(const ResourceCont& rc) const { return (res > rc.res); }
+};
+
+class LabelExt {
+public:
+ bool operator()(const Graph& g, ResourceCont& rc, const ResourceCont& old_rc, Edge e) const {
+ rc.res = old_rc.res - g[e].cost;
+ return (rc.res > 0);
+ }
+};
+
+class LabelDom {
+public:
+ bool operator()(const ResourceCont& rc1, const ResourceCont& rc2) const {
+ return (rc1 == rc2 || rc1 < rc2);
+ }
+};
+
+int main() {
+ VertexProperty vp1(1, 1);
+ VertexProperty vp2(5, 9);
+ VertexProperty vp3(4, 3);
+ EdgeProperty e12(1);
+ EdgeProperty e23(2);
+
+ Graph g;
+
+ Vertex v1 = add_vertex(g); g[v1] = vp1;
+ Vertex v2 = add_vertex(g); g[v2] = vp2;
+ Vertex v3 = add_vertex(g); g[v3] = vp3;
+
+ add_edge(v1, v2, e12, g);
+ add_edge(v2, v3, e23, g);
+
+ int index = 0;
+ BGL_FORALL_VERTICES(v, g, Graph) {
+ g[v].id = index++;
+ }
+ index = 0;
+ BGL_FORALL_EDGES(e, g, Graph) {
+ g[e].id = index++;
+ }
+
+ typedef vector<vector<Edge> > OptPath;
+ typedef vector<ResourceCont> ParetoOpt;
+
+ OptPath op;
+ ParetoOpt ol;
+
+ r_c_shortest_paths( g,
+ get(&VertexProperty::id, g),
+ get(&EdgeProperty::id, g),
+ v1,
+ v2,
+ op,
+ ol,
+ ResourceCont(5),
+ LabelExt(),
+ LabelDom(),
+ allocator<r_c_shortest_paths_label<Graph, ResourceCont> >(),
+ default_r_c_shortest_paths_visitor());
+
+ return 0;
+}


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