Changeset 303:1b377a730d02 in lemon-0.x for src/work/marci/bfs_iterator.h

Timestamp:

04/05/04 18:52:46 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@421

Message:

konvergalunk, konvergalunk...

File:

• src/work/marci/bfs_iterator.h (modified) (11 diffs)

src/work/marci/bfs_iterator.h

@@ -6 +6 @@
 #include <stack>
 #include <utility>
-#include <graph_wrapper.h>
 
 namespace hugo {
@@ -631 +630 @@
 
 
-  template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
-            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
+  template <typename Graph, /*typename OutEdgeIt,*/ 
+            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   class BfsIterator5 {
-    typedef typename GraphWrapper::Node Node;
-    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
-    GraphWrapper G;
+  protected:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    const Graph* graph;
     std::queue<Node> bfs_queue;
     ReachedMap& reached;
@@ -643 +643 @@
     bool own_reached_map;
   public:
-    BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
+    BfsIterator5(const Graph& _graph, ReachedMap& _reached) : 
+      graph(&_graph), reached(_reached), 
       own_reached_map(false) { }
-    BfsIterator5(const GraphWrapper& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+    BfsIterator5(const Graph& _graph) : 
+      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
       own_reached_map(true) { }
-//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G, 
-//               ReachedMap& _reached) : 
-//       G(_G), reached(_reached), 
-//       own_reached_map(false) { }
-//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : 
-//       G(_G), reached(*(new ReachedMap(G /*, false*/))), 
-//       own_reached_map(true) { }
     ~BfsIterator5() { if (own_reached_map) delete &reached; }
     void pushAndSetReached(Node s) { 
@@ -661 +654 @@
       if (bfs_queue.empty()) {
         bfs_queue.push(s);
-        G./*getF*/first(actual_edge, s);
-        if (G.valid(actual_edge)/*.valid()*/) { 
-          Node w=G.bNode(actual_edge);
-          if (!reached.get(w)) {
+        graph->first(actual_edge, s);
+        if (graph->valid(actual_edge)) { 
+          Node w=graph->bNode(actual_edge);
+          if (!reached[w]) {
             bfs_queue.push(w);
             reached.set(w, true);
@@ -676 +669 @@
       }
     }
-    BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
+    BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
-      if (G.valid(actual_edge)/*.valid()*/) { 
-        /*++*/G.next(actual_edge);
-        if (G.valid(actual_edge)/*.valid()*/) {
-          Node w=G.bNode(actual_edge);
-          if (!reached.get(w)) {
+      if (graph->valid(actual_edge)) { 
+        graph->next(actual_edge);
+        if (graph->valid(actual_edge)) {
+          Node w=graph->bNode(actual_edge);
+          if (!reached[w]) {
             bfs_queue.push(w);
             reached.set(w, true);
@@ -693 +686 @@
         bfs_queue.pop(); 
         if (!bfs_queue.empty()) {
-          G./*getF*/first(actual_edge, bfs_queue.front());
-          if (G.valid(actual_edge)/*.valid()*/) {
-            Node w=G.bNode(actual_edge);
-            if (!reached.get(w)) {
+          graph->first(actual_edge, bfs_queue.front());
+          if (graph->valid(actual_edge)) {
+            Node w=graph->bNode(actual_edge);
+            if (!reached[w]) {
               bfs_queue.push(w);
               reached.set(w, true);
@@ -711 +704 @@
     operator OutEdgeIt () const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     Node aNode() const { return bfs_queue.front(); }
-    Node bNode() const { return G.bNode(actual_edge); }
+    Node bNode() const { return graph->bNode(actual_edge); }
     const ReachedMap& getReachedMap() const { return reached; }
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
@@ -774 +767 @@
 //   };
 
-  template <typename GraphWrapper, /*typename OutEdgeIt,*/ 
-            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
+  template <typename Graph, /*typename OutEdgeIt,*/ 
+            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   class DfsIterator5 {
-    typedef typename GraphWrapper::Node Node;
-    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
-    GraphWrapper G;
+  protected:
+    typedef typename Graph::Node Node;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    const Graph* graph;
     std::stack<OutEdgeIt> dfs_stack;
     bool b_node_newly_reached;
@@ -787 +781 @@
     bool own_reached_map;
   public:
-    DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 
-      G(_G), reached(_reached), 
+    DfsIterator5(const Graph& _graph, ReachedMap& _reached) : 
+      graph(&_graph), reached(_reached), 
       own_reached_map(false) { }
-    DfsIterator5(const GraphWrapper& _G) : 
-      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+    DfsIterator5(const Graph& _graph) : 
+      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
       own_reached_map(true) { }
     ~DfsIterator5() { if (own_reached_map) delete &reached; }
@@ -798 +792 @@
       reached.set(s, true);
       OutEdgeIt e;
-      G.first(e, s);
+      graph->first(e, s);
       dfs_stack.push(e); 
     }
-    DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& 
+    DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
       actual_edge=dfs_stack.top();
       //actual_node=G.aNode(actual_edge);
-      if (G.valid(actual_edge)/*.valid()*/) { 
-        Node w=G.bNode(actual_edge);
+      if (graph->valid(actual_edge)/*.valid()*/) { 
+        Node w=graph->bNode(actual_edge);
         actual_node=w;
-        if (!reached.get(w)) {
+        if (!reached[w]) {
           OutEdgeIt e;
-          G.first(e, w);
+          graph->first(e, w);
           dfs_stack.push(e);
           reached.set(w, true);
           b_node_newly_reached=true;
         } else {
-          actual_node=G.aNode(actual_edge);
-          /*++*/G.next(dfs_stack.top());
+          actual_node=graph->aNode(actual_edge);
+          graph->next(dfs_stack.top());
           b_node_newly_reached=false;
         }
@@ -828 +822 @@
     operator OutEdgeIt () const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
+    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
     Node aNode() const { return actual_node; /*FIXME*/}
     Node bNode() const { return G.bNode(actual_edge); }