COIN-OR::LEMON - Graph Library

Changeset 472:052af4060f3e in lemon-0.x


Ignore:
Timestamp:
04/29/04 17:58:34 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@629
Message:

preflow, maxflow

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow.h

    r471 r472  
    4545
    4646#include <graph_wrapper.h>
     47#include <bfs_iterator.h>
     48#include <invalid.h>
     49#include <maps.h>
     50#include <for_each_macros.h>
     51
    4752
    4853namespace hugo {
     
    112117    bool augmentOnBlockingFlow2();
    113118
    114     //Returns the maximum value of a flow.
    115     Num flowValue() {
    116       return excess[t];
     119    /// Returns the actual flow value.
     120    /// More precisely, it returns the negative excess of s, thus
     121    /// this works also for preflows.
     122    Num flowValue() {
     123      Num a=0;
     124      FOR_EACH_INC_LOC(OutEdgeIt, e, *g, s) a+=(*flow)[e];
     125      FOR_EACH_INC_LOC(InEdgeIt, e, *g, s) a-=(*flow)[e];
     126      return a;
    117127    }
    118128
     
    434444    void relabel(Node w, int newlevel, VecStack& active, 
    435445                 VecNode& level_list, NNMap& left,
    436                  NNMap& right, int& b, int& k, bool what_heur ) {
     446                 NNMap& right, int& b, int& k, bool what_heur )
     447    {
    437448
    438449      Num lev=level[w];
     
    498509     
    499510    } //relabel
     511
     512
     513    template<typename MapGraphWrapper>
     514    class DistanceMap {
     515    protected:
     516      const MapGraphWrapper* g;
     517      typename MapGraphWrapper::template NodeMap<int> dist;
     518    public:
     519      DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
     520      void set(const typename MapGraphWrapper::Node& n, int a) {
     521        dist.set(n, a);
     522      }
     523      int operator[](const typename MapGraphWrapper::Node& n)
     524        { return dist[n]; }
     525//       int get(const typename MapGraphWrapper::Node& n) const {
     526//      return dist[n]; }
     527//       bool get(const typename MapGraphWrapper::Edge& e) const {
     528//      return (dist.get(g->tail(e))<dist.get(g->head(e))); }
     529      bool operator[](const typename MapGraphWrapper::Edge& e) const {
     530        return (dist[g->tail(e)]<dist[g->head(e)]);
     531      }
     532    };
    500533   
    501534  };
     
    675708
    676709
    677 
    678 
    679 
    680 
    681 
     710  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     711  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
     712  {
     713      ResGW res_graph(*g, *capacity, *flow);
     714      bool _augment=false;
     715     
     716      //ReachedMap level(res_graph);
     717      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     718      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     719      bfs.pushAndSetReached(s);
     720       
     721      typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
     722      pred.set(s, INVALID);
     723     
     724      typename ResGW::template NodeMap<Num> free(res_graph);
     725       
     726      //searching for augmenting path
     727      while ( !bfs.finished() ) {
     728        ResGWOutEdgeIt e=bfs;
     729        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     730          Node v=res_graph.tail(e);
     731          Node w=res_graph.head(e);
     732          pred.set(w, e);
     733          if (res_graph.valid(pred[v])) {
     734            free.set(w, std::min(free[v], res_graph.resCap(e)));
     735          } else {
     736            free.set(w, res_graph.resCap(e));
     737          }
     738          if (res_graph.head(e)==t) { _augment=true; break; }
     739        }
     740       
     741        ++bfs;
     742      } //end of searching augmenting path
     743
     744      if (_augment) {
     745        Node n=t;
     746        Num augment_value=free[t];
     747        while (res_graph.valid(pred[n])) {
     748          ResGWEdge e=pred[n];
     749          res_graph.augment(e, augment_value);
     750          n=res_graph.tail(e);
     751        }
     752      }
     753
     754      return _augment;
     755    }
     756
     757
     758
     759
     760
     761
     762
     763
     764
     765  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     766  template<typename MutableGraph>
     767  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
     768  {     
     769      typedef MutableGraph MG;
     770      bool _augment=false;
     771
     772      ResGW res_graph(*g, *capacity, *flow);
     773
     774      //bfs for distances on the residual graph
     775      //ReachedMap level(res_graph);
     776      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     777      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     778      bfs.pushAndSetReached(s);
     779      typename ResGW::template NodeMap<int>
     780        dist(res_graph); //filled up with 0's
     781
     782      //F will contain the physical copy of the residual graph
     783      //with the set of edges which are on shortest paths
     784      MG F;
     785      typename ResGW::template NodeMap<typename MG::Node>
     786        res_graph_to_F(res_graph);
     787      {
     788        typename ResGW::NodeIt n;
     789        for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
     790          res_graph_to_F.set(n, F.addNode());
     791        }
     792      }
     793
     794      typename MG::Node sF=res_graph_to_F[s];
     795      typename MG::Node tF=res_graph_to_F[t];
     796      typename MG::template EdgeMap<ResGWEdge> original_edge(F);
     797      typename MG::template EdgeMap<Num> residual_capacity(F);
     798
     799      while ( !bfs.finished() ) {
     800        ResGWOutEdgeIt e=bfs;
     801        if (res_graph.valid(e)) {
     802          if (bfs.isBNodeNewlyReached()) {
     803            dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     804            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     805            original_edge.update();
     806            original_edge.set(f, e);
     807            residual_capacity.update();
     808            residual_capacity.set(f, res_graph.resCap(e));
     809          } else {
     810            if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
     811              typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
     812              original_edge.update();
     813              original_edge.set(f, e);
     814              residual_capacity.update();
     815              residual_capacity.set(f, res_graph.resCap(e));
     816            }
     817          }
     818        }
     819        ++bfs;
     820      } //computing distances from s in the residual graph
     821
     822      bool __augment=true;
     823
     824      while (__augment) {
     825        __augment=false;
     826        //computing blocking flow with dfs
     827        DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
     828        typename MG::template NodeMap<typename MG::Edge> pred(F);
     829        pred.set(sF, INVALID);
     830        //invalid iterators for sources
     831
     832        typename MG::template NodeMap<Num> free(F);
     833
     834        dfs.pushAndSetReached(sF);     
     835        while (!dfs.finished()) {
     836          ++dfs;
     837          if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
     838            if (dfs.isBNodeNewlyReached()) {
     839              typename MG::Node v=F.aNode(dfs);
     840              typename MG::Node w=F.bNode(dfs);
     841              pred.set(w, dfs);
     842              if (F.valid(pred[v])) {
     843                free.set(w, std::min(free[v], residual_capacity[dfs]));
     844              } else {
     845                free.set(w, residual_capacity[dfs]);
     846              }
     847              if (w==tF) {
     848                __augment=true;
     849                _augment=true;
     850                break;
     851              }
     852             
     853            } else {
     854              F.erase(/*typename MG::OutEdgeIt*/(dfs));
     855            }
     856          }
     857        }
     858
     859        if (__augment) {
     860          typename MG::Node n=tF;
     861          Num augment_value=free[tF];
     862          while (F.valid(pred[n])) {
     863            typename MG::Edge e=pred[n];
     864            res_graph.augment(original_edge[e], augment_value);
     865            n=F.tail(e);
     866            if (residual_capacity[e]==augment_value)
     867              F.erase(e);
     868            else
     869              residual_capacity.set(e, residual_capacity[e]-augment_value);
     870          }
     871        }
     872       
     873      }
     874           
     875      return _augment;
     876    }
     877
     878
     879
     880
     881
     882
     883  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
     884  bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
     885  {
     886      bool _augment=false;
     887
     888      ResGW res_graph(*g, *capacity, *flow);
     889     
     890      //ReachedMap level(res_graph);
     891      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
     892      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
     893
     894      bfs.pushAndSetReached(s);
     895      DistanceMap<ResGW> dist(res_graph);
     896      while ( !bfs.finished() ) {
     897        ResGWOutEdgeIt e=bfs;
     898        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     899          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     900        }
     901        ++bfs;
     902      } //computing distances from s in the residual graph
     903
     904      //Subgraph containing the edges on some shortest paths
     905      ConstMap<typename ResGW::Node, bool> true_map(true);
     906      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     907        DistanceMap<ResGW> > FilterResGW;
     908      FilterResGW filter_res_graph(res_graph, true_map, dist);
     909
     910      //Subgraph, which is able to delete edges which are already
     911      //met by the dfs
     912      typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
     913        first_out_edges(filter_res_graph);
     914      typename FilterResGW::NodeIt v;
     915      for(filter_res_graph.first(v); filter_res_graph.valid(v);
     916          filter_res_graph.next(v))
     917      {
     918        typename FilterResGW::OutEdgeIt e;
     919        filter_res_graph.first(e, v);
     920        first_out_edges.set(v, e);
     921      }
     922      typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
     923        template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
     924      ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
     925
     926      bool __augment=true;
     927
     928      while (__augment) {
     929
     930        __augment=false;
     931        //computing blocking flow with dfs
     932        DfsIterator< ErasingResGW,
     933          typename ErasingResGW::template NodeMap<bool> >
     934          dfs(erasing_res_graph);
     935        typename ErasingResGW::
     936          template NodeMap<typename ErasingResGW::OutEdgeIt>
     937          pred(erasing_res_graph);
     938        pred.set(s, INVALID);
     939        //invalid iterators for sources
     940
     941        typename ErasingResGW::template NodeMap<Num>
     942          free1(erasing_res_graph);
     943
     944        dfs.pushAndSetReached(
     945          typename ErasingResGW::Node(
     946            typename FilterResGW::Node(
     947              typename ResGW::Node(s)
     948              )
     949            )
     950          );
     951        while (!dfs.finished()) {
     952          ++dfs;
     953          if (erasing_res_graph.valid(
     954                typename ErasingResGW::OutEdgeIt(dfs)))
     955          {
     956            if (dfs.isBNodeNewlyReached()) {
     957         
     958              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
     959              typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
     960
     961              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
     962              if (erasing_res_graph.valid(pred[v])) {
     963                free1.set(w, std::min(free1[v], res_graph.resCap(
     964                                       typename ErasingResGW::OutEdgeIt(dfs))));
     965              } else {
     966                free1.set(w, res_graph.resCap(
     967                           typename ErasingResGW::OutEdgeIt(dfs)));
     968              }
     969             
     970              if (w==t) {
     971                __augment=true;
     972                _augment=true;
     973                break;
     974              }
     975            } else {
     976              erasing_res_graph.erase(dfs);
     977            }
     978          }
     979        }       
     980
     981        if (__augment) {
     982          typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
     983//        typename ResGW::NodeMap<Num> a(res_graph);
     984//        typename ResGW::Node b;
     985//        Num j=a[b];
     986//        typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
     987//        typename FilterResGW::Node b1;
     988//        Num j1=a1[b1];
     989//        typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
     990//        typename ErasingResGW::Node b2;
     991//        Num j2=a2[b2];
     992          Num augment_value=free1[n];
     993          while (erasing_res_graph.valid(pred[n])) {
     994            typename ErasingResGW::OutEdgeIt e=pred[n];
     995            res_graph.augment(e, augment_value);
     996            n=erasing_res_graph.tail(e);
     997            if (res_graph.resCap(e)==0)
     998              erasing_res_graph.erase(e);
     999        }
     1000      }
     1001     
     1002      } //while (__augment)
     1003           
     1004      return _augment;
     1005    }
    6821006
    6831007
  • src/work/marci/edmonds_karp_demo.cc

    r465 r472  
    66#include <smart_graph.h>
    77#include <dimacs.h>
    8 #include <edmonds_karp.h>
     8//#include <edmonds_karp.h>
    99#include <time_measure.h>
    1010//#include <graph_wrapper.h>
    1111#include <preflow.h>
    12 #include <preflow_res.h>
     12//#include <preflow_res.h>
    1313#include <for_each_macros.h>
    1414
     
    7373  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    7474    pre_flow_test(G, s, t, cap, flow/*, true*/);
    75   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    76     pre_flow_ize(G, s, t, cap, flow/*, false*/);
     75  //  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     76  //  pre_flow_ize(G, s, t, cap, flow/*, false*/);
    7777//   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    7878//     pre_flow_res(G, s, t, cap, flow/*, true*/);
    79   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    80     max_flow_test(G, s, t, cap, flow);
     79  //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     80  //  max_flow_test(G, s, t, cap, flow);
    8181
    8282  {
     
    9292    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    9393    ts.reset();
    94     pre_flow_ize.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     94    pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    9595    std::cout << "elapsed time: " << ts << std::endl;
    96     std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl;
     96    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    9797  }
    9898
     
    111111    ts.reset();
    112112    int i=0;
    113     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
     113    while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    114114    std::cout << "elapsed time: " << ts << std::endl;
    115115    std::cout << "number of augmentation phases: " << i << std::endl;
    116     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     116    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    117117  }
    118118
    119   {
    120     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    121     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    122     ts.reset();
    123     int i=0;
    124     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    125     std::cout << "elapsed time: " << ts << std::endl;
    126     std::cout << "number of augmentation phases: " << i << std::endl;
    127     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    128   }
     119//   {
     120//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     121//     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     122//     ts.reset();
     123//     int i=0;
     124//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     125//     std::cout << "elapsed time: " << ts << std::endl;
     126//     std::cout << "number of augmentation phases: " << i << std::endl;
     127//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     128//   }
    129129
    130130  {
     
    133133    ts.reset();
    134134    int i=0;
    135     while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     135    while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
    136136    std::cout << "elapsed time: " << ts << std::endl;
    137137    std::cout << "number of augmentation phases: " << i << std::endl;
    138     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     138    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    139139  }
    140140
     
    144144    ts.reset();
    145145    int i=0;
    146     while (max_flow_test.augmentOnShortestPath()) { ++i; }
     146    while (pre_flow_test.augmentOnShortestPath()) { ++i; }
    147147    std::cout << "elapsed time: " << ts << std::endl;
    148148    std::cout << "number of augmentation phases: " << i << std::endl;
    149     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     149    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    150150  }
    151151
Note: See TracChangeset for help on using the changeset viewer.