[Boost-commit] svn:boost r85661 - in trunk/libs/graph: example test

Subject: [Boost-commit] svn:boost r85661 - in trunk/libs/graph: example test
From: jewillco_at_[hidden]
Date: 2013-09-13 10:48:17

Author: jewillco
Date: 2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)
New Revision: 85661
URL: http://svn.boost.org/trac/boost/changeset/85661

Log:
Attached patch from Piotr Wygocki for min-cost max-flow

Text files modified: 
   trunk/libs/graph/example/cycle_canceling_example.cpp                              |     6 ++--                                    
   trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp |     6 ++--                                    
   trunk/libs/graph/test/cycle_canceling_test.cpp                                    |    17 ++++++++-------                         
   trunk/libs/graph/test/min_cost_max_flow_utils.hpp                                 |    41 ++++++++++++++++++++------------------- 
   trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp       |    17 ++++++++-------                         
   5 files changed, 45 insertions(+), 42 deletions(-)

Modified: trunk/libs/graph/example/cycle_canceling_example.cpp
==============================================================================
--- trunk/libs/graph/example/cycle_canceling_example.cpp	Thu Sep 12 18:00:51 2013	(r85660)
+++ trunk/libs/graph/example/cycle_canceling_example.cpp	2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)	(r85661)
@@ -14,9 +14,9 @@
 
 
 int main() {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g;
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     boost::edmonds_karp_max_flow(g, s, t);
     boost::cycle_canceling(g);

Modified: trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp
==============================================================================
--- trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp	Thu Sep 12 18:00:51 2013	(r85660)
+++ trunk/libs/graph/example/successive_shortest_path_nonnegative_weights_example.cpp	2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)	(r85661)
@@ -14,9 +14,9 @@
 
 
 int main() {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g; 
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     boost::successive_shortest_path_nonnegative_weights(g, s, t);
 

Modified: trunk/libs/graph/test/cycle_canceling_test.cpp
==============================================================================
--- trunk/libs/graph/test/cycle_canceling_test.cpp	Thu Sep 12 18:00:51 2013	(r85660)
+++ trunk/libs/graph/test/cycle_canceling_test.cpp	2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)	(r85661)
@@ -18,9 +18,9 @@
 
 
 BOOST_AUTO_TEST_CASE(cycle_canceling_def_test) {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g;
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     boost::edmonds_karp_max_flow(g, s, t);
     boost::cycle_canceling(g);
@@ -30,9 +30,9 @@
 }
 
 BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph2(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g; 
+    boost::SampleGraph::getSampleGraph2(g, s, t);
 
     boost::edmonds_karp_max_flow(g, s, t);
     boost::cycle_canceling(g);
@@ -42,9 +42,10 @@
 }
 
 BOOST_AUTO_TEST_CASE(cycle_canceling_test) {
-    unsigned s,t;
+    boost::SampleGraph::vertex_descriptor s,t;
     typedef boost::SampleGraph::Graph Graph;
-    Graph g = boost::SampleGraph::getSampleGraph(s, t);
+    boost::SampleGraph::Graph g; 
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     int N = num_vertices(g);
     std::vector<int> dist(N);

Modified: trunk/libs/graph/test/min_cost_max_flow_utils.hpp
==============================================================================
--- trunk/libs/graph/test/min_cost_max_flow_utils.hpp	Thu Sep 12 18:00:51 2013	(r85660)
+++ trunk/libs/graph/test/min_cost_max_flow_utils.hpp	2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)	(r85661)
@@ -19,7 +19,7 @@
 struct SampleGraph {
     typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
 
-    typedef adjacency_list < listS, vecS, directedS, no_property,
+    typedef adjacency_list < vecS, vecS, directedS, no_property,
             property < edge_capacity_t, long,
                 property < edge_residual_capacity_t, long,
                     property < edge_reverse_t, Traits::edge_descriptor, 
@@ -30,14 +30,15 @@
     typedef property_map < Graph, edge_capacity_t >::type Capacity;
     typedef property_map < Graph, edge_residual_capacity_t >::type ResidualCapacity;
     typedef property_map < Graph, edge_weight_t >::type Weight;
+    typedef property_map < Graph, edge_reverse_t>::type Reversed;
+    typedef boost::graph_traits<Graph>::vertices_size_type size_type;
+    typedef Traits::vertex_descriptor vertex_descriptor;
     
-
-    template <typename Graph, typename Weight, typename Capacity, typename Reversed, typename ResidualCapacity>
     class EdgeAdder {
     public:
         EdgeAdder(Graph & g, Weight & w, Capacity & c, Reversed & rev, ResidualCapacity & residualCapacity) 
             : m_g(g), m_w(w), m_cap(c), m_resCap(residualCapacity), m_rev(rev) {}
-        void addEdge(int v, int w, int weight, int capacity) {
+        void addEdge(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
             Traits::edge_descriptor e,f;
             e = add(v, w, weight, capacity);
             f = add(w, v, -weight, 0);
@@ -45,7 +46,7 @@
             m_rev[f] = e; 
         }
     private:
-        Traits::edge_descriptor add(int v, int w, int weight, int capacity) {
+        Traits::edge_descriptor add(vertex_descriptor v, vertex_descriptor w, long weight, long capacity) {
             bool b;
             Traits::edge_descriptor e;
             boost::tie(e, b) = add_edge(vertex(v, m_g), vertex(w, m_g), m_g);
@@ -65,11 +66,13 @@
     };
 
 
-    static Graph getSampleGraph(unsigned & s, unsigned & t) {
-        const boost::graph_traits<Graph>::vertices_size_type N(6);
+    static void getSampleGraph(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
+        size_type N(6);
         typedef property_map < Graph, edge_reverse_t >::type Reversed;
 
-        Graph g(N);
+        for(size_type i = 0; i < N; ++i){
+            add_vertex(g);
+        }
         Capacity  capacity = get(edge_capacity, g);
         Reversed rev = get(edge_reverse, g);
         ResidualCapacity residual_capacity = get(edge_residual_capacity, g); 
@@ -78,8 +81,7 @@
         s = 0;
         t = 5;
 
-        EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity> 
-            ea(g, weight, capacity, rev, residual_capacity);
+        EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
 
         ea.addEdge(0, 1, 4 ,2);
         ea.addEdge(0, 2, 2 ,2);
@@ -91,15 +93,17 @@
 
         ea.addEdge(3, 5, 4 ,20);
         ea.addEdge(4, 5, 2 ,20);
-
-        return g;
     }       
-    
-    static Graph getSampleGraph2(unsigned & s, unsigned & t) {
+
+    static void getSampleGraph2(Graph &g, vertex_descriptor & s, vertex_descriptor & t) {
+
         const boost::graph_traits<Graph>::vertices_size_type N(5);
         typedef property_map < Graph, edge_reverse_t >::type Reversed;
 
-        Graph g(N);
+        for(size_type i = 0; i < N; ++i){
+            add_vertex(g);
+        }
+
         Capacity  capacity = get(edge_capacity, g);
         Reversed rev = get(edge_reverse, g);
         ResidualCapacity residual_capacity = get(edge_residual_capacity, g); 
@@ -108,8 +112,7 @@
         s = 0;
         t = 4;
 
-        EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity> 
-            ea(g, weight, capacity, rev, residual_capacity);
+        EdgeAdder ea(g, weight, capacity, rev, residual_capacity);
 
         ea.addEdge(0, 1, 4 ,2);
         ea.addEdge(0, 2, 2 ,2);
@@ -117,7 +120,7 @@
         ea.addEdge(2, 3, 1 ,1);
         ea.addEdge(2, 4, 1 ,1);
         ea.addEdge(3, 4, 1 ,1);
-        
+
 
         ea.addEdge(1, 0, 2 ,2);
         ea.addEdge(2, 0, 1 ,1);
@@ -125,8 +128,6 @@
         ea.addEdge(3, 2, 1 ,1);
         ea.addEdge(4, 2, 2 ,2);
         ea.addEdge(4, 3, 1 ,3);
-
-        return g;
     }       
 };
 } //boost

Modified: trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp
==============================================================================
--- trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp	Thu Sep 12 18:00:51 2013	(r85660)
+++ trunk/libs/graph/test/successive_shortest_path_nonnegative_weights_test.cpp	2013-09-13 10:48:17 EDT (Fri, 13 Sep 2013)	(r85661)
@@ -18,9 +18,9 @@
 
 
 BOOST_AUTO_TEST_CASE(path_augmentation_def_test) {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g; 
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     boost::successive_shortest_path_nonnegative_weights(g, s, t);
 
@@ -29,9 +29,9 @@
 }
 
 BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
-    unsigned s,t;
-    boost::SampleGraph::Graph g 
-        = boost::SampleGraph::getSampleGraph2(s, t);
+    boost::SampleGraph::vertex_descriptor s,t;
+    boost::SampleGraph::Graph g; 
+    boost::SampleGraph::getSampleGraph2(g, s, t);
 
     boost::successive_shortest_path_nonnegative_weights(g, s, t);
 
@@ -40,9 +40,10 @@
 }
 
 BOOST_AUTO_TEST_CASE(path_augmentation_test) {
-    unsigned s,t;
+    boost::SampleGraph::vertex_descriptor s,t;
     typedef boost::SampleGraph::Graph Graph;
-    Graph g = boost::SampleGraph::getSampleGraph(s, t);
+    Graph g;
+    boost::SampleGraph::getSampleGraph(g, s, t);
 
     int N = boost::num_vertices(g);
     std::vector<int> dist(N);