Changes in / [431:9dfaf6efc36f:432:e9a568cc86e3] in lemon-1.2

Files:

• lemon/bfs.h (modified) (1 diff)
• lemon/circulation.h (modified) (6 diffs)
• lemon/connectivity.h (modified) (33 diffs)
• lemon/dfs.h (modified) (2 diffs)
• lemon/max_matching.h (modified) (1 diff)
• lemon/preflow.h (modified) (2 diffs)
• lemon/suurballe.h (modified) (1 diff)
• scripts/chg-len.py (modified) (1 diff)
• test/CMakeLists.txt (modified) (3 diffs)
• test/Makefile.am (modified) (2 diffs)
• test/min_cost_flow_test.lgf (deleted)
• test/preflow_graph.lgf (deleted)
• test/preflow_test.cc (modified) (3 diffs)
• test/suurballe_test.cc (modified) (4 diffs)

lemon/bfs.h

@@ -1742 +1742 @@
     /// \pre Either \ref run(Node) "run()" or \ref init()
     /// must be called before using this function.
-    bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
 
     ///@}

lemon/circulation.h

@@ -420 +420 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    const Elevator& elevator() {
+    const Elevator& elevator() const {
       return *_level;
     }
@@ -645 +645 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    const FlowMap& flowMap() {
+    const FlowMap& flowMap() const {
       return *_flow;
     }
@@ -670 +670 @@
        \sa checkBarrier()
     */
-    bool barrier(const Node& node)
+    bool barrier(const Node& node) const
     {
       return (*_level)[node] >= _el;
@@ -693 +693 @@
     /// \sa checkBarrier()
     template<class BarrierMap>
-    void barrierMap(BarrierMap &bar)
+    void barrierMap(BarrierMap &bar) const
     {
       for(NodeIt n(_g);n!=INVALID;++n)
@@ -713 +713 @@
     ///Check if the found flow is a feasible circulation,
     ///
-    bool checkFlow() {
+    bool checkFlow() const {
       for(ArcIt e(_g);e!=INVALID;++e)
         if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
@@ -731 +731 @@
     ///\sa barrier()
     ///\sa barrierMap()
-    bool checkBarrier()
+    bool checkBarrier() const
     {
       Value delta=0;

lemon/connectivity.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_TOPOLOGY_H
-#define LEMON_TOPOLOGY_H
+#ifndef LEMON_CONNECTIVITY_H
+#define LEMON_CONNECTIVITY_H
 
 #include <lemon/dfs.h>
@@ -155 +155 @@
   }
 
-  namespace _topology_bits {
+  namespace _connectivity_bits {
 
     template <typename Digraph, typename Iterator >
@@ -189 +189 @@
 
     template <typename Digraph, typename ArcMap>
-    struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
+    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
     public:
       typedef typename Digraph::Node Node;
       typedef typename Digraph::Arc Arc;
 
-      StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
-                                       ArcMap& cutMap,
-                                       int& cutNum)
+      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
+                                      ArcMap& cutMap,
+                                      int& cutNum)
         : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
-          _compMap(digraph), _num(0) {
-      }
-
-      void stop(const Node&) {
+          _compMap(digraph, -1), _num(-1) {
+      }
+
+      void start(const Node&) {
         ++_num;
       }
@@ -249 +249 @@
     if (source == INVALID) return true;
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef DfsVisitor<Digraph> Visitor;
@@ -266 +266 @@
 
     typedef ReverseDigraph<const Digraph> RDigraph;
+    typedef typename RDigraph::NodeIt RNodeIt;
     RDigraph rdigraph(digraph);
 
@@ -276 +277 @@
     rdfs.start();
 
-    for (NodeIt it(rdigraph); it != INVALID; ++it) {
+    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
       if (!rdfs.reached(it)) {
         return false;
@@ -295 +296 @@
   /// direction.
   ///
-  /// \param graph The graph.
+  /// \param digraph The graph.
   /// \return The number of components
   /// \note By definition, the empty graph has zero
@@ -303 +304 @@
     checkConcept<concepts::Digraph, Digraph>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef typename Digraph::Node Node;
@@ -375 +376 @@
     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef std::vector<Node> Container;
@@ -439 +440 @@
     checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef std::vector<Node> Container;
@@ -464 +465 @@
     int cutNum = 0;
 
-    typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
+    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
     RVisitor rvisitor(rgraph, cutMap, cutNum);
 
@@ -479 +480 @@
   }
 
-  namespace _topology_bits {
+  namespace _connectivity_bits {
 
     template <typename Digraph>
@@ -731 +732 @@
     typedef typename Graph::NodeIt NodeIt;
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
@@ -774 +775 @@
     checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
@@ -814 +815 @@
     checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
@@ -833 +834 @@
   }
 
-  namespace _topology_bits {
+  namespace _connectivity_bits {
 
     template <typename Digraph>
@@ -1054 +1055 @@
     typedef typename Graph::NodeIt NodeIt;
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
@@ -1096 +1097 @@
     checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
@@ -1137 +1138 @@
     checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
 
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
@@ -1157 +1158 @@
 
 
-  namespace _topology_bits {
+  namespace _connectivity_bits {
 
     template <typename Digraph, typename IntNodeMap>
@@ -1194 +1195 @@
   template <typename Digraph, typename NodeMap>
   void topologicalSort(const Digraph& graph, NodeMap& order) {
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     checkConcept<concepts::Digraph, Digraph>();
@@ -1225 +1226 @@
   /// that the given graph is DAG.
   ///
-  /// \param graph The graph. It must be directed and acyclic.
+  /// \param digraph The graph. It must be directed and acyclic.
   /// \retval order A readable - writable node map. The values will be set
   /// from 0 to the number of the nodes in the graph minus one. Each values
@@ -1235 +1236 @@
   /// \see dag
   template <typename Digraph, typename NodeMap>
-  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
-    using namespace _topology_bits;
+  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
+    using namespace _connectivity_bits;
 
     checkConcept<concepts::Digraph, Digraph>();
@@ -1246 +1247 @@
     typedef typename Digraph::Arc Arc;
 
-    order = constMap<Node, int, -1>();
+    for (NodeIt it(digraph); it != INVALID; ++it) {
+      order.set(it, -1);
+    }
 
     TopologicalSortVisitor<Digraph, NodeMap>
-      visitor(order, countNodes(graph));
+      visitor(order, countNodes(digraph));
 
     DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
-      dfs(graph, visitor);
+      dfs(digraph, visitor);
 
     dfs.init();
-    for (NodeIt it(graph); it != INVALID; ++it) {
+    for (NodeIt it(digraph); it != INVALID; ++it) {
       if (!dfs.reached(it)) {
         dfs.addSource(it);
         while (!dfs.emptyQueue()) {
-           Arc edge = dfs.nextArc();
-           Node target = graph.target(edge);
+           Arc arc = dfs.nextArc();
+           Node target = digraph.target(arc);
            if (dfs.reached(target) && order[target] == -1) {
              return false;
@@ -1280 +1283 @@
   /// \see acyclic
   template <typename Digraph>
-  bool dag(const Digraph& graph) {
+  bool dag(const Digraph& digraph) {
 
     checkConcept<concepts::Digraph, Digraph>();
@@ -1291 +1294 @@
 
     typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
-      Create dfs(graph);
-
-    ProcessedMap processed(graph);
+      Create dfs(digraph);
+
+    ProcessedMap processed(digraph);
     dfs.processedMap(processed);
 
     dfs.init();
-    for (NodeIt it(graph); it != INVALID; ++it) {
+    for (NodeIt it(digraph); it != INVALID; ++it) {
       if (!dfs.reached(it)) {
         dfs.addSource(it);
         while (!dfs.emptyQueue()) {
           Arc edge = dfs.nextArc();
-          Node target = graph.target(edge);
+          Node target = digraph.target(edge);
           if (dfs.reached(target) && !processed[target]) {
             return false;
@@ -1381 +1384 @@
   }
 
-  namespace _topology_bits {
+  namespace _connectivity_bits {
 
     template <typename Digraph>
@@ -1450 +1453 @@
   template<typename Graph>
   inline bool bipartite(const Graph &graph){
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     checkConcept<concepts::Graph, Graph>();
@@ -1490 +1493 @@
   template<typename Graph, typename NodeMap>
   inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
-    using namespace _topology_bits;
+    using namespace _connectivity_bits;
 
     checkConcept<concepts::Graph, Graph>();
@@ -1521 +1524 @@
   /// Returns true when there are not loop edges in the graph.
   template <typename Digraph>
-  bool loopFree(const Digraph& graph) {
-    for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
-      if (graph.source(it) == graph.target(it)) return false;
+  bool loopFree(const Digraph& digraph) {
+    for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
+      if (digraph.source(it) == digraph.target(it)) return false;
     }
     return true;
@@ -1532 +1535 @@
   /// Returns true when there are not parallel edges in the graph.
   template <typename Digraph>
-  bool parallelFree(const Digraph& graph) {
-    typename Digraph::template NodeMap<bool> reached(graph, false);
-    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
-      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
-        if (reached[graph.target(e)]) return false;
-        reached.set(graph.target(e), true);
-      }
-      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
-        reached.set(graph.target(e), false);
+  bool parallelFree(const Digraph& digraph) {
+    typename Digraph::template NodeMap<bool> reached(digraph, false);
+    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
+      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
+        if (reached[digraph.target(a)]) return false;
+        reached.set(digraph.target(a), true);
+      }
+      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
+        reached.set(digraph.target(a), false);
       }
     }
@@ -1552 +1555 @@
   /// the graph.
   template <typename Digraph>
-  bool simpleDigraph(const Digraph& graph) {
-    typename Digraph::template NodeMap<bool> reached(graph, false);
-    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
+  bool simpleDigraph(const Digraph& digraph) {
+    typename Digraph::template NodeMap<bool> reached(digraph, false);
+    for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
       reached.set(n, true);
-      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
-        if (reached[graph.target(e)]) return false;
-        reached.set(graph.target(e), true);
-      }
-      for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
-        reached.set(graph.target(e), false);
+      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
+        if (reached[digraph.target(a)]) return false;
+        reached.set(digraph.target(a), true);
+      }
+      for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
+        reached.set(digraph.target(a), false);
       }
       reached.set(n, false);
@@ -1570 +1573 @@
 } //namespace lemon
 
-#endif //LEMON_TOPOLOGY_H
+#endif //LEMON_CONNECTIVITY_H

lemon/dfs.h

@@ -1411 +1411 @@
           } else {
             _visitor->leave(s);
+            _visitor->stop(s);
           }
         }
@@ -1626 +1627 @@
     /// \pre Either \ref run(Node) "run()" or \ref init()
     /// must be called before using this function.
-    bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
 
     ///@}

lemon/max_matching.h

@@ -417 +417 @@
     /// \ref init(), \ref greedyInit() or \ref matchingInit()
     /// functions first, then you can start the algorithm with the \ref
-    /// startParse() or startDense() functions.
+    /// startSparse() or startDense() functions.
 
     ///@{

lemon/preflow.h

@@ -367 +367 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    const Elevator& elevator() {
+    const Elevator& elevator() const {
       return *_level;
     }
@@ -919 +919 @@
     /// \pre Either \ref run() or \ref init() must be called before
     /// using this function.
-    const FlowMap& flowMap() {
+    const FlowMap& flowMap() const {
       return *_flow;
     }

lemon/suurballe.h

@@ -52 +52 @@
   ///
   /// \note For finding node-disjoint paths this algorithm can be used
-  /// with \ref SplitDigraphAdaptor.
+  /// with \ref SplitNodes.
 #ifdef DOXYGEN
   template <typename Digraph, typename LengthMap>

scripts/chg-len.py

@@ -4 +4 @@
 
 from mercurial import ui, hg
+from mercurial import util
+
+util.rcpath = lambda : []
 
 if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:

test/CMakeLists.txt

@@ -5 +5 @@
 SET(TESTS
   bfs_test
+  circulation_test
   counter_test
   dfs_test
@@ -11 +12 @@
   dim_test
   error_test
+  graph_adaptor_test
   graph_copy_test
   graph_test
@@ -19 +21 @@
   maps_test
   max_matching_test
+  path_test
+  preflow_test
   random_test
-  path_test
+  suurballe_test
   time_measure_test
   unionfind_test)

test/Makefile.am

@@ -1 +1 @@
 EXTRA_DIST += \
-        test/CMakeLists.txt \
-        test/min_cost_flow_test.lgf \
-        test/preflow_graph.lgf
+        test/CMakeLists.txt
 
 noinst_HEADERS += \
@@ -21 +19 @@
         test/graph_test \
         test/graph_utils_test \
+        test/hao_orlin_test \
         test/heap_test \
         test/kruskal_test \
-        test/hao_orlin_test \
         test/maps_test \
         test/max_matching_test \
-        test/random_test \
         test/path_test \
         test/preflow_test \
+        test/random_test \
         test/suurballe_test \
         test/test_tools_fail \

test/preflow_test.cc

@@ -17 +17 @@
  */
 
-#include <fstream>
-#include <string>
+#include <iostream>
 
 #include "test_tools.h"
@@ -29 +28 @@
 
 using namespace lemon;
+
+char test_lgf[] =
+  "@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"
+  "    label capacity\n"
+  "0 1 0     20\n"
+  "0 2 1     0\n"
+  "1 1 2     3\n"
+  "1 2 3     8\n"
+  "1 3 4     8\n"
+  "2 5 5     5\n"
+  "3 2 6     5\n"
+  "3 5 7     5\n"
+  "3 6 8     5\n"
+  "4 3 9     3\n"
+  "5 7 10    3\n"
+  "5 6 11    10\n"
+  "5 8 12    10\n"
+  "6 8 13    8\n"
+  "8 9 14    20\n"
+  "8 1 15    5\n"
+  "9 5 16    5\n"
+  "@attributes\n"
+  "source 1\n"
+  "target 8\n";
 
 void checkPreflowCompile()
@@ -124 +159 @@
   typedef Preflow<Digraph, CapMap> PType;
 
-  std::string f_name;
-  if( getenv("srcdir") )
-    f_name = std::string(getenv("srcdir"));
-  else f_name = ".";
-  f_name += "/test/preflow_graph.lgf";
-
-  std::ifstream file(f_name.c_str());
-
-  check(file, "Input file '" << f_name << "' not found.");
-
   Digraph g;
   Node s, t;
   CapMap cap(g);
-  DigraphReader<Digraph>(g,file).
+  std::istringstream input(test_lgf);
+  DigraphReader<Digraph>(g,input).
     arcMap("capacity", cap).
     node("source",s).

test/suurballe_test.cc

@@ -18 +18 @@
 
 #include <iostream>
-#include <fstream>
 
 #include <lemon/list_graph.h>
@@ -28 +27 @@
 
 using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label supply1 supply2 supply3\n"
+  "1     0        20      27\n"
+  "2     0       -4        0\n"
+  "3     0        0        0\n"
+  "4     0        0        0\n"
+  "5     0        9        0\n"
+  "6     0       -6        0\n"
+  "7     0        0        0\n"
+  "8     0        0        0\n"
+  "9     0        3        0\n"
+  "10    0       -2        0\n"
+  "11    0        0        0\n"
+  "12    0       -20     -27\n"
+  "@arcs\n"
+  "      cost capacity lower1 lower2\n"
+  " 1  2  70  11       0      8\n"
+  " 1  3 150   3       0      1\n"
+  " 1  4  80  15       0      2\n"
+  " 2  8  80  12       0      0\n"
+  " 3  5 140   5       0      3\n"
+  " 4  6  60  10       0      1\n"
+  " 4  7  80   2       0      0\n"
+  " 4  8 110   3       0      0\n"
+  " 5  7  60  14       0      0\n"
+  " 5 11 120  12       0      0\n"
+  " 6  3   0   3       0      0\n"
+  " 6  9 140   4       0      0\n"
+  " 6 10  90   8       0      0\n"
+  " 7  1  30   5       0      0\n"
+  " 8 12  60  16       0      4\n"
+  " 9 12  50   6       0      0\n"
+  "10 12  70  13       0      5\n"
+  "10  2 100   7       0      0\n"
+  "10  7  60  10       0      0\n"
+  "11 10  20  14       0      6\n"
+  "12 11  30  10       0      0\n"
+  "@attributes\n"
+  "source  1\n"
+  "target 12\n"
+  "@end\n";
 
 // Check the feasibility of the flow
@@ -97 +139 @@
   Node source, target;
 
-  std::string fname;
-  if(getenv("srcdir"))
-    fname = std::string(getenv("srcdir"));
-  else fname = ".";
-  fname += "/test/min_cost_flow_test.lgf";
-
-  std::ifstream input(fname.c_str());
-  check(input, "Input file '" << fname << "' not found");
+  std::istringstream input(test_lgf);
   DigraphReader<ListDigraph>(digraph, input).
     arcMap("cost", length).
@@ -110 +145 @@
     node("target", target).
     run();
-  input.close();
   
   // Find 2 paths