# HG changeset patch # User marci # Date 1078239073 0 # Node ID a1323efc5753829d5ed5bbf9a2b44872e2091562 # Parent c1ec00df3b3abbc26cf4d405525680fff2d1172b BfsIterator4, DfsIterator4 extension diff -r c1ec00df3b3a -r a1323efc5753 src/work/bfs_iterator.hh --- a/src/work/bfs_iterator.hh Mon Mar 01 17:34:37 2004 +0000 +++ b/src/work/bfs_iterator.hh Tue Mar 02 14:51:13 2004 +0000 @@ -542,16 +542,25 @@ //const std::queue< std::pair >& getBfsQueue() const { return bfs_queue; } }; - template + + template > class BfsIterator4 { typedef typename Graph::NodeIt NodeIt; const Graph& G; std::queue bfs_queue; - ReachedMap reached; + 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); if (bfs_queue.empty()) { @@ -611,38 +620,27 @@ NodeIt bNode() const { return G.bNode(actual_edge); } const ReachedMap& getReachedMap() const { return reached; } const std::queue& getBfsQueue() const { return bfs_queue; } - }; + }; - - template - struct DfsIterator4 { + template > + class DfsIterator4 { typedef typename Graph::NodeIt NodeIt; const Graph& G; std::stack dfs_stack; - //ReachedMap& reached; bool b_node_newly_reached; OutEdgeIt actual_edge; NodeIt actual_node; - ReachedMap reached; - DfsIterator4(const Graph& _G - /*, std::stack& _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; reached.set(s, true); diff -r c1ec00df3b3a -r a1323efc5753 src/work/marci/edmonds_karp_demo.cc --- a/src/work/marci/edmonds_karp_demo.cc Mon Mar 01 17:34:37 2004 +0000 +++ b/src/work/marci/edmonds_karp_demo.cc Tue Mar 02 14:51:13 2004 +0000 @@ -54,19 +54,21 @@ std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl; ListGraph::EdgeMap flow(G); //0 flow - double pre_time=currTime(); + Timer ts; + ts.reset(); + //double pre_time=currTime(); MaxFlow, ListGraph::EdgeMap > max_flow_test(G, s, t, flow, cap); //max_flow_test.augmentWithBlockingFlow(); int i=0; while (max_flow_test.augmentOnBlockingFlow()) { ++i; } - double post_time=currTime(); + //double post_time=currTime(); //std::cout << "maximum flow: "<< std::endl; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { // std::cout<<"("<"< flow(G); //0 flow - double pre_time=currTime(); + Timer ts; + ts.reset(); + //double pre_time=currTime(); MaxFlow, ListGraph::EdgeMap > max_flow_test(G, s, t, flow, cap); //max_flow_test.augmentWithBlockingFlow(); int i=0; while (max_flow_test.augmentOnShortestPath()) { ++i; } - double post_time=currTime(); + //double post_time=currTime(); //std::cout << "maximum flow: "<< std::endl; //for(EachEdgeIt e=G.first(); e.valid(); ++e) { // std::cout<<"("<"<