COIN-OR::LEMON - Graph Library

Changeset 133:0631992fe7a1 in lemon-0.x for src


Ignore:
Timestamp:
02/27/04 13:39:15 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@180
Message:

Dinits blocking flow added to edmonds_karp_demo.hh.

Location:
src/work
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r105 r133  
    645645    }
    646646    void pushAndSetReached(NodeIt s) {
     647      actual_node=s;
    647648      reached.set(s, true);
    648649      dfs_stack.push(G.template first<OutEdgeIt>(s));
     
    660661          b_node_newly_reached=true;
    661662        } else {
     663          actual_node=G.aNode(actual_edge);
    662664          ++(dfs_stack.top());
    663665          b_node_newly_reached=false;
     
    673675    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    674676    bool isANodeExamined() const { return !(actual_edge.valid()); }
    675     NodeIt aNode() const { return actual_node; }
     677    NodeIt aNode() const { return actual_node; /*FIXME*/}
    676678    NodeIt bNode() const { return G.bNode(actual_edge); }
    677679    const ReachedMap& getReachedMap() const { return reached; }
  • src/work/edmonds_karp.hh

    r127 r133  
    77
    88#include <bfs_iterator.hh>
    9 #include <time_measure.h>
     9//#include <time_measure.h>
    1010
    1111namespace hugo {
     
    282282    public:
    283283      EdgeIt() : out_or_in(1) { }
     284      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
    284285      Number free() const {
    285286        if (out_or_in) {
     
    298299        }
    299300      }
     301      void print() {
     302        if (out_or_in) {
     303          std::cout << "out ";
     304          if (out.valid())
     305            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
     306          else
     307            std::cout << "invalid";
     308        }
     309        else {
     310          std::cout << "in ";
     311          if (in.valid())
     312            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
     313          else
     314            std::cout << "invalid";
     315        }
     316        std::cout << std::endl;
     317      }
    300318    };
    301319
     
    309327        flow=&_flow;
    310328        capacity=&_capacity;
    311         out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     329        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     330        G->getFirst(out, v);
    312331        while( out.valid() && !(free()>0) ) { ++out; }
    313332        if (!out.valid()) {
    314333          out_or_in=0;
    315           in=/*resG->*/G->template first<OldInEdgeIt>(v);
     334          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
     335          G->getFirst(in, v);
    316336          while( in.valid() && !(free()>0) ) { ++in; }
    317337        }
     
    325345          if (!out.valid()) {
    326346            out_or_in=0;
    327             in=/*resG->*/G->template first<OldInEdgeIt>(v);
     347            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    328348            while( in.valid() && !(free()>0) ) { ++in; }
    329349          }
     
    336356    };
    337357
     358    class EachEdgeIt : public EdgeIt {
     359      typename Graph::EachNodeIt v;
     360    public:
     361      EachEdgeIt() { }
     362      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
     363      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
     364        G=&_G;
     365        flow=&_flow;
     366        capacity=&_capacity;
     367        out_or_in=1;
     368        G->getFirst(v);
     369        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
     370        while (out.valid() && !(free()>0) ) { ++out; }
     371        while (v.valid() && !out.valid()) {
     372          ++v;
     373          if (v.valid()) G->getFirst(out, v);
     374          while (out.valid() && !(free()>0) ) { ++out; }
     375        }
     376        if (!out.valid()) {
     377          out_or_in=0;
     378          G->getFirst(v);
     379          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     380          while (in.valid() && !(free()>0) ) { ++in; }
     381          while (v.valid() && !in.valid()) {
     382            ++v;
     383            if (v.valid()) G->getFirst(in, v);
     384            while (in.valid() && !(free()>0) ) { ++in; }
     385          }
     386        }
     387      }
     388      EachEdgeIt& operator++() {
     389        if (out_or_in) {
     390          ++out;
     391          while (out.valid() && !(free()>0) ) { ++out; }
     392          while (v.valid() && !out.valid()) {
     393            ++v;
     394            if (v.valid()) G->getFirst(out, v);
     395            while (out.valid() && !(free()>0) ) { ++out; }
     396          }
     397          if (!out.valid()) {
     398            out_or_in=0;
     399            G->getFirst(v);
     400            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     401            while (in.valid() && !(free()>0) ) { ++in; }
     402            while (v.valid() && !in.valid()) {
     403              ++v;
     404              if (v.valid()) G->getFirst(in, v);
     405              while (in.valid() && !(free()>0) ) { ++in; }
     406            } 
     407          }
     408        } else {
     409          ++in;
     410          while (in.valid() && !(free()>0) ) { ++in; }
     411          while (v.valid() && !in.valid()) {
     412            ++v;
     413            if (v.valid()) G->getFirst(in, v);
     414            while (in.valid() && !(free()>0) ) { ++in; }
     415          }
     416        }
     417        return *this;
     418      }
     419    };
     420
    338421    void getFirst(OutEdgeIt& e, NodeIt v) const {
    339422      e=OutEdgeIt(G, v, flow, capacity);
     423    }
     424    void getFirst(EachEdgeIt& e) const {
     425      e=EachEdgeIt(G, flow, capacity);
    340426    }
    341427    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     
    402488    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
    403489    //typename AugGraph::NodeMap<AugEdgeIt> pred;
    404     //typename AugGraph::NodeMap<int> free;
     490    //typename AugGraph::NodeMap<Number> free;
    405491  public:
    406492    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
     
    408494      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
    409495      { }
    410     bool augment() {
     496    bool augmentOnShortestPath() {
    411497      AugGraph res_graph(G, flow, capacity);
    412498      bool _augment=false;
     
    420506      //pred.set(s, AugEdgeIt());
    421507     
    422       typename AugGraph::NodeMap<int> free(res_graph);
     508      typename AugGraph::NodeMap<Number> free(res_graph);
    423509       
    424510      //searching for augmenting path
     
    452538      return _augment;
    453539    }
    454     bool augmentWithBlockingFlow() {
    455       BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
     540    template<typename MutableGraph> bool augmentOnBlockingFlow() {
     541      bool _augment=false;
     542
     543      AugGraph res_graph(G, flow, capacity);
     544
     545      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     546      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     547
    456548      bfs.pushAndSetReached(s);
    457       typename Graph::NodeMap<int> dist(G); //filled up with 0's
     549      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    458550      while ( !bfs.finished() ) {
    459         OutEdgeIt e=OutEdgeIt(bfs);
     551        AugOutEdgeIt e=AugOutEdgeIt(bfs);
    460552        if (e.valid() && bfs.isBNodeNewlyReached()) {
    461           dist.set(G.head(e), dist.get(G.tail(e))+1);
    462           //NodeIt v=res_graph.tail(e);
    463           //NodeIt w=res_graph.head(e);
    464           //pred.set(w, e);
    465           //if (pred.get(v).valid()) {
    466           //  free.set(w, std::min(free.get(v), e.free()));
    467           //} else {
    468           //  free.set(w, e.free());
    469           //}
    470           //if (res_graph.head(e)==t) { _augment=true; break; }
     553          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    471554        }
    472555       
    473556        ++bfs;
    474       } //end of searching augmenting path
    475 
    476       double pre_time_copy=currTime();
    477       typedef Graph MutableGraph;
     557      } //computing distances from s in the residual graph
     558
    478559      MutableGraph F;
    479       typename Graph::NodeMap<NodeIt> G_to_F(G);
    480       for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
    481         G_to_F.set(n, F.addNode());
    482       }
    483       for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
    484         if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
    485           F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
    486         }
    487       }
    488       double post_time_copy=currTime();
    489       std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
    490 
    491       return 0;
     560      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
     561      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
     562        res_graph_to_F.set(n, F.addNode());
     563      }
     564     
     565      typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
     566      typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
     567
     568      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
     569      typename MutableGraph::EdgeMap<Number> free_on_edge(F);
     570
     571      //Making F to the graph containing the edges of the residual graph
     572      //which are in some shortest paths
     573      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
     574        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     575          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     576          original_edge.update();
     577          original_edge.set(f, e);
     578          free_on_edge.update();
     579          free_on_edge.set(f, e.free());
     580        }
     581      }
     582
     583      bool __augment=true;
     584
     585      while (__augment) {
     586        __augment=false;
     587        //computing blocking flow with dfs
     588        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
     589        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     590        typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
     591        typename MutableGraph::NodeMap<Number> free(F);
     592
     593        dfs.pushAndSetReached(sF);     
     594        while (!dfs.finished()) {
     595          ++dfs;
     596          if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
     597            //std::cout << "OutEdgeIt: " << dfs;
     598            //std::cout << " aNode: " << F.aNode(dfs);
     599            //std::cout << " bNode: " << F.bNode(dfs) << " ";
     600         
     601            typename MutableGraph::NodeIt v=F.aNode(dfs);
     602            typename MutableGraph::NodeIt w=F.bNode(dfs);
     603            pred.set(w, dfs);
     604            if (pred.get(v).valid()) {
     605              free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
     606            } else {
     607              free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
     608            }
     609            if (w==tF) {
     610              //std::cout << "AUGMENTATION"<<std::endl;
     611              __augment=true;
     612              _augment=true;
     613              break;
     614            }
     615          } else {
     616            //std::cout << "OutEdgeIt: " << "invalid";
     617            //std::cout << " aNode: " << dfs.aNode();
     618            //std::cout << " bNode: " << "invalid" << " ";
     619          }
     620          if (dfs.isBNodeNewlyReached()) {
     621            //std::cout << "bNodeIsNewlyReached ";
     622          } else {
     623            //std::cout << "bNodeIsNotNewlyReached ";
     624            if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
     625              //std::cout << "DELETE ";
     626              F.erase(typename MutableGraph::OutEdgeIt(dfs));
     627            }
     628          }
     629          //if (dfs.isANodeExamined()) {
     630            //std::cout << "aNodeIsExamined ";
     631            //} else {
     632            //std::cout << "aNodeIsNotExamined ";
     633            //}
     634          //std::cout<<std::endl;
     635        }
     636
     637        if (__augment) {
     638          typename MutableGraph::NodeIt n=tF;
     639          Number augment_value=free.get(tF);
     640          while (pred.get(n).valid()) {
     641            typename MutableGraph::EdgeIt e=pred.get(n);
     642            original_edge.get(e).augment(augment_value);
     643            n=F.tail(e);
     644            F.erase(e);
     645          }
     646        }
     647
     648      }
     649           
     650      return _augment;
    492651    }
    493652    void run() {
    494653      //int num_of_augmentations=0;
    495       while (augment()) {
     654      while (augmentOnShortestPath()) {
     655        //while (augmentOnBlockingFlow<MutableGraph>()) {
     656        //std::cout << ++num_of_augmentations << " ";
     657        //std::cout<<std::endl;
     658      }
     659    }
     660    template<typename MutableGraph> void run() {
     661      //int num_of_augmentations=0;
     662      //while (augmentOnShortestPath()) {
     663        while (augmentOnBlockingFlow<MutableGraph>()) {
    496664        //std::cout << ++num_of_augmentations << " ";
    497665        //std::cout<<std::endl;
     
    600768      //filled up with invalid iterators
    601769     
    602       typename AugGraph::NodeMap<int> free(res_graph);
     770      typename AugGraph::NodeMap<Number> free(res_graph);
    603771       
    604772      //searching for augmenting path
  • src/work/marci/edmonds_karp_demo.cc

    r105 r133  
    2020  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2121
    22 /*
    23   double pre_time_copy=currTime();
    24   ListGraph F;
    25   ListGraph::NodeMap<NodeIt> G_to_F(G);
    26   typedef ListGraph::EachNodeIt EachNodeIt;
    27   for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) {
    28     G_to_F.set(n, F.addNode());
    29   }
    30   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    31     F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
    32   }
    33   double post_time_copy=currTime();
    34   std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
    35 */
    36 
    37   std::cout << "edmonds karp demo..." << std::endl;
     22  {
     23  std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    3824  ListGraph::EdgeMap<int> flow(G); //0 flow
    3925
    4026  double pre_time=currTime();
    4127  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    42   max_flow_test.augmentWithBlockingFlow();
    43   max_flow_test.run();
     28  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
     29  max_flow_test.run<ListGraph>();
    4430  double post_time=currTime();
     31
    4532  //std::cout << "maximum flow: "<< std::endl;
    4633  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     
    5037  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
    5138  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     39  }
     40
     41  {
     42  std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
     43  ListGraph::EdgeMap<int> flow(G); //0 flow
     44
     45  double pre_time=currTime();
     46  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     47  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
     48  max_flow_test.run();
     49  double post_time=currTime();
     50
     51  //std::cout << "maximum flow: "<< std::endl;
     52  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     53  //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     54  //}
     55  //std::cout<<std::endl;
     56  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
     57  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     58  }
    5259
    5360  return 0;
  • src/work/marci_graph_demo.cc

    r107 r133  
    226226    ListGraph::EdgeMap<int> flow(flowG, 0);
    227227    MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
     228    /*
     229    max_flow_test.augmentOnBlockingFlow<ListGraph>();
     230    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     231      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     232    }
     233    std::cout<<std::endl;
     234    max_flow_test.augmentOnBlockingFlow<ListGraph>();
     235    for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     236      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     237    }
     238    std::cout<<std::endl;*/
    228239    max_flow_test.run();
    229240   
Note: See TracChangeset for help on using the changeset viewer.