Changeset 1173:d216e1c8b3fa in lemon for test

Timestamp:

11/28/12 11:54:43 (11 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Parents:

1160:00f8d9f9920d (diff), 1171:7e368d9b67f7 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge #453 to branches >=1.2

Location:

test

Files:

• bfs_test.cc (modified) (2 diffs)
• bfs_test.cc (modified) (5 diffs)
• circulation_test.cc (modified) (1 diff)
• circulation_test.cc (modified) (4 diffs)
• dfs_test.cc (modified) (2 diffs)
• dfs_test.cc (modified) (4 diffs)
• dijkstra_test.cc (modified) (2 diffs)
• dijkstra_test.cc (modified) (5 diffs)
• gomory_hu_test.cc (modified) (1 diff)
• gomory_hu_test.cc (modified) (5 diffs)
• hao_orlin_test.cc (modified) (1 diff)
• hao_orlin_test.cc (modified) (6 diffs)
• matching_test.cc (modified) (1 diff)
• matching_test.cc (modified) (8 diffs)
• min_cost_arborescence_test.cc (modified) (1 diff)
• min_cost_arborescence_test.cc (modified) (3 diffs)
• preflow_test.cc (modified) (1 diff)
• preflow_test.cc (modified) (3 diffs)
• suurballe_test.cc (modified) (1 diff)
• suurballe_test.cc (modified) (9 diffs)

test/bfs_test.cc

@@ -62 +62 @@
   Arc e;
   int l, i;
+  ignore_unused_variable_warning(l,i);
   bool b;
   BType::DistMap d(G);
@@ -151 +152 @@
   Digraph g;
   bool b;
+  ignore_unused_variable_warning(b);
+
   bfs(g).run(Node());
   b=bfs(g).run(Node(),Node());

test/bfs_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -85 +85 @@
     b = const_bfs_test.emptyQueue();
     i = const_bfs_test.queueSize();
-    
+
     bfs_test.start();
     bfs_test.start(t);
@@ -106 +106 @@
       ::SetProcessedMap<concepts::WriteMap<Node,bool> >
       ::Create bfs_test(G);
-      
+
     concepts::ReadWriteMap<Node,Arc> pred_map;
     concepts::ReadWriteMap<Node,int> dist_map;
     concepts::ReadWriteMap<Node,bool> reached_map;
     concepts::WriteMap<Node,bool> processed_map;
-    
+
     bfs_test
       .predMap(pred_map)
@@ -121 +121 @@
     bfs_test.run(s,t);
     bfs_test.run();
-    
+
     bfs_test.init();
     bfs_test.addSource(s);
@@ -130 +130 @@
     b = bfs_test.emptyQueue();
     i = bfs_test.queueSize();
-    
+
     bfs_test.start();
     bfs_test.start(t);

test/circulation_test.cc

@@ -74 +74 @@
   VType v;
   bool b;
+  ignore_unused_variable_warning(v,b);
 
   typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>

test/circulation_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -83 +83 @@
   CirculationType circ_test(g, lcap, ucap, supply);
   const CirculationType& const_circ_test = circ_test;
-   
+
   circ_test
     .lowerMap(lcap)
@@ -89 +89 @@
     .supplyMap(supply)
     .flowMap(flow);
+
+  const CirculationType::Elevator& elev = const_circ_test.elevator();
+  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
+  CirculationType::Tolerance tol = const_circ_test.tolerance();
+  circ_test.tolerance(tol);
 
   circ_test.init();
@@ -99 +104 @@
   b = const_circ_test.barrier(n);
   const_circ_test.barrierMap(bar);
-  
+
   ignore_unused_variable_warning(fm);
 }

test/dfs_test.cc

@@ -68 +68 @@
   int l, i;
   bool b;
+  ignore_unused_variable_warning(l,i,b);
+
   DType::DistMap d(G);
   DType::PredMap p(G);
@@ -152 +154 @@
   Digraph g;
   bool b;
