COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 334:63703ea7d02f in lemon-0.x for src/work/marci/lg_vs_sg.cc


Ignore:
Timestamp:
04/15/04 22:50:03 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@453
Message:

brrr

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/lg_vs_sg.cc

    r174 r334  
    88#include <dimacs.h>
    99#include <edmonds_karp.h>
     10#include <preflow.h>
    1011#include <time_measure.h>
    11 #include <graph_wrapper.h>
     12#include <for_each_macros.h>
    1213
    1314using namespace hugo;
    … …  
    3233    readDimacsMaxFlow(ins, G, s, t, cap);
    3334
     35    Timer ts;
     36    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);
     39    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     40      max_flow_test(G, s, t, cap, flow);
     41
     42    std::cout << "ListGraph ..." << std::endl;
     43
    3444    {
    35       std::cout << "ListGraph..." << std::endl;
    36       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    37       Graph::EdgeMap<int> flow(G); //0 flow
     45      std::cout << "preflow ..." << std::endl;
     46      ts.reset();
     47      pre_flow_test.run();
     48      std::cout << "elapsed time: " << ts << std::endl;
     49      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     50    }
    3851
    39       Timer ts;
     52    {
     53      std::cout << "physical blocking flow augmentation ..." << std::endl;
     54      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    4055      ts.reset();
    41 
    42       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    4356      int i=0;
    4457      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    45 
    4658      std::cout << "elapsed time: " << ts << std::endl;
    4759      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    5062
    5163    {
    52       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    53       Graph::EdgeMap<int> flow(G); //0 flow
    54 
    55       Timer ts;
     64      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     65      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    5666      ts.reset();
    57 
    58       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    5967      int i=0;
    60       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    61 
     68      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    6269      std::cout << "elapsed time: " << ts << std::endl;
    6370      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    6673
    6774    {
    68       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    69       Graph::EdgeMap<int> flow(G); //0 flow
     75      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     76      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     77      ts.reset();
     78      int i=0;
     79      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     80      std::cout << "elapsed time: " << ts << std::endl;
     81      std::cout << "number of augmentation phases: " << i << std::endl;
     82      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     83    }
    7084
    71       Timer ts;
     85    {
     86      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     87      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    7288      ts.reset();
    73 
    74       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    7589      int i=0;
    7690      while (max_flow_test.augmentOnShortestPath()) { ++i; }
    77 
    7891      std::cout << "elapsed time: " << ts << std::endl;
    7992      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    94107    readDimacsMaxFlow(ins, G, s, t, cap);
    95108
     109    Timer ts;
     110    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);
     113    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     114      max_flow_test(G, s, t, cap, flow);
     115
     116    std::cout << "SmatrGraph ..." << std::endl;
     117
    96118    {
    97       std::cout << "SmartGraph..." << std::endl;
    98       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    99       Graph::EdgeMap<int> flow(G); //0 flow
     119      std::cout << "preflow ..." << std::endl;
     120      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     121      ts.reset();
     122      pre_flow_test.run();
     123      std::cout << "elapsed time: " << ts << std::endl;
     124      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
     125    }
    100126
    101       Timer ts;
     127    {
     128      std::cout << "physical blocking flow augmentation ..." << std::endl;
     129      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    102130      ts.reset();
    103 
    104       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    105131      int i=0;
    106132      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
    107 
    108133      std::cout << "elapsed time: " << ts << std::endl;
    109134      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    112137
    113138    {
    114       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    115       Graph::EdgeMap<int> flow(G); //0 flow
    116 
    117       Timer ts;
     139      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
     140      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    118141      ts.reset();
    119 
    120       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    121142      int i=0;
    122       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
    123 
     143      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
    124144      std::cout << "elapsed time: " << ts << std::endl;
    125145      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    128148
    129149    {
    130       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    131       Graph::EdgeMap<int> flow(G); //0 flow
     150      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
     151      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     152      ts.reset();
     153      int i=0;
     154      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     155      std::cout << "elapsed time: " << ts << std::endl;
     156      std::cout << "number of augmentation phases: " << i << std::endl;
     157      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     158    }
    132159
    133       Timer ts;
     160    {
     161      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
     162      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    134163      ts.reset();
    135 
    136       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    137164      int i=0;
    138165      while (max_flow_test.augmentOnShortestPath()) { ++i; }
    139 
    140166      std::cout << "elapsed time: " << ts << std::endl;
    141167      std::cout << "number of augmentation phases: " << i << std::endl;
    … …  
    144170  }
    145171
     172
     173
     174
    146175  return 0;
    147176}
Note: See TracChangeset for help on using the changeset viewer.