COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
03/12/04 10:19:54 (18 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@250
Message:

towards on ListGraph?, SmartGraph? compatibility

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp_demo.cc

    r168 r174  
     1// -*- c++ -*-
    12#include <iostream>
    23#include <fstream>
    34
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
    6 #include <edmonds_karp.hh>
     5#include <list_graph.h>
     6#include <smart_graph.h>
     7#include <dimacs.h>
     8#include <edmonds_karp.h>
    79#include <time_measure.h>
    810#include <graph_wrapper.h>
     
    1315// read_dimacs_demo < dimacs_max_flow_file
    1416
    15 /*
    16   struct Ize {
    17   };
     17
     18//   struct Ize {
     19//   };
    1820 
    19   struct Mize {
    20     Ize bumm;
    21   };
     21//   struct Mize {
     22//     Ize bumm;
     23//   };
    2224
    23   template <typename B>
    24     class Huha {
    25     public:
    26       int u;
    27       B brr;
    28     };
    29 */
     25//   template <typename B>
     26//     class Huha {
     27//     public:
     28//       int u;
     29//       B brr;
     30//     };
     31
    3032
    3133int main(int, char **) {
    32   typedef ListGraph::NodeIt NodeIt;
    33   typedef ListGraph::EachEdgeIt EachEdgeIt;
    3434
    35 /*
    36   Mize mize[10];
    37   Mize bize[0];
    38   Mize zize;
    39   typedef Mize Tize[0];
     35  typedef ListGraph MutableGraph;
    4036
    41   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
    42   std::cout << sizeof(bize) << std::endl;
     37  typedef SmartGraph Graph;
     38  typedef Graph::Node Node;
     39  typedef Graph::EdgeIt EdgeIt;
    4340
    4441
    45   Huha<Tize> k;
    46   std::cout << sizeof(k) << std::endl;
     42//   Mize mize[10];
     43//   Mize bize[0];
     44//   Mize zize;
     45//   typedef Mize Tize[0];
     46
     47//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
     48//   std::cout << sizeof(bize) << std::endl;
    4749
    4850
    49   struct Bumm {
    50     //int a;
    51     bool b;
    52   };
     51//   Huha<Tize> k;
     52//   std::cout << sizeof(k) << std::endl;
    5353
    54   std::cout << sizeof(Bumm) << std::endl;
    55 */
    5654
    57   ListGraph G;
    58   NodeIt s, t;
    59   ListGraph::EdgeMap<int> cap(G);
     55//   struct Bumm {
     56//     //int a;
     57//     bool b;
     58//   };
     59
     60//   std::cout << sizeof(Bumm) << std::endl;
     61
     62
     63  Graph G;
     64  Node s, t;
     65  Graph::EdgeMap<int> cap(G);
    6066  readDimacsMaxFlow(std::cin, G, s, t, cap);
    61 /*
    62   typedef TrivGraphWrapper<ListGraph> TGW;
    63   TGW gw(G);
    64   TGW::EachNodeIt sw;
    65   gw.getFirst(sw);
    66   std::cout << "p1:" << gw.nodeNum() << std::endl;
    67   gw.erase(sw);
    68   std::cout << "p2:" << gw.nodeNum() << std::endl;
    6967
    70   typedef const ListGraph cLG;
    71   typedef TrivGraphWrapper<const cLG> CTGW;
    72   CTGW cgw(G);
    73   CTGW::EachNodeIt csw;
    74   cgw.getFirst(csw);
    75   std::cout << "p1:" << cgw.nodeNum() << std::endl;
    76   //cgw.erase(csw);
    77   std::cout << "p2:" << cgw.nodeNum() << std::endl;
    78 */
     68//   typedef TrivGraphWrapper<Graph> TGW;
     69//   TGW gw(G);
     70//   TGW::NodeIt sw;
     71//   gw./*getF*/first(sw);
     72//   std::cout << "p1:" << gw.nodeNum() << std::endl;
     73//   gw.erase(sw);
     74//   std::cout << "p2:" << gw.nodeNum() << std::endl;
     75
     76//   typedef const Graph cLG;
     77//   typedef TrivGraphWrapper<const cLG> CTGW;
     78//   CTGW cgw(G);
     79//   CTGW::NodeIt csw;
     80//   cgw./*getF*/first(csw);
     81//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
     82//   //cgw.erase(csw);
     83//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
     84
    7985
    8086  {
    81   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    82   ListGraph::EdgeMap<int> flow(G); //0 flow
     87    std::cout << "SmartGraph..." << std::endl;
     88    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
     89    Graph::EdgeMap<int> flow(G); //0 flow
    8390
    84   Timer ts;
    85   ts.reset();
    86   //double pre_time=currTime();
    87   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    88   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    89   int i=0;
    90   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
    91 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     91    Timer ts;
     92    ts.reset();
     93
     94    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     95    //max_flow_test.augmentWithBlockingFlow<Graph>();
     96    int i=0;
     97    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
     98//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    9299//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    93100//     }
    94101//     std::cout<<std::endl;
    95     ++i;
    96   }
    97   //double post_time=currTime();
     102      ++i;
     103    }
    98104
    99   //std::cout << "maximum flow: "<< std::endl;
    100   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    101   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    102   //}
    103   //std::cout<<std::endl;
    104   std::cout << "elapsed time: " << ts << std::endl;
    105   std::cout << "number of augmentation phases: " << i << std::endl;
    106   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     105//   std::cout << "maximum flow: "<< std::endl;
     106//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     107//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     108//   }
     109//   std::cout<<std::endl;
     110    std::cout << "elapsed time: " << ts << std::endl;
     111    std::cout << "number of augmentation phases: " << i << std::endl;
     112    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    107113  }
    108114
    109115  {
    110   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    111   ListGraph::EdgeMap<int> flow(G); //0 flow
     116    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     117    Graph::EdgeMap<int> flow(G); //0 flow
    112118
    113   Timer ts;
    114   ts.reset();
    115   //double pre_time=currTime();
    116   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    117   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    118   int i=0;
    119   while (max_flow_test.augmentOnBlockingFlow2()) {
    120 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     119    Timer ts;
     120    ts.reset();
     121
     122    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     123    //max_flow_test.augmentWithBlockingFlow<Graph>();
     124    int i=0;
     125    while (max_flow_test.augmentOnBlockingFlow2()) {
     126//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    121127//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    122128//     }
    123129//     std::cout<<std::endl;
    124     ++i;
    125   }
    126   //double post_time=currTime();
     130      ++i;
     131    }
    127132
    128   //std::cout << "maximum flow: "<< std::endl;
    129   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    130   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    131   //}
    132   //std::cout<<std::endl;
    133   std::cout << "elapsed time: " << ts << std::endl;
    134   std::cout << "number of augmentation phases: " << i << std::endl;
    135   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     133//   std::cout << "maximum flow: "<< std::endl;
     134//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     135//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     136//   }
     137//   std::cout<<std::endl;
     138    std::cout << "elapsed time: " << ts << std::endl;
     139    std::cout << "number of augmentation phases: " << i << std::endl;
     140    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    136141  }
    137142
    138143  {
    139   std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
    140   ListGraph::EdgeMap<int> flow(G); //0 flow
     144    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
     145    Graph::EdgeMap<int> flow(G); //0 flow
    141146
    142   Timer ts;
    143   ts.reset();
    144   //double pre_time=currTime();
    145   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    146   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    147   int i=0;
    148   while (max_flow_test.augmentOnShortestPath()) {
    149 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     147    Timer ts;
     148    ts.reset();
     149
     150    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     151    //max_flow_test.augmentWithBlockingFlow<Graph>();
     152    int i=0;
     153    while (max_flow_test.augmentOnShortestPath()) {
     154//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    150155//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    151156//     }
    152157//     std::cout<<std::endl;
    153     ++i;
     158      ++i;
     159    }
     160
     161//   std::cout << "maximum flow: "<< std::endl;
     162//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     163//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     164//   }
     165//   std::cout<<std::endl;
     166    std::cout << "elapsed time: " << ts << std::endl;
     167    std::cout << "number of augmentation phases: " << i << std::endl;
     168    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    154169  }
    155   //double post_time=currTime();
    156170
    157   //std::cout << "maximum flow: "<< std::endl;
    158   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    159   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    160   //}
    161   //std::cout<<std::endl;
    162   std::cout << "elapsed time: " << ts << std::endl;
    163   std::cout << "number of augmentation phases: " << i << std::endl;
    164   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    165   }
    166171
    167172  return 0;
Note: See TracChangeset for help on using the changeset viewer.