+  ignore_unused_variable_warning(b);
+
   dfs(g).run(Node());
   b=dfs(g).run(Node(),Node());

test/dfs_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -89 +89 @@
     b = const_dfs_test.emptyQueue();
     i = const_dfs_test.queueSize();
-    
+
     dfs_test.start();
     dfs_test.start(t);
@@ -115 +115 @@
     concepts::ReadWriteMap<Node,bool> reached_map;
     concepts::WriteMap<Node,bool> processed_map;
-    
+
     dfs_test
       .predMap(pred_map)
@@ -132 +132 @@
     b = dfs_test.emptyQueue();
     i = dfs_test.queueSize();
-    
+
     dfs_test.start();
     dfs_test.start(t);

test/dijkstra_test.cc

@@ -66 +66 @@
   int i;
   bool b;
+  ignore_unused_variable_warning(l,i,b);
+
   DType::DistMap d(G);
   DType::PredMap p(G);
@@ -163 +165 @@
   Digraph g;
   bool b;
+  ignore_unused_variable_warning(b);
+
   dijkstra(g,LengthMap()).run(Node());
   b=dijkstra(g,LengthMap()).run(Node(),Node());

test/dijkstra_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -88 +88 @@
     b = const_dijkstra_test.emptyQueue();
     i = const_dijkstra_test.queueSize();
-    
+
     dijkstra_test.start();
     dijkstra_test.start(t);
@@ -112 +112 @@
       ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
       ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
-      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >, 
+      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
                 concepts::ReadWriteMap<Node,int> >
       ::Create dijkstra_test(G,length);
@@ -122 +122 @@
     concepts::ReadWriteMap<Node,int> heap_cross_ref;
     BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
-    
+
     dijkstra_test
       .lengthMap(length_map)
@@ -139 +139 @@
     b = dijkstra_test.emptyQueue();
     i = dijkstra_test.queueSize();
-    
+
     dijkstra_test.start();
     dijkstra_test.start(t);

test/gomory_hu_test.cc

@@ -69 +69 @@
   Value v;
   int d;
+  ignore_unused_variable_warning(v,d);
 
   GomoryHu<Graph, CapMap> gh_test(g, cap);

test/gomory_hu_test.cc

@@ +1 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
 #include <iostream>
 
@@ -34 +52 @@
   "source 0\n"
   "target 3\n";
-  
+
 void checkGomoryHuCompile()
 {
@@ -71 +89 @@
 
 int cutValue(const Graph& graph, const BoolNodeMap& cut,
-             const IntEdgeMap& capacity) {
+             const IntEdgeMap& capacity) {
 
   int sum = 0;
@@ -109 +127 @@
       int sum=0;
       for(GomoryHu<Graph>::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a)
-        sum+=capacity[a]; 
+        sum+=capacity[a];
       check(sum == ght.minCutValue(u, v), "Problem with MinCutEdgeIt");
 
@@ -120 +138 @@
     }
   }
-  
+
   return 0;
 }

test/hao_orlin_test.cc

@@ -67 +67 @@
   CutMap cut;
   Value v;
+  ignore_unused_variable_warning(v);
 
   HaoOrlin<Digraph, CapMap> ho_test(g, cap);

test/hao_orlin_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -85 +85 @@
 
 template <typename Graph, typename CapMap, typename CutMap>
-typename CapMap::Value 
+typename CapMap::Value
   cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
 {
@@ -112 +112 @@
     ho.run();
     ho.minCutMap(cut);
-    
+
     check(ho.minCutValue() == 1, "Wrong cut value");
     check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
@@ -128 +128 @@
     ho.run();
     ho.minCutMap(cut);
-    
+
     check(ho.minCutValue() == 1, "Wrong cut value");
     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);
-    
+
     check(ho.minCutValue() == 2, "Wrong cut value");
     check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
@@ -148 +148 @@
     ho.run();
     ho.minCutMap(cut);
-    
+
     check(ho.minCutValue() == 5, "Wrong cut value");
     check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
@@ -156 +156 @@
     ho.run();
     ho.minCutMap(cut);
-    
+
     check(ho.minCutValue() == 5, "Wrong cut value");
     check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");

test/matching_test.cc

@@ -146 +146 @@
   MaxMatching<Graph>::Status stat =
     const_mat_test.status(n);
+  ignore_unused_variable_warning(stat);
   const MaxMatching<Graph>::StatusMap& smap =
     const_mat_test.statusMap();

test/matching_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -135 +135 @@
   mat_test.startDense();
   mat_test.run();
-  
+
   const_mat_test.matchingSize();
   const_mat_test.matching(e);
@@ -144 +144 @@
   const_mat_test.mate(n);
 
-  MaxMatching<Graph>::Status stat = 
+  MaxMatching<Graph>::Status stat =
     const_mat_test.status(n);
   ignore_unused_variable_warning(stat);
@@ -172 +172 @@
   mat_test.start();
   mat_test.run();
-  
+
   const_mat_test.matchingWeight();
   const_mat_test.matchingSize();
@@ -181 +181 @@
   e = mmap[n];
   const_mat_test.mate(n);
-  
+
   int k = 0;
   const_mat_test.dualValue();
@@ -209 +209 @@
   mat_test.start();
   mat_test.run();
-  
+
   const_mat_test.matchingWeight();
   const_mat_test.matching(e);
@@ -217 +217 @@
   e = mmap[n];
   const_mat_test.mate(n);
-  
+
   int k = 0;
   const_mat_test.dualValue();
@@ -403 +403 @@
       edgeMap("weight", weight).run();
 
-    MaxMatching<SmartGraph> mm(graph);
-    mm.run();
-    checkMatching(graph, mm);
-
-    MaxWeightedMatching<SmartGraph> mwm(graph, weight);
-    mwm.run();
-    checkWeightedMatching(graph, weight, mwm);
-
-    MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
-    bool perfect = mwpm.run();
-
-    check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
-          "Perfect matching found");
-
-    if (perfect) {
-      checkWeightedPerfectMatching(graph, weight, mwpm);
+    bool perfect;
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.run();
+      checkMatching(graph, mm);
+      perfect = 2 * mm.matchingSize() == countNodes(graph);
+    }
+
+    {
+      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
+      mwm.run();
+      checkWeightedMatching(graph, weight, mwm);
+    }
+
+    {
+      MaxWeightedMatching<SmartGraph> mwm(graph, weight);
+      mwm.init();
+      mwm.start();
+      checkWeightedMatching(graph, weight, mwm);
+    }
+
+    {
+      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
+      bool result = mwpm.run();
+
+      check(result == perfect, "Perfect matching found");
+      if (perfect) {
+        checkWeightedPerfectMatching(graph, weight, mwpm);
+      }
+    }
+
+    {
+      MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
+      mwpm.init();
+      bool result = mwpm.start();
+
+      check(result == perfect, "Perfect matching found");
+      if (perfect) {
+        checkWeightedPerfectMatching(graph, weight, mwpm);
+      }
     }
   }

test/min_cost_arborescence_test.cc

@@ -92 +92 @@
   VType c;
   bool b;
+  ignore_unused_variable_warning(c,b);
   int i;
   CostMap cost;

test/min_cost_arborescence_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -112 +112 @@
   b = const_mcarb_test.emptyQueue();
   i = const_mcarb_test.queueSize();
-  
+
   c = const_mcarb_test.arborescenceCost();
   b = const_mcarb_test.arborescence(e);
@@ -122 +122 @@
   b = const_mcarb_test.reached(n);
   b = const_mcarb_test.processed(n);
-  
+
   i = const_mcarb_test.dualNum();
   c = const_mcarb_test.dualValue();
   i = const_mcarb_test.dualSize(i);
   c = const_mcarb_test.dualValue(i);
-  
+
   ignore_unused_variable_warning(am);
   ignore_unused_variable_warning(pm);

test/preflow_test.cc

@@ -87 +87 @@
   VType v;
   bool b;
+  ignore_unused_variable_warning(v,b);
 
   typedef Preflow<Digraph, CapMap>

test/preflow_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -97 +97 @@
   const PreflowType& const_preflow_test = preflow_test;
 
+  const PreflowType::Elevator& elev = const_preflow_test.elevator();
+  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
+  PreflowType::Tolerance tol = const_preflow_test.tolerance();
+  preflow_test.tolerance(tol);
+
   preflow_test
     .capacityMap(cap)
@@ -115 +120 @@
   b = const_preflow_test.minCut(n);
   const_preflow_test.minCutMap(cut);
-  
+
   ignore_unused_variable_warning(fm);
 }

test/suurballe_test.cc

@@ -118 +118 @@
   int f;
   VType c;
+  ignore_unused_variable_warning(f,c);
+
   c = const_suurb_test.totalLength();
   f = const_suurb_test.flow(e);

test/suurballe_test.cc

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -24 +24 @@
 #include <lemon/suurballe.h>
 #include <lemon/concepts/digraph.h>
+#include <lemon/concepts/heap.h>
 
 #include "test_tools.h"
@@ -81 +82 @@
   typedef Digraph::Arc Arc;
   typedef concepts::ReadMap<Arc, VType> LengthMap;
-  
-  typedef Suurballe<Digraph, LengthMap> SuurballeType;
+
+  typedef Suurballe<Digraph, LengthMap> ST;
+  typedef Suurballe<Digraph, LengthMap>
+    ::SetFlowMap<ST::FlowMap>
+    ::SetPotentialMap<ST::PotentialMap>
+    ::SetPath<SimplePath<Digraph> >
+    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
+    ::Create SuurballeType;
 
   Digraph g;
@@ -102 +109 @@
   k = suurb_test.run(n, n, k);
   suurb_test.init(n);
+  suurb_test.fullInit(n);
+  suurb_test.start(n);
+  suurb_test.start(n, k);
   k = suurb_test.findFlow(n);
   k = suurb_test.findFlow(n, k);
   suurb_test.findPaths();
-  
+
   int f;
   VType c;
@@ -119 +129 @@
   k = const_suurb_test.pathNum();
   Path<Digraph> p = const_suurb_test.path(k);
-  
+
   ignore_unused_variable_warning(fm);
   ignore_unused_variable_warning(pm);
@@ -198 +208 @@
     run();
 
-  // Find 2 paths
+  // Check run()
   {
     Suurballe<ListDigraph> suurballe(digraph, length);
+
+    // Find 2 paths
     check(suurballe.run(s, t) == 2, "Wrong number of paths");
     check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
@@ -210 +222 @@
     for (int i = 0; i < suurballe.pathNum(); ++i)
       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
-  }
-
-  // Find 3 paths
-  {
-    Suurballe<ListDigraph> suurballe(digraph, length);
+
+    // Find 3 paths
     check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
@@ -224 +233 @@
     for (int i = 0; i < suurballe.pathNum(); ++i)
       check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
-  }
-
-  // Find 5 paths (only 3 can be found)
-  {
-    Suurballe<ListDigraph> suurballe(digraph, length);
+
+    // Find 5 paths (only 3 can be found)
     check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
     check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
@@ -240 +246 @@
   }
 
+  // Check fullInit() + start()
+  {
+    Suurballe<ListDigraph> suurballe(digraph, length);
+    suurballe.fullInit(s);
+
+    // Find 2 paths
+    check(suurballe.start(t) == 2, "Wrong number of paths");
+    check(suurballe.totalLength() == 510, "The flow is not optimal");
+
+    // Find 3 paths
+    check(suurballe.start(t, 3) == 3, "Wrong number of paths");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+
+    // Find 5 paths (only 3 can be found)
+    check(suurballe.start(t, 5) == 3, "Wrong number of paths");
+    check(suurballe.totalLength() == 1040, "The flow is not optimal");
+  }
+
   return 0;
 }