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

Timestamp:

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

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

BfsIterator4, DfsIterator4 extension

Location:

src/work

Files:

• bfs_iterator.hh (modified) (2 diffs)
• marci/edmonds_karp_demo.cc (modified) (4 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;

src/work/marci/edmonds_karp_demo.cc

@@ -55 +55 @@
   ListGraph::EdgeMap<int> flow(G); //0 flow
 
-  double pre_time=currTime();
+  Timer ts;
+  ts.reset();
+  //double pre_time=currTime();
   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
-  double post_time=currTime();
+  //double post_time=currTime();
 
   //std::cout << "maximum flow: "<< std::endl;
@@ -67 +69 @@
   //}
   //std::cout<<std::endl;
-  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
+  std::cout << "elapsed time: " << ts << std::endl;
   std::cout << "number of augmentation phases: " << i << std::endl; 
   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
@@ -76 +78 @@
   ListGraph::EdgeMap<int> flow(G); //0 flow
 
-  double pre_time=currTime();
+  Timer ts;
+  ts.reset();
+  //double pre_time=currTime();
   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
   int i=0;
   while (max_flow_test.augmentOnShortestPath()) { ++i; }
-  double post_time=currTime();
+  //double post_time=currTime();
 
   //std::cout << "maximum flow: "<< std::endl;
@@ -88 +92 @@
   //}
   //std::cout<<std::endl;
-  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
+  std::cout << "elapsed time: " << ts << std::endl;
   std::cout << "number of augmentation phases: " << i << std::endl; 
   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;