COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 476:cfe550761745 in lemon-0.x for src/work/marci


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/marci
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • 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.