Changeset 777:a82713ed19f3 in lemon-0.x for src/work/marci/bfs_dfs.h

Timestamp:

08/31/04 19:54:22 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

graph_wrapper.h is ready for hugo 0.2

File:

• src/work/marci/bfs_dfs.h (modified) (19 diffs)

src/work/marci/bfs_dfs.h

@@ -28 +28 @@
   protected:
     typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     const Graph* graph;
@@ -33 +34 @@
     ReachedMap& reached;
     bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
+    Edge actual_edge;
     bool own_reached_map;
   public:
@@ -56 +57 @@
     /// and the first out-edge is processed.
     /// If the queue is not empty, then \c s is simply pushed.
-    void pushAndSetReached(Node s) { 
+    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
       reached.set(s, true);
       if (bfs_queue.empty()) {
         bfs_queue.push(s);
-        graph->first(actual_edge, s);
+        actual_edge=OutEdgeIt(*graph, s);
+        //graph->first(actual_edge, s);
         if (actual_edge!=INVALID) { 
           Node w=graph->head(actual_edge);
@@ -74 +76 @@
         bfs_queue.push(s);
       }
+      return *this;
     }
     /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
@@ -80 +83 @@
     operator++() { 
       if (actual_edge!=INVALID) { 
-        ++actual_edge;
+        actual_edge=++OutEdgeIt(*graph, actual_edge);
+        //++actual_edge;
         if (actual_edge!=INVALID) {
           Node w=graph->head(actual_edge);
@@ -94 +98 @@
         bfs_queue.pop(); 
         if (!bfs_queue.empty()) {
-          graph->first(actual_edge, bfs_queue.front());
+          actual_edge=OutEdgeIt(*graph, bfs_queue.front());
+          //graph->first(actual_edge, bfs_queue.front());
           if (actual_edge!=INVALID) {
             Node w=graph->head(actual_edge);
@@ -114 +119 @@
     /// to an \c out-edge-iterator.
     ///\bug Edge have to be in HUGO 0.2
-    operator OutEdgeIt() const { return actual_edge; }
+    operator Edge() const { return actual_edge; }
     /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -120 +125 @@
     bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
-    Node aNode() const { return bfs_queue.front(); }
+    Node tail() const { return bfs_queue.front(); }
     /// \pre The actual edge have to be valid.
-    Node bNode() const { return graph->bNode(actual_edge); }
+    Node head() const { return graph->head(actual_edge); }
     /// Guess what?
     /// \deprecated 
@@ -160 +165 @@
     /// in addition its pred is set to be \c INVALID, and dist to \c 0. 
     /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
+    Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) { 
       if (this->reached[s]) {
         Parent::pushAndSetReached(s);
@@ -168 +173 @@
         dist.set(s, 0);
       }
+      return *this;
     }
     /// A bfs is processed from \c s.
-    void run(Node s) {
+    Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
       push(s);
       while (!this->finished()) this->operator++();
+      return *this;
     }
     /// Beside the bfs iteration, \c pred and \dist are saved in a 
@@ -180 +187 @@
       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
       {
-        pred.set(this->bNode(), this->actual_edge);
-        dist.set(this->bNode(), dist[this->aNode()]);
+        pred.set(this->head(), this->actual_edge);
+        dist.set(this->head(), dist[this->tail()]);
       }
       return *this;
@@ -202 +209 @@
   protected:
     typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     const Graph* graph;
     std::stack<OutEdgeIt> dfs_stack;
     bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
+    Edge actual_edge;
     Node actual_node;
     ReachedMap& reached;
@@ -225 +233 @@
     ~DfsIterator() { if (own_reached_map) delete &reached; }
     /// This method markes s reached and first out-edge is processed.
-    void pushAndSetReached(Node s) { 
+    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { 
       actual_node=s;
       reached.set(s, true);
-      OutEdgeIt e;
-      graph->first(e, s);
+      OutEdgeIt e(*graph, s);
+      //graph->first(e, s);
       dfs_stack.push(e); 
+      return *this;
     }
     /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
@@ -237 +246 @@
     operator++() { 
       actual_edge=dfs_stack.top();
-      //actual_node=G.aNode(actual_edge);
       if (actual_edge!=INVALID/*.valid()*/) { 
         Node w=graph->head(actual_edge);
         actual_node=w;
         if (!reached[w]) {
-          OutEdgeIt e;
-          graph->first(e, w);
+          OutEdgeIt e(*graph, w);
+          //graph->first(e, w);
           dfs_stack.push(e);
           reached.set(w, true);
@@ -263 +271 @@
     /// to an \c out-edge-iterator.
     ///\bug Edge have to be in HUGO 0.2
-    operator OutEdgeIt() const { return actual_edge; }
+    operator Edge() const { return actual_edge; }
     /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -269 +277 @@
     bool isANodeExamined() const { return actual_edge==INVALID; }
     /// Returns a-node of the actual edge, so does if the edge is invalid.
-    Node aNode() const { return actual_node; /*FIXME*/}
+    Node tail() const { return actual_node; /*FIXME*/}
     /// Returns b-node of the actual edge. 
     /// \pre The actual edge have to be valid.
-    Node bNode() const { return graph->bNode(actual_edge); }
+    Node head() const { return graph->head(actual_edge); }
     /// Guess what?
     /// \deprecated
@@ -305 +313 @@
     /// in addition its pred is set to be \c INVALID. 
     /// if \c s was marked previuosly, then it is simply pushed.
-    void push(Node s) { 
+    Dfs<Graph, ReachedMap, PredMap>& push(Node s) { 
       if (this->reached[s]) {
         Parent::pushAndSetReached(s);
@@ -312 +320 @@
         pred.set(s, INVALID);
       }
+      return *this;
     }
     /// A bfs is processed from \c s.
-    void run(Node s) {
+    Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
       push(s);
       while (!this->finished()) this->operator++();
+      return *this;
     }
     /// Beside the dfs iteration, \c pred is saved in a 
@@ -324 +334 @@
       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
       {
-        pred.set(this->bNode(), this->actual_edge);
+        pred.set(this->head(), this->actual_edge);
       }
       return *this;