Changeset 144:a1323efc5753 in lemon0.x for src/work
 Timestamp:
 03/02/04 15:51:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@199
 Location:
 src/work
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r133 r144 543 543 }; 544 544 545 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 545 546 template <typename Graph, typename OutEdgeIt, 547 typename ReachedMap=typename Graph::NodeMap<bool> > 546 548 class BfsIterator4 { 547 549 typedef typename Graph::NodeIt NodeIt; 548 550 const Graph& G; 549 551 std::queue<NodeIt> bfs_queue; 550 ReachedMap reached; 551 bool b_node_newly_reached; 552 OutEdgeIt actual_edge; 552 ReachedMap& reached; 553 bool b_node_newly_reached; 554 OutEdgeIt actual_edge; 555 bool own_reached_map; 553 556 public: 554 BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { } 557 BfsIterator4(const Graph& _G, ReachedMap& _reached) : 558 G(_G), reached(_reached), 559 own_reached_map(false) { } 560 BfsIterator4(const Graph& _G) : 561 G(_G), reached(*(new ReachedMap(G /*, false*/))), 562 own_reached_map(true) { } 563 ~BfsIterator4() { if (own_reached_map) delete &reached; } 555 564 void pushAndSetReached(NodeIt s) { 556 565 reached.set(s, true); … … 612 621 const ReachedMap& getReachedMap() const { return reached; } 613 622 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 614 }; 615 616 617 template <typename Graph, typename OutEdgeIt, typename ReachedMap>618 structDfsIterator4 {623 }; 624 625 template <typename Graph, typename OutEdgeIt, 626 typename ReachedMap=typename Graph::NodeMap<bool> > 627 class DfsIterator4 { 619 628 typedef typename Graph::NodeIt NodeIt; 620 629 const Graph& G; 621 630 std::stack<OutEdgeIt> dfs_stack; 622 //ReachedMap& reached;623 631 bool b_node_newly_reached; 624 632 OutEdgeIt actual_edge; 625 633 NodeIt actual_node; 626 ReachedMap reached; 627 DfsIterator4(const Graph& _G 628 /*, std::stack<OutEdgeIt>& _bfs_queue, 629 ReachedMap& _reached*/) : 630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 631 //actual_edge=bfs_queue.top(); 632 //if (actual_edge.valid()) { 633 // NodeIt w=G.bNode(actual_edge); 634 //if (!reached.get(w)) { 635 // bfs_queue.push(OutEdgeIt(G, w)); 636 // reached.set(w, true); 637 // b_node_newly_reached=true; 638 //} else { 639 // ++(bfs_queue.top()); 640 // b_node_newly_reached=false; 641 //} 642 //} else { 643 // bfs_queue.pop(); 644 //} 645 } 634 ReachedMap& reached; 635 bool own_reached_map; 636 public: 637 DfsIterator4(const Graph& _G, ReachedMap& _reached) : 638 G(_G), reached(_reached), 639 own_reached_map(false) { } 640 DfsIterator4(const Graph& _G) : 641 G(_G), reached(*(new ReachedMap(G /*, false*/))), 642 own_reached_map(true) { } 643 ~DfsIterator4() { if (own_reached_map) delete &reached; } 646 644 void pushAndSetReached(NodeIt s) { 647 645 actual_node=s; 
src/work/marci/edmonds_karp_demo.cc
r139 r144 55 55 ListGraph::EdgeMap<int> flow(G); //0 flow 56 56 57 double pre_time=currTime(); 57 Timer ts; 58 ts.reset(); 59 //double pre_time=currTime(); 58 60 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 59 61 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 60 62 int i=0; 61 63 while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; } 62 double post_time=currTime();64 //double post_time=currTime(); 63 65 64 66 //std::cout << "maximum flow: "<< std::endl; … … 67 69 //} 68 70 //std::cout<<std::endl; 69 std::cout << "elapsed time: " << post_timepre_time << " sec"<< std::endl;71 std::cout << "elapsed time: " << ts << std::endl; 70 72 std::cout << "number of augmentation phases: " << i << std::endl; 71 73 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; … … 76 78 ListGraph::EdgeMap<int> flow(G); //0 flow 77 79 78 double pre_time=currTime(); 80 Timer ts; 81 ts.reset(); 82 //double pre_time=currTime(); 79 83 MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap); 80 84 //max_flow_test.augmentWithBlockingFlow<ListGraph>(); 81 85 int i=0; 82 86 while (max_flow_test.augmentOnShortestPath()) { ++i; } 83 double post_time=currTime();87 //double post_time=currTime(); 84 88 85 89 //std::cout << "maximum flow: "<< std::endl; … … 88 92 //} 89 93 //std::cout<<std::endl; 90 std::cout << "elapsed time: " << post_timepre_time << " sec"<< std::endl;94 std::cout << "elapsed time: " << ts << std::endl; 91 95 std::cout << "number of augmentation phases: " << i << std::endl; 92 96 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
Note: See TracChangeset
for help on using the changeset viewer.