Changeset 144:a1323efc5753 in lemon-0.x for src/work/bfs_iterator.hh

Timestamp:

03/02/04 15:51:13 (19 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

BfsIterator4, DfsIterator4 extension

File:

• src/work/bfs_iterator.hh (modified) (2 diffs)

src/work/bfs_iterator.hh

@@ -543 +543 @@
  };
 
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+
+  template <typename Graph, typename OutEdgeIt, 
+            typename ReachedMap=typename Graph::NodeMap<bool> >
   class BfsIterator4 {
     typedef typename Graph::NodeIt NodeIt;
     const Graph& G;
     std::queue<NodeIt> bfs_queue;
-    ReachedMap reached;
-    bool b_node_newly_reached;
-    OutEdgeIt actual_edge;
+    ReachedMap& reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+    bool own_reached_map;
   public:
-    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
+    BfsIterator4(const Graph& _G, ReachedMap& _reached) : 
+      G(_G), reached(_reached), 
+      own_reached_map(false) { }
+    BfsIterator4(const Graph& _G) : 
+      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+      own_reached_map(true) { }
+    ~BfsIterator4() { if (own_reached_map) delete &reached; }
     void pushAndSetReached(NodeIt s) { 
       reached.set(s, true);
@@ -612 +621 @@
     const ReachedMap& getReachedMap() const { return reached; }
     const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
- };
-
-
-  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
-  struct DfsIterator4 {
+ };  
+
+  template <typename Graph, typename OutEdgeIt, 
+            typename ReachedMap=typename Graph::NodeMap<bool> >
+  class DfsIterator4 {
     typedef typename Graph::NodeIt NodeIt;
     const Graph& G;
     std::stack<OutEdgeIt> dfs_stack;
-    //ReachedMap& reached;
     bool b_node_newly_reached;
     OutEdgeIt actual_edge;
     NodeIt actual_node;
-    ReachedMap reached;
-    DfsIterator4(const Graph& _G 
-                 /*, std::stack<OutEdgeIt>& _bfs_queue, 
-                   ReachedMap& _reached*/) : 
-      G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 
-      //actual_edge=bfs_queue.top();
-      //if (actual_edge.valid()) { 
-      //        NodeIt w=G.bNode(actual_edge);
-      //if (!reached.get(w)) {
-      //  bfs_queue.push(OutEdgeIt(G, w));
-      //  reached.set(w, true);
-      //  b_node_newly_reached=true;
-      //} else {
-      //  ++(bfs_queue.top());
-      //  b_node_newly_reached=false;
-      //}
-      //} else {
-      //        bfs_queue.pop();
-      //}
-    }
+    ReachedMap& reached;
+    bool own_reached_map;
+  public:
+    DfsIterator4(const Graph& _G, ReachedMap& _reached) : 
+      G(_G), reached(_reached), 
+      own_reached_map(false) { }
+    DfsIterator4(const Graph& _G) : 
+      G(_G), reached(*(new ReachedMap(G /*, false*/))), 
+      own_reached_map(true) { }
+    ~DfsIterator4() { if (own_reached_map) delete &reached; }
     void pushAndSetReached(NodeIt s) { 
       actual_node=s;