COIN-OR::LEMON - Graph Library

Changeset 144:a1323efc5753 in lemon-0.x


Ignore:
Timestamp:
03/02/04 15:51:13 (16 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:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r133 r144  
    543543 };
    544544
    545   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
     545
     546  template <typename Graph, typename OutEdgeIt,
     547            typename ReachedMap=typename Graph::NodeMap<bool> >
    546548  class BfsIterator4 {
    547549    typedef typename Graph::NodeIt NodeIt;
    548550    const Graph& G;
    549551    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;
    553556  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; }
    555564    void pushAndSetReached(NodeIt s) {
    556565      reached.set(s, true);
     
    612621    const ReachedMap& getReachedMap() const { return reached; }
    613622    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
    614  };
    615 
    616 
    617   template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    618   struct DfsIterator4 {
     623 }; 
     624
     625  template <typename Graph, typename OutEdgeIt,
     626            typename ReachedMap=typename Graph::NodeMap<bool> >
     627  class DfsIterator4 {
    619628    typedef typename Graph::NodeIt NodeIt;
    620629    const Graph& G;
    621630    std::stack<OutEdgeIt> dfs_stack;
    622     //ReachedMap& reached;
    623631    bool b_node_newly_reached;
    624632    OutEdgeIt actual_edge;
    625633    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; }
    646644    void pushAndSetReached(NodeIt s) {
    647645      actual_node=s;
  • src/work/marci/edmonds_karp_demo.cc

    r139 r144  
    5555  ListGraph::EdgeMap<int> flow(G); //0 flow
    5656
    57   double pre_time=currTime();
     57  Timer ts;
     58  ts.reset();
     59  //double pre_time=currTime();
    5860  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    5961  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    6062  int i=0;
    6163  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
    62   double post_time=currTime();
     64  //double post_time=currTime();
    6365
    6466  //std::cout << "maximum flow: "<< std::endl;
     
    6769  //}
    6870  //std::cout<<std::endl;
    69   std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
     71  std::cout << "elapsed time: " << ts << std::endl;
    7072  std::cout << "number of augmentation phases: " << i << std::endl;
    7173  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     
    7678  ListGraph::EdgeMap<int> flow(G); //0 flow
    7779
    78   double pre_time=currTime();
     80  Timer ts;
     81  ts.reset();
     82  //double pre_time=currTime();
    7983  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    8084  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    8185  int i=0;
    8286  while (max_flow_test.augmentOnShortestPath()) { ++i; }
    83   double post_time=currTime();
     87  //double post_time=currTime();
    8488
    8589  //std::cout << "maximum flow: "<< std::endl;
     
    8892  //}
    8993  //std::cout<<std::endl;
    90   std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
     94  std::cout << "elapsed time: " << ts << std::endl;
    9195  std::cout << "number of augmentation phases: " << i << std::endl;
    9296  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
Note: See TracChangeset for help on using the changeset viewer.