Changes in / [421:0f2091856dab:420:6a2a33ad261b] in lemon-1.2

Location:

lemon

Files:

• connectivity.h (modified) (31 diffs)
• dfs.h (modified) (1 diff)

lemon/connectivity.h

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

lemon/dfs.h

@@ -1411 +1411 @@
           } else {
             _visitor->leave(s);
-            _visitor->stop(s);
           }
         }