1.1 --- a/src/work/bfs_iterator.hh Mon Mar 01 17:34:37 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Tue Mar 02 14:51:13 2004 +0000
1.3 @@ -542,16 +542,25 @@
1.4 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
1.5 };
1.6
1.7 - template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.8 +
1.9 + template <typename Graph, typename OutEdgeIt,
1.10 + typename ReachedMap=typename Graph::NodeMap<bool> >
1.11 class BfsIterator4 {
1.12 typedef typename Graph::NodeIt NodeIt;
1.13 const Graph& G;
1.14 std::queue<NodeIt> bfs_queue;
1.15 - ReachedMap reached;
1.16 + ReachedMap& reached;
1.17 bool b_node_newly_reached;
1.18 OutEdgeIt actual_edge;
1.19 + bool own_reached_map;
1.20 public:
1.21 - BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
1.22 + BfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.23 + G(_G), reached(_reached),
1.24 + own_reached_map(false) { }
1.25 + BfsIterator4(const Graph& _G) :
1.26 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.27 + own_reached_map(true) { }
1.28 + ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.29 void pushAndSetReached(NodeIt s) {
1.30 reached.set(s, true);
1.31 if (bfs_queue.empty()) {
1.32 @@ -611,38 +620,27 @@
1.33 NodeIt bNode() const { return G.bNode(actual_edge); }
1.34 const ReachedMap& getReachedMap() const { return reached; }
1.35 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.36 - };
1.37 + };
1.38
1.39 -
1.40 - template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.41 - struct DfsIterator4 {
1.42 + template <typename Graph, typename OutEdgeIt,
1.43 + typename ReachedMap=typename Graph::NodeMap<bool> >
1.44 + class DfsIterator4 {
1.45 typedef typename Graph::NodeIt NodeIt;
1.46 const Graph& G;
1.47 std::stack<OutEdgeIt> dfs_stack;
1.48 - //ReachedMap& reached;
1.49 bool b_node_newly_reached;
1.50 OutEdgeIt actual_edge;
1.51 NodeIt actual_node;
1.52 - ReachedMap reached;
1.53 - DfsIterator4(const Graph& _G
1.54 - /*, std::stack<OutEdgeIt>& _bfs_queue,
1.55 - ReachedMap& _reached*/) :
1.56 - G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ {
1.57 - //actual_edge=bfs_queue.top();
1.58 - //if (actual_edge.valid()) {
1.59 - // NodeIt w=G.bNode(actual_edge);
1.60 - //if (!reached.get(w)) {
1.61 - // bfs_queue.push(OutEdgeIt(G, w));
1.62 - // reached.set(w, true);
1.63 - // b_node_newly_reached=true;
1.64 - //} else {
1.65 - // ++(bfs_queue.top());
1.66 - // b_node_newly_reached=false;
1.67 - //}
1.68 - //} else {
1.69 - // bfs_queue.pop();
1.70 - //}
1.71 - }
1.72 + ReachedMap& reached;
1.73 + bool own_reached_map;
1.74 + public:
1.75 + DfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.76 + G(_G), reached(_reached),
1.77 + own_reached_map(false) { }
1.78 + DfsIterator4(const Graph& _G) :
1.79 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.80 + own_reached_map(true) { }
1.81 + ~DfsIterator4() { if (own_reached_map) delete &reached; }
1.82 void pushAndSetReached(NodeIt s) {
1.83 actual_node=s;
1.84 reached.set(s, true);
2.1 --- a/src/work/marci/edmonds_karp_demo.cc Mon Mar 01 17:34:37 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp_demo.cc Tue Mar 02 14:51:13 2004 +0000
2.3 @@ -54,19 +54,21 @@
2.4 std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
2.5 ListGraph::EdgeMap<int> flow(G); //0 flow
2.6
2.7 - double pre_time=currTime();
2.8 + Timer ts;
2.9 + ts.reset();
2.10 + //double pre_time=currTime();
2.11 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.12 //max_flow_test.augmentWithBlockingFlow<ListGraph>();
2.13 int i=0;
2.14 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
2.15 - double post_time=currTime();
2.16 + //double post_time=currTime();
2.17
2.18 //std::cout << "maximum flow: "<< std::endl;
2.19 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
2.20 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.21 //}
2.22 //std::cout<<std::endl;
2.23 - std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
2.24 + std::cout << "elapsed time: " << ts << std::endl;
2.25 std::cout << "number of augmentation phases: " << i << std::endl;
2.26 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.27 }
2.28 @@ -75,19 +77,21 @@
2.29 std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
2.30 ListGraph::EdgeMap<int> flow(G); //0 flow
2.31
2.32 - double pre_time=currTime();
2.33 + Timer ts;
2.34 + ts.reset();
2.35 + //double pre_time=currTime();
2.36 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
2.37 //max_flow_test.augmentWithBlockingFlow<ListGraph>();
2.38 int i=0;
2.39 while (max_flow_test.augmentOnShortestPath()) { ++i; }
2.40 - double post_time=currTime();
2.41 + //double post_time=currTime();
2.42
2.43 //std::cout << "maximum flow: "<< std::endl;
2.44 //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
2.45 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
2.46 //}
2.47 //std::cout<<std::endl;
2.48 - std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
2.49 + std::cout << "elapsed time: " << ts << std::endl;
2.50 std::cout << "number of augmentation phases: " << i << std::endl;
2.51 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.52 }