Changeset 596:293551ad254f in lemon-main for test

Timestamp:

04/15/09 09:37:51 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improvements and fixes for the minimum cut algorithms (#264)

Location:

test

Files:

• gomory_hu_test.cc (modified) (4 diffs)
• hao_orlin_test.cc (modified) (2 diffs)

test/gomory_hu_test.cc

@@ -3 +3 @@
 #include "test_tools.h"
 #include <lemon/smart_graph.h>
+#include <lemon/concepts/graph.h>
+#include <lemon/concepts/maps.h>
 #include <lemon/lgf_reader.h>
 #include <lemon/gomory_hu.h>
@@ -33 +35 @@
   "target 3\n";
   
+void checkGomoryHuCompile()
+{
+  typedef int Value;
+  typedef concepts::Graph Graph;
+
+  typedef Graph::Node Node;
+  typedef Graph::Edge Edge;
+  typedef concepts::ReadMap<Edge, Value> CapMap;
+  typedef concepts::ReadWriteMap<Node, bool> CutMap;
+
+  Graph g;
+  Node n;
+  CapMap cap;
+  CutMap cut;
+  Value v;
+  int d;
+
+  GomoryHu<Graph, CapMap> gh_test(g, cap);
+  const GomoryHu<Graph, CapMap>&
+    const_gh_test = gh_test;
+
+  gh_test.run();
+
+  n = const_gh_test.predNode(n);
+  v = const_gh_test.predValue(n);
+  d = const_gh_test.rootDist(n);
+  v = const_gh_test.minCutValue(n, n);
+  v = const_gh_test.minCutMap(n, n, cut);
+}
+
 GRAPH_TYPEDEFS(Graph);
 typedef Graph::EdgeMap<int> IntEdgeMap;
@@ -71 +103 @@
       ght.minCutMap(u, v, cm);
       check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
-      check(cm[u] != cm[v], "Wrong cut 3");
-      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
+      check(cm[u] != cm[v], "Wrong cut 2");
+      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
 
       int sum=0;
@@ -85 +117 @@
         sum++;
       check(sum == countNodes(graph), "Problem with MinCutNodeIt");
-      
     }
   }

test/hao_orlin_test.cc

@@ -20 +20 @@
 
 #include <lemon/smart_graph.h>
+#include <lemon/adaptors.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concepts/maps.h>
+#include <lemon/lgf_reader.h>
 #include <lemon/hao_orlin.h>
 
-#include <lemon/lgf_reader.h>
 #include "test_tools.h"
 
@@ -38 +41 @@
   "5\n"
   "@edges\n"
-  "     label  capacity\n"
-  "0 1  0      2\n"
-  "1 2  1      2\n"
-  "2 0  2      2\n"
-  "3 4  3      2\n"
-  "4 5  4      2\n"
-  "5 3  5      2\n"
-  "2 3  6      3\n";
+  "     cap1 cap2 cap3\n"
+  "0 1  1    1    1   \n"
+  "0 2  2    2    4   \n"
+  "1 2  4    4    4   \n"
+  "3 4  1    1    1   \n"
+  "3 5  2    2    4   \n"
+  "4 5  4    4    4   \n"
+  "5 4  4    4    4   \n"
+  "2 3  1    6    6   \n"
+  "4 0  1    6    6   \n";
+
+void checkHaoOrlinCompile()
+{
+  typedef int Value;
+  typedef concepts::Digraph Digraph;
+
+  typedef Digraph::Node Node;
+  typedef Digraph::Arc Arc;
+  typedef concepts::ReadMap<Arc, Value> CapMap;
+  typedef concepts::WriteMap<Node, bool> CutMap;
+
+  Digraph g;
+  Node n;
+  CapMap cap;
+  CutMap cut;
+  Value v;
+
+  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
+  const HaoOrlin<Digraph, CapMap>&
+    const_ho_test = ho_test;
+
+  ho_test.init();
+  ho_test.init(n);
+  ho_test.calculateOut();
+  ho_test.calculateIn();
+  ho_test.run();
+  ho_test.run(n);
+
+  v = const_ho_test.minCutValue();
+  v = const_ho_test.minCutMap(cut);
+}
+
+template <typename Graph, typename CapMap, typename CutMap>
+typename CapMap::Value 
+  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
+{
+  typename CapMap::Value sum = 0;
+  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
+    if (cut[graph.source(a)] && !cut[graph.target(a)])
+      sum += cap[a];
+  }
+  return sum;
+}
 
 int main() {
-  SmartGraph graph;
-  SmartGraph::EdgeMap<int> capacity(graph);
+  SmartDigraph graph;
+  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
+  SmartDigraph::NodeMap<bool> cut(graph);
 
-  istringstream lgfs(lgf);
-  graphReader(graph, lgfs).
-    edgeMap("capacity", capacity).run();
+  istringstream input(lgf);
+  digraphReader(graph, input)
+    .arcMap("cap1", cap1)
+    .arcMap("cap2", cap2)
+    .arcMap("cap3", cap3)
+    .run();
 
-  HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
-  ho.run();
-
-  check(ho.minCutValue() == 3, "Wrong cut value");
+  {
+    HaoOrlin<SmartDigraph> ho(graph, cap1);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // BUG: The cut value should be positive
+    check(ho.minCutValue() == 0, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
+  }
+  {
+    HaoOrlin<SmartDigraph> ho(graph, cap2);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // BUG: The cut value should be positive
+    check(ho.minCutValue() == 0, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
+  }
+  {
+    HaoOrlin<SmartDigraph> ho(graph, cap3);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // BUG: The cut value should be positive
+    check(ho.minCutValue() == 0, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
+  }
+  
+  typedef Undirector<SmartDigraph> UGraph;
+  UGraph ugraph(graph);
+  
+  {
+    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // BUG: The cut value should be 2
+    check(ho.minCutValue() == 1, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
+  }
+  {
+    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // TODO: Check this cut value
+    check(ho.minCutValue() == 4, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
+  }
+  {
+    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
+    ho.run();
+    ho.minCutMap(cut);
+    
+    // TODO: Check this cut value
+    check(ho.minCutValue() == 5, "Wrong cut value");
+    // BUG: It should work
+    //check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
+  }
 
   return 0;