Changes in / [1173:57167d92e96c:1164:04f57dad1b07] in lemon-main

Files:

• lemon/dimacs.h (modified) (7 diffs)
• lemon/lgf_reader.h (modified) (4 diffs)
• lemon/lgf_writer.h (modified) (4 diffs)
• lemon/preflow.h (modified) (6 diffs)
• lemon/static_graph.h (modified) (2 diffs)
• lemon/vf2.h (modified) (1 diff)
• test/bellman_ford_test.cc (modified) (2 diffs)
• test/max_flow_test.cc (modified) (14 diffs)
• tools/dimacs-solver.cc (modified) (3 diffs)

lemon/dimacs.h

@@ -26 +26 @@
 #include <lemon/maps.h>
 #include <lemon/error.h>
-
 /// \ingroup dimacs_group
 /// \file
@@ -124 +123 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c desc parameter.
+  /// the descriptor struct should be given by the \c dest parameter.
   template <typename Digraph, typename LowerMap,
             typename CapacityMap, typename CostMap,
@@ -278 +277 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c desc parameter.
+  /// the descriptor struct should be given by the \c dest parameter.
   template<typename Digraph, typename CapacityMap>
   void readDimacsMax(std::istream& is,
@@ -305 +304 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c desc parameter.
+  /// the descriptor struct should be given by the \c dest parameter.
   template<typename Digraph, typename LengthMap>
   void readDimacsSp(std::istream& is,
@@ -336 +335 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c desc parameter.
+  /// the descriptor struct should be given by the \c dest parameter.
   template<typename Digraph, typename CapacityMap>
   void readDimacsCap(std::istream& is,
@@ -345 +344 @@
     typename Digraph::Node u,v;
     if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);
-    if(desc.type!=DimacsDescriptor::MAX && desc.type!=DimacsDescriptor::SP)
+    if(desc.type!=DimacsDescriptor::MAX || desc.type!=DimacsDescriptor::SP)
       throw FormatError("Problem type mismatch");
     _readDimacs(is, g, capacity, u, v, infty, desc);
@@ -376 +375 @@
   ///
   /// If the file type was previously evaluated by dimacsType(), then
-  /// the descriptor struct should be given by the \c desc parameter.
+  /// the descriptor struct should be given by the \c dest parameter.
   template<typename Graph>
   void readDimacsMat(std::istream& is, Graph &g,

lemon/lgf_reader.h

@@ -452 +452 @@
   ///
   ///\code
-  /// DigraphReader<DGR>(digraph, std::cin)
-  ///   .nodeMap("coordinates", coord_map)
-  ///   .arcMap("capacity", cap_map)
-  ///   .node("source", src)
-  ///   .node("target", trg)
-  ///   .attribute("caption", caption)
-  ///   .run();
+  /// DigraphReader<DGR>(digraph, std::cin).
+  ///   nodeMap("coordinates", coord_map).
+  ///   arcMap("capacity", cap_map).
+  ///   node("source", src).
+  ///   node("target", trg).
+  ///   attribute("caption", caption).
+  ///   run();
   ///\endcode
   ///
@@ -1247 +1247 @@
   ///ListDigraph::ArcMap<int> cap(digraph);
   ///ListDigraph::Node src, trg;
-  ///digraphReader(digraph, std::cin)
-  ///  .arcMap("capacity", cap)
-  ///  .node("source", src)
-  ///  .node("target", trg)
-  ///  .run();
+  ///digraphReader(digraph, std::cin).
+  ///  arcMap("capacity", cap).
+  ///  node("source", src).
+  ///  node("target", trg).
+  ///  run();
   ///\endcode
   ///
@@ -2124 +2124 @@
   ///ListGraph graph;
   ///ListGraph::EdgeMap<int> weight(graph);
-  ///graphReader(graph, std::cin)
-  ///  .edgeMap("weight", weight)
-  ///  .run();
+  ///graphReader(graph, std::cin).
+  ///  edgeMap("weight", weight).
+  ///  run();
   ///\endcode
   ///
@@ -3192 +3192 @@
   ///ListBpGraph graph;
   ///ListBpGraph::EdgeMap<int> weight(graph);
-  ///bpGraphReader(graph, std::cin)
-  ///  .edgeMap("weight", weight)
-  ///  .run();
+  ///bpGraphReader(graph, std::cin).
+  ///  edgeMap("weight", weight).
+  ///  run();
   ///\endcode
   ///

lemon/lgf_writer.h

@@ -409 +409 @@
   ///
   ///\code
-  /// DigraphWriter<DGR>(digraph, std::cout)
-  ///   .nodeMap("coordinates", coord_map)
-  ///   .nodeMap("size", size)
-  ///   .nodeMap("title", title)
-  ///   .arcMap("capacity", cap_map)
-  ///   .node("source", src)
-  ///   .node("target", trg)
-  ///   .attribute("caption", caption)
-  ///   .run();
+  /// DigraphWriter<DGR>(digraph, std::cout).
+  ///   nodeMap("coordinates", coord_map).
+  ///   nodeMap("size", size).
+  ///   nodeMap("title", title).
+  ///   arcMap("capacity", cap_map).
+  ///   node("source", src).
+  ///   node("target", trg).
+  ///   attribute("caption", caption).
+  ///   run();
   ///\endcode
   ///
@@ -962 +962 @@
   ///ListDigraph::Node src, trg;
   ///  // Setting the capacity map and source and target nodes
-  ///digraphWriter(digraph, std::cout)
-  ///  .arcMap("capacity", cap)
-  ///  .node("source", src)
-  ///  .node("target", trg)
-  ///  .run();
+  ///digraphWriter(digraph, std::cout).
+  ///  arcMap("capacity", cap).
+  ///  node("source", src).
+  ///  node("target", trg).
+  ///  run();
   ///\endcode
   ///
@@ -1600 +1600 @@
   ///ListGraph::EdgeMap<int> weight(graph);
   ///  // Setting the weight map
-  ///graphWriter(graph, std::cout)
-  ///  .edgeMap("weight", weight)
-  ///  .run();
+  ///graphWriter(graph, std::cout).
+  ///  edgeMap("weight", weight).
+  ///  run();
   ///\endcode
   ///
@@ -2420 +2420 @@
   ///ListBpGraph::EdgeMap<int> weight(graph);
   ///  // Setting the weight map
-  ///bpGraphWriter(graph, std::cout)
-  ///  .edgeMap("weight", weight)
-  ///  .run();
+  ///bpGraphWriter(graph, std::cout).
+  ///  edgeMap("weight", weight).
+  ///  run();
   ///\endcode
   ///

lemon/preflow.h

@@ -477 +477 @@
     /// flow to the given \c flowMap. The \c flowMap should contain a
     /// flow or at least a preflow, i.e. at each node excluding the
-    /// source node the incoming flow should be greater or equal to the
+    /// source node the incoming flow should greater or equal to the
     /// outgoing flow.
     /// \return \c false if the given \c flowMap is not a preflow.
@@ -496 +496 @@
           excess -= (*_flow)[e];
         }
-        if (_tolerance.negative(excess) && n != _source) return false;
+        if (excess < 0 && n != _source) return false;
         (*_excess)[n] = excess;
       }
@@ -640 +640 @@
           (*_excess)[n] = excess;
 
-          if (_tolerance.nonZero(excess)) {
+          if (excess != 0) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftHighestActive(new_level + 1);
@@ -721 +721 @@
           (*_excess)[n] = excess;
 
-          if (_tolerance.nonZero(excess)) {
+          if (excess != 0) {
             if (new_level + 1 < _level->maxLevel()) {
               _level->liftActiveOn(level, new_level + 1);
@@ -792 +792 @@
         if (!reached[n]) {
           _level->dirtyTopButOne(n);
-        } else if (_tolerance.positive((*_excess)[n]) && _target != n) {
+        } else if ((*_excess)[n] > 0 && _target != n) {
           _level->activate(n);
         }
@@ -853 +853 @@
         (*_excess)[n] = excess;
 
-        if (_tolerance.nonZero(excess)) {
+        if (excess != 0) {
           if (new_level + 1 < _level->maxLevel()) {
             _level->liftHighestActive(new_level + 1);

lemon/static_graph.h

@@ -30 +30 @@
 
   class StaticDigraphBase {
-
   public:
 
@@ -298 +297 @@
   /// \sa concepts::Digraph
   class StaticDigraph : public ExtendedStaticDigraphBase {
-
-  private:
-    /// Graphs are \e not copy constructible. Use DigraphCopy instead.
-    StaticDigraph(const StaticDigraph &) : ExtendedStaticDigraphBase() {};
-    /// \brief Assignment of a graph to another one is \e not allowed.
-    /// Use DigraphCopy instead.
-    void operator=(const StaticDigraph&) {}
-
   public:
 

lemon/vf2.h

@@ -27 +27 @@
 #include <lemon/dfs.h>
 #include <lemon/bfs.h>
+#include <test/test_tools.h>
 
 #include <vector>

test/bellman_ford_test.cc

@@ -101 +101 @@
     pp = const_bf_test.negativeCycle();
 
-#ifdef LEMON_CXX11
     for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
     for (auto n: const_bf_test.activeNodes()) { ::lemon::ignore_unused_variable_warning(n); }
@@ -107 +106 @@
       ::lemon::ignore_unused_variable_warning(n);
     }
-#endif
   }
   {

test/max_flow_test.cc

@@ -27 +27 @@
 #include <lemon/lgf_reader.h>
 #include <lemon/elevator.h>
-#include <lemon/tolerance.h>
 
 using namespace lemon;
@@ -67 +66 @@
   "target 8\n";
 
-char test_lgf_float[] =
-  "@nodes\n"
-  "label\n"
-  "0\n"
-  "1\n"
-  "2\n"
-  "3\n"
-  "4\n"
-  "5\n"
-  "6\n"
-  "7\n"
-  "8\n"
-  "9\n"
-  "@arcs\n"
-  "      capacity\n"
-  "0 1 0.1\n"
-  "0 2 0.1\n"
-  "0 3 0.1\n"
-  "1 4 0.1\n"
-  "2 4 0.1\n"
-  "3 4 0.1\n"
-  "4 5 0.3\n"
-  "5 6 0.1\n"
-  "5 7 0.1\n"
-  "5 8 0.1\n"
-  "6 9 0.1\n"
-  "7 9 0.1\n"
-  "8 9 0.1\n"
-  "@attributes\n"
-  "source 0\n"
-  "target 9\n";
 
 // Checks the general interface of a max flow algorithm
@@ -198 +166 @@
   typedef concepts::Digraph Digraph;
   typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
+  typedef Elevator<Digraph, Digraph::Node> Elev;
+  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 
   Digraph g;
@@ -215 +185 @@
 
 template <typename T>
-T cutValue(const SmartDigraph& g,
-           const SmartDigraph::NodeMap<bool>& cut,
-           const SmartDigraph::ArcMap<T>& cap) {
-
-  T c = 0;
-  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
-    if (cut[g.source(e)] && !cut[g.target(e)]) c += cap[e];
+T cutValue (const SmartDigraph& g,
+              const SmartDigraph::NodeMap<bool>& cut,
+              const SmartDigraph::ArcMap<T>& cap) {
+
+  T c=0;
+  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
+    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
   }
   return c;
@@ -230 +200 @@
                const SmartDigraph::ArcMap<T>& flow,
                const SmartDigraph::ArcMap<T>& cap,
-               SmartDigraph::Node s, SmartDigraph::Node t,
-               const Tolerance<T>& tol) {
+               SmartDigraph::Node s, SmartDigraph::Node t) {
 
   for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
-    if (tol.negative(flow[e]) || tol.less(cap[e], flow[e])) return false;
+    if (flow[e] < 0 || flow[e] > cap[e]) return false;
   }
 
@@ -246 +215 @@
       sum -= flow[e];
     }
-    if (tol.nonZero(sum)) return false;
+    if (sum != 0) return false;
   }
   return true;
 }
 
-void checkInitPreflow()
+void initFlowTest()
 {
   DIGRAPH_TYPEDEFS(SmartDigraph);
 
   SmartDigraph g;
-  SmartDigraph::ArcMap<int> cap(g), iflow(g);
-  Node s = g.addNode(); Node t = g.addNode();
-  Node n1 = g.addNode(); Node n2 = g.addNode();
+  SmartDigraph::ArcMap<int> cap(g),iflow(g);
+  Node s=g.addNode(); Node t=g.addNode();
+  Node n1=g.addNode(); Node n2=g.addNode();
   Arc a;
-  a = g.addArc(s, n1); cap[a] = 20; iflow[a] = 20;
-  a = g.addArc(n1, n2); cap[a] = 10; iflow[a] = 0;
-  a = g.addArc(n2, t); cap[a] = 20; iflow[a] = 0;
-
-  Preflow<SmartDigraph> pre(g, cap, s, t);
+  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
+  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
+  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
+
+  Preflow<SmartDigraph> pre(g,cap,s,t);
   pre.init(iflow);
   pre.startFirstPhase();
-
-  check(pre.flowValue() == 10, "Incorrect max flow value.");
+  check(pre.flowValue() == 10, "The incorrect max flow value.");
   check(pre.minCut(s), "Wrong min cut (Node s).");
   check(pre.minCut(n1), "Wrong min cut (Node n1).");
@@ -276 +244 @@
 
 template <typename MF, typename SF>
-void checkMaxFlowAlg(const char *input_lgf,  typename MF::Value expected) {
+void checkMaxFlowAlg() {
   typedef SmartDigraph Digraph;
   DIGRAPH_TYPEDEFS(Digraph);
@@ -285 +253 @@
   typedef BoolNodeMap CutMap;
 
-  Tolerance<Value> tol;
-
   Digraph g;
   Node s, t;
   CapMap cap(g);
-  std::istringstream input(input_lgf);
-  DigraphReader<Digraph>(g, input)
+  std::istringstream input(test_lgf);
+  DigraphReader<Digraph>(g,input)
       .arcMap("capacity", cap)
-      .node("source", s)
-      .node("target", t)
+      .node("source",s)
+      .node("target",t)
       .run();
 
@@ -300 +266 @@
   max_flow.run();
 
-  check(!tol.different(expected, max_flow.flowValue()),
-        "Incorrect max flow value.");
-  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
         "The flow is not feasible.");
 
@@ -309 +273 @@
   Value min_cut_value = cutValue(g, min_cut, cap);
 
-  check(!tol.different(expected, min_cut_value),
-        "Incorrect min cut value.");
+  check(max_flow.flowValue() == min_cut_value,
+        "The max flow value is not equal to the min cut value.");
 
   FlowMap flow(g);
-  for (ArcIt e(g); e != INVALID; ++e) flow[e] = 13 * max_flow.flowMap()[e];
-  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 17 * cap[e];
+  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
+
+  Value flow_value = max_flow.flowValue();
+
+  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
   max_flow.init(flow);
 
@@ -323 +290 @@
   min_cut_value = cutValue(g, min_cut1, cap);
 
-  check(!tol.different(17 * expected, max_flow.flowValue()),
-        "Incorrect max flow value.");
-  check(!tol.different(17 * expected, min_cut_value),
-        "Incorrect min cut value.");
+  check(max_flow.flowValue() == min_cut_value &&
+        min_cut_value == 2 * flow_value,
+        "The max flow value or the min cut value is wrong.");
 
   SF::startSecondPhase(max_flow);       // start second phase of the algorithm
 
-  check(checkFlow(g, max_flow.flowMap(), cap, s, t, tol),
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
         "The flow is not feasible.");
 
@@ -337 +303 @@
   min_cut_value = cutValue(g, min_cut2, cap);
 
-  check(!tol.different(17 * expected, max_flow.flowValue()),
-        "Incorrect max flow value.");
-  check(!tol.different(17 * expected, min_cut_value),
-        "Incorrect min cut value.");
+  check(max_flow.flowValue() == min_cut_value &&
+        min_cut_value == 2 * flow_value,
+        "The max flow value or the min cut value was not doubled");
+
 
   max_flow.flowMap(flow);
@@ -359 +325 @@
   CutMap min_cut3(g);
   max_flow.minCutMap(min_cut3);
-  min_cut_value = cutValue(g, min_cut3, cap);
-
-  check(!tol.different(max_flow.flowValue(), min_cut_value),
+  min_cut_value=cutValue(g, min_cut3, cap);
+
+  check(max_flow.flowValue() == min_cut_value,
         "The max flow value or the min cut value is wrong.");
 }
@@ -414 +380 @@
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
   typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
-  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<double> > PType3;
-
-  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >(test_lgf, 13);
-  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf, 13);
-  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf, 13);
-
-  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >(test_lgf_float, 0.3);
-  checkMaxFlowAlg<PType3, PreflowStartFunctions<PType3> >(test_lgf_float, 0.3);
-
-  checkInitPreflow();
+  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
+  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
+  initFlowTest();
 
   // Check EdmondsKarp
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
   typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
-  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<double> > EKType3;
-
-  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >(test_lgf, 13);
-  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf, 13);
-  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf, 13);
-
-  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >(test_lgf_float, 0.3);
-  checkMaxFlowAlg<EKType3, GeneralStartFunctions<EKType3> >(test_lgf_float, 0.3);
+  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
+  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
+
+  initFlowTest();
 
   return 0;

tools/dimacs-solver.cc

@@ -223 +223 @@
         throw IoError("Cannot open the file for writing", ap.files()[1]);
       }
-      // fall through
     case 1:
       input.open(ap.files()[0].c_str());
@@ -229 +228 @@
         throw IoError("File cannot be found", ap.files()[0]);
       }
-      // fall through
     case 0:
       break;
@@ -254 +252 @@
         case DimacsDescriptor::SP:
           std::cout << "sp";
-          break;
         case DimacsDescriptor::MAT:
           std::cout << "mat";