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