src/work/marci/leda_graph_demo.cc
author marci
Fri, 21 May 2004 10:57:30 +0000
changeset 655 a9878222d5c8
parent 181 96f647f568c7
child 921 818510fa3d99
permissions -rw-r--r--
bug correction in BidirGraphWrapper<Graph> default constructor
marci@181
     1
// -*- c++ -*-
marci@181
     2
#include <iostream>
marci@181
     3
#include <fstream>
marci@181
     4
marci@181
     5
#include <LEDA/graph.h>
marci@189
     6
#include <leda_graph_wrapper.h>
marci@181
     7
#include <dimacs.h>
marci@181
     8
#include <time_measure.h>
marci@181
     9
#include <edmonds_karp.h>
marci@181
    10
marci@181
    11
using namespace hugo;
marci@181
    12
marci@181
    13
using std::cout; 
marci@181
    14
using std::endl;
marci@181
    15
marci@181
    16
int main() {
marci@181
    17
  leda::graph g;
marci@189
    18
  typedef LedaGraphWrapper<leda::graph> Graph;
marci@181
    19
  Graph G(g);
marci@181
    20
//   G.addNode();
marci@181
    21
//   G.addNode();
marci@181
    22
//   std::cout << G.nodeNum() << std::endl; 
marci@181
    23
marci@181
    24
  typedef Graph::Node Node;
marci@181
    25
  typedef Graph::NodeIt NodeIt;  
marci@181
    26
  typedef Graph::Edge Edge;
marci@181
    27
  typedef Graph::EdgeIt EdgeIt;
marci@181
    28
  typedef Graph::OutEdgeIt OutEdgeIt;
marci@181
    29
  typedef Graph::InEdgeIt InEdgeIt;
marci@181
    30
marci@181
    31
  Node s, t;
marci@181
    32
  Graph::EdgeMap<int> cap(G);
marci@181
    33
  readDimacsMaxFlow(std::cin, G, s, t, cap);
marci@181
    34
marci@181
    35
marci@181
    36
//   cout << "bfs and dfs iterator demo on the directed graph" << endl;
marci@181
    37
//   for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
marci@181
    38
//     cout << G.id(n) << ": ";
marci@181
    39
//     cout << "out edges: ";
marci@181
    40
//     for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
marci@181
    41
//       cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";
marci@181
    42
//     cout << "in edges: ";
marci@181
    43
//     for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
marci@181
    44
//       cout << G.id(G.tail(e)) << "-" << cap.get(e) << "->" << G.id(G.head(e)) << " ";
marci@181
    45
//     cout << endl;
marci@181
    46
//   }
marci@181
    47
marci@181
    48
//   int i=0;
marci@181
    49
//   for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cap.set(e, i); i+=3; }
marci@181
    50
//   for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) { cout << cap.get(e) << " "; }
marci@181
    51
//   cout << endl;
marci@181
    52
marci@181
    53
  {
marci@181
    54
    //std::cout << "SmartGraph..." << std::endl;
marci@181
    55
    std::cout << "on-the-fly edmonds karp demo on wrapped leda graph..." << std::endl;
marci@181
    56
    Graph::EdgeMap<int> flow(G); //0 flow
marci@181
    57
marci@181
    58
marci@181
    59
    Timer ts;
marci@181
    60
    ts.reset();
marci@181
    61
marci@181
    62
    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
marci@181
    63
    //max_flow_test.augmentWithBlockingFlow<Graph>();
marci@181
    64
    int i=0;
marci@181
    65
    while (max_flow_test.augmentOnShortestPath()) { 
marci@181
    66
//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
marci@181
    67
//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@181
    68
//     }
marci@181
    69
//     std::cout<<std::endl;
marci@181
    70
      ++i; 
marci@181
    71
    }
marci@181
    72
marci@181
    73
//   std::cout << "maximum flow: "<< std::endl;
marci@181
    74
//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
marci@181
    75
//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@181
    76
//   }
marci@181
    77
//   std::cout<<std::endl;
marci@181
    78
    std::cout << "elapsed time: " << ts << std::endl;
marci@181
    79
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@181
    80
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@181
    81
  }
marci@181
    82
  
marci@181
    83
marci@181
    84
  return 0;
marci@181
    85
}