Changeset 2586:37fb2c384c78 in lemon-0.x for test/suurballe_test.cc

Timestamp:

02/29/08 16:55:13 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3468

Message:

Reimplemented Suurballe class.

• The new version is the specialized version of CapacityScaling?.
• It is about 10-20 times faster than the former Suurballe algorithm

and about 20-50 percent faster than CapacityScaling?.

• Doc improvements.
• The test file is also replaced.

File:

• test/suurballe_test.cc (modified) (1 diff)

test/suurballe_test.cc

@@ -18 +18 @@
 
 #include <iostream>
+#include <fstream>
+
 #include <lemon/list_graph.h>
+#include <lemon/graph_reader.h>
+#include <lemon/path.h>
 #include <lemon/suurballe.h>
-//#include <path.h>
+
 #include "test_tools.h"
 
 using namespace lemon;
 
+// Checks the feasibility of the flow
+template <typename Graph, typename FlowMap>
+bool checkFlow( const Graph& gr, const FlowMap& flow, 
+                typename Graph::Node s, typename Graph::Node t,
+                int value )
+{
+  GRAPH_TYPEDEFS(typename Graph);
+  for (EdgeIt e(gr); e != INVALID; ++e)
+    if (!(flow[e] == 0 || flow[e] == 1)) return false;
 
-bool passed = true;
+  for (NodeIt n(gr); n != INVALID; ++n) {
+    int sum = 0;
+    for (OutEdgeIt e(gr, n); e != INVALID; ++e)
+      sum += flow[e];
+    for (InEdgeIt e(gr, n); e != INVALID; ++e)
+      sum -= flow[e];
+    if (n == s && sum != value) return false;
+    if (n == t && sum != -value) return false;
+    if (n != s && n != t && sum != 0) return false;
+  }
+
+  return true;
+}
+
+// Checks the optimalitiy of the flow
+template < typename Graph, typename CostMap, 
+           typename FlowMap, typename PotentialMap >
+bool checkOptimality( const Graph& gr, const CostMap& cost,
+                      const FlowMap& flow, const PotentialMap& pi )
+{
+  // Checking the Complementary Slackness optimality condition
+  GRAPH_TYPEDEFS(typename Graph);
+  bool opt = true;
+  for (EdgeIt e(gr); e != INVALID; ++e) {
+    typename CostMap::Value red_cost =
+      cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
+    opt = (flow[e] == 0 && red_cost >= 0) ||
+          (flow[e] == 1 && red_cost <= 0);
+    if (!opt) break;
+  }
+  return opt;
+}
+
+// Checks a path
+template < typename Graph, typename Path >
+bool checkPath( const Graph& gr, const Path& path,
+                typename Graph::Node s, typename Graph::Node t)
+{
+  // Checking the Complementary Slackness optimality condition
+  GRAPH_TYPEDEFS(typename Graph);
+  Node n = s;
+  for (int i = 0; i < path.length(); ++i) {
+    if (gr.source(path.nth(i)) != n) return false;
+    n = gr.target(path.nth(i));
+  }
+  return n == t;
+}
 
 
 int main()
 {
-  typedef ListGraph Graph;
-  typedef Graph::Node Node;
-  typedef Graph::Edge Edge;
+  GRAPH_TYPEDEFS(ListGraph);
 
-  Graph graph;
+  // Reading the test graph
+  ListGraph graph;
+  ListGraph::EdgeMap<int> length(graph);
+  Node source, target;
 
-  //Ahuja könyv példája
+  std::string fname;
+  if(getenv("srcdir"))
+    fname = std::string(getenv("srcdir"));
+  else fname = ".";
+  fname += "/test/min_cost_flow_test.lgf";
 
-  Node s=graph.addNode();
-  Node v1=graph.addNode();  
-  Node v2=graph.addNode();
-  Node v3=graph.addNode();
-  Node v4=graph.addNode();
-  Node v5=graph.addNode();
-  Node t=graph.addNode();
+  std::ifstream input(fname.c_str());
+  check(input, "Input file '" << fname << "' not found");
+  GraphReader<ListGraph>(input, graph).
+    readEdgeMap("cost", length).
+    readNode("source", source).
+    readNode("target", target).
+    run();
+  input.close();
+  
+  // Finding 2 paths
+  {
+    Suurballe<ListGraph> suurballe(graph, length, source, target);
+    check(suurballe.run(2) == 2, "Wrong number of paths");
+    check(checkFlow(graph, suurballe.flowMap(), source, target, 2),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 510, "The flow is not optimal");
+    check(checkOptimality(graph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(graph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
 
-  Edge s_v1=graph.addEdge(s, v1);
-  Edge v1_v2=graph.addEdge(v1, v2);
-  Edge s_v3=graph.addEdge(s, v3);
-  Edge v2_v4=graph.addEdge(v2, v4);
-  Edge v2_v5=graph.addEdge(v2, v5);
-  Edge v3_v5=graph.addEdge(v3, v5);
-  Edge v4_t=graph.addEdge(v4, t);
-  Edge v5_t=graph.addEdge(v5, t);
-  
+  // Finding 3 paths
+  {
+    Suurballe<ListGraph> suurballe(graph, length, source, target);
+    check(suurballe.run(3) == 3, "Wrong number of paths");
+    check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+    check(checkOptimality(graph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(graph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
 
-  Graph::EdgeMap<int> length(graph);
+  // Finding 5 paths (only 3 can be found)
+  {
+    Suurballe<ListGraph> suurballe(graph, length, source, target);
+    check(suurballe.run(5) == 3, "Wrong number of paths");
+    check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
+          "The flow is not feasible");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+    check(checkOptimality(graph, length, suurballe.flowMap(), 
+                          suurballe.potentialMap()),
+          "Wrong potentials");
+    for (int i = 0; i < suurballe.pathNum(); ++i)
+      check(checkPath(graph, suurballe.path(i), source, target),
+            "Wrong path");
+  }
 
-  length.set(s_v1, 6);
-  length.set(v1_v2, 4);
-  length.set(s_v3, 10);
-  length.set(v2_v4, 5);
-  length.set(v2_v5, 1);
-  length.set(v3_v5, 5);
-  length.set(v4_t, 8);
-  length.set(v5_t, 8);
-
-  std::cout << "Minlengthpaths algorithm test..." << std::endl;
-
-  
-  int k=3;
-  Suurballe< Graph, Graph::EdgeMap<int> >
-    surb_test(graph, length, s, t);
-
-  check(  surb_test.run(k) == 2 && surb_test.totalLength() == 46,
-          "Two paths, total length should be 46");
-
-  check(  surb_test.checkComplementarySlackness(),
-          "Complementary slackness conditions are not met.");
-
-  //  typedef DirPath<Graph> DPath;
-  //  DPath P(graph);
-
-  /*
-  surb_test.getPath(P,0);
-  check(P.length() == 4, "First path should contain 4 edges.");  
-  std::cout<<P.length()<<std::endl;
-  surb_test.getPath(P,1);
-  check(P.length() == 3, "Second path: 3 edges.");
-  std::cout<<P.length()<<std::endl;
-  */  
-
-  k=1;
-  check(  surb_test.run(k) == 1 && surb_test.totalLength() == 19,
-          "One path, total length should be 19");
-
-  check(  surb_test.checkComplementarySlackness(),
-          "Complementary slackness conditions are not met.");
- 
-  //  surb_test.getPath(P,0);
-  //  check(P.length() == 4, "First path should contain 4 edges.");  
-
-  std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
-            << std::endl;
-
-  return passed ? 0 : 1;
-
+  return 0;
 }