Changeset 419:9afe81e4c543 in lemon-main

Timestamp:

12/03/08 14:23:22 (16 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Renamings in connectivity.h and bug fix in DfsVisit? (#61)

• The include guard, the private namespace and some local varibles are renamed
• The stop() must be called in DfsVisit?, if there are not outgoing arcs from the added node

Location:

lemon

Files:

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

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;
@@ -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>();
@@ -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);
           }
         }