COIN-OR::LEMON - Graph Library

Changeset 476:cfe550761745 in lemon-0.x


Ignore:
Timestamp:
04/29/04 18:25:03 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@633
Message:

preflow, maxflow

Location:
src/work
Files:
6 edited

Legend:

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

    r472 r476  
    5656            typename CapMap=typename Graph::template EdgeMap<Num>,
    5757            typename FlowMap=typename Graph::template EdgeMap<Num> >
    58   class Preflow {
     58  class MaxFlow {
    5959   
    6060    typedef typename Graph::Node Node;
     
    9393    };
    9494
    95     Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
     95    MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    9696            FlowMap& _flow) :
    9797      g(&_G), s(_s), t(_t), capacity(&_capacity),
     
    536536
    537537  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    538   void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
     538  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
    539539  {
    540540     
     
    645645
    646646  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    647   void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
     647  void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
    648648  {
    649649     
     
    709709
    710710  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    711   bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
     711  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
    712712  {
    713713      ResGW res_graph(*g, *capacity, *flow);
     
    765765  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    766766  template<typename MutableGraph>
    767   bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
     767  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
    768768  {     
    769769      typedef MutableGraph MG;
     
    882882
    883883  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
    884   bool Preflow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
     884  bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
    885885  {
    886886      bool _augment=false;
  • src/work/marci/bipartite_graph_wrapper_test.cc

    r409 r476  
    1212#include <graph_wrapper.h>
    1313#include <maps.h>
    14 #include <edmonds_karp.h>
     14#include <preflow.h>
    1515
    1616using namespace hugo;
  • src/work/marci/bipartite_matching_try.cc

    r465 r476  
    1313#include <graph_wrapper.h>
    1414#include <maps.h>
    15 #include <edmonds_karp.h>
    1615#include <preflow.h>
    1716
     
    181180  ts.reset();
    182181  stGW::EdgeMap<int> pre_flow(stgw);
    183   Preflow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
     182  MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
    184183    pre_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, pre_flow/*, true*/);
    185184  pre_flow_test.run();
  • src/work/marci/lg_vs_sg.cc

    r465 r476  
    77#include <smart_graph.h>
    88#include <dimacs.h>
    9 #include <edmonds_karp.h>
    109#include <preflow.h>
    1110#include <time_measure.h>
     
    3534    Timer ts;
    3635    Graph::EdgeMap<int> flow(G); //0 flow
    37     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    38       pre_flow_test(G, s, t, cap, flow/*, true*/);
    3936    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    40       max_flow_test(G, s, t, cap, flow);
     37      max_flow_test(G, s, t, cap, flow/*, true*/);
    4138
    4239    std::cout << "ListGraph ..." << std::endl;
     
    4542      std::cout << "preflow ..." << std::endl;
    4643      ts.reset();
    47       pre_flow_test.run();
     44      max_flow_test.run();
    4845      std::cout << "elapsed time: " << ts << std::endl;
    49       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     46      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    5047    }
    5148
     
    6158    }
    6259
    63     {
    64       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    65       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    66       ts.reset();
    67       int i=0;
    68       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    69       std::cout << "elapsed time: " << ts << std::endl;
    70       std::cout << "number of augmentation phases: " << i << std::endl;
    71       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    72     }
     60//     {
     61//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     62//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     63//       ts.reset();
     64//       int i=0;
     65//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     66//       std::cout << "elapsed time: " << ts << std::endl;
     67//       std::cout << "number of augmentation phases: " << i << std::endl;
     68//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     69//     }
    7370
    7471    {
     
    109106    Timer ts;
    110107    Graph::EdgeMap<int> flow(G); //0 flow
    111     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    112       pre_flow_test(G, s, t, cap, flow/*, true*/);
    113108    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    114       max_flow_test(G, s, t, cap, flow);
     109      max_flow_test(G, s, t, cap, flow/*, true*/);
     110    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     111    //  max_flow_test(G, s, t, cap, flow);
    115112
    116113    std::cout << "SmatrGraph ..." << std::endl;
     
    120117      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    121118      ts.reset();
    122       pre_flow_test.run();
     119      max_flow_test.run();
    123120      std::cout << "elapsed time: " << ts << std::endl;
    124       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     121      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    125122    }
    126123
     
    136133    }
    137134
    138     {
    139       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    140       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    141       ts.reset();
    142       int i=0;
    143       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    144       std::cout << "elapsed time: " << ts << std::endl;
    145       std::cout << "number of augmentation phases: " << i << std::endl;
    146       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    147     }
     135//     {
     136//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     137//       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     138//       ts.reset();
     139//       int i=0;
     140//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     141//       std::cout << "elapsed time: " << ts << std::endl;
     142//       std::cout << "number of augmentation phases: " << i << std::endl;
     143//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     144//     }
    148145
    149146    {
  • src/work/marci/makefile

    r433 r476  
    55
    66LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    7 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
     7BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
    88#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    99
  • src/work/marci/max_flow_demo.cc

    r475 r476  
    66#include <smart_graph.h>
    77#include <dimacs.h>
    8 //#include <edmonds_karp.h>
    98#include <time_measure.h>
    109//#include <graph_wrapper.h>
     
    7170  Timer ts;
    7271  Graph::EdgeMap<int> flow(G); //0 flow
    73   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    74     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*/);
    77 //   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
    78 //     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);
     72  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     73    max_flow_test(G, s, t, cap, flow);
    8174
    8275  {
    8376    std::cout << "preflow ..." << std::endl;
    8477    ts.reset();
    85     pre_flow_test.run();
     78    max_flow_test.run();
    8679    std::cout << "elapsed time: " << ts << std::endl;
    87     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     80    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    8881  }
    8982
     
    9285    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    9386    ts.reset();
    94     pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
     87    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    9588    std::cout << "elapsed time: " << ts << std::endl;
    96     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     89    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    9790  }
    9891
     
    111104    ts.reset();
    112105    int i=0;
    113     while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
     106    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    114107    std::cout << "elapsed time: " << ts << std::endl;
    115108    std::cout << "number of augmentation phases: " << i << std::endl;
    116     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     109    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    117110  }
    118111
     
    133126    ts.reset();
    134127    int i=0;
    135     while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
     128    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    136129    std::cout << "elapsed time: " << ts << std::endl;
    137130    std::cout << "number of augmentation phases: " << i << std::endl;
    138     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     131    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    139132  }
    140133
     
    144137    ts.reset();
    145138    int i=0;
    146     while (pre_flow_test.augmentOnShortestPath()) { ++i; }
     139    while (max_flow_test.augmentOnShortestPath()) { ++i; }
    147140    std::cout << "elapsed time: " << ts << std::endl;
    148141    std::cout << "number of augmentation phases: " << i << std::endl;
    149     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     142    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    150143  }
    151144
Note: See TracChangeset for help on using the changeset viewer.