src/work/marci/max_flow_1.cc
author alpar
Wed, 29 Sep 2004 15:30:04 +0000
changeset 921 818510fa3d99
parent 762 511200bdb71f
permissions -rw-r--r--
hugo -> lemon
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 
     5 #include <sage_graph.h>
     6 #include <lemon/smart_graph.h>
     7 #include <lemon/dimacs.h>
     8 #include <lemon/time_measure.h>
     9 //#include <graph_wrapper.h>
    10 #include <lemon/max_flow.h>
    11 //#include <preflow_res.h>
    12 #include <for_each_macros.h>
    13 
    14 using namespace lemon;
    15 
    16 // Use a DIMACS max flow file as stdin.
    17 // read_dimacs_demo < dimacs_max_flow_file
    18 
    19 
    20 int main(int, char **) {
    21 
    22   typedef SageGraph MutableGraph;
    23 
    24   typedef SmartGraph Graph;
    25   //  typedef ListGraph Graph;
    26   typedef Graph::Node Node;
    27   typedef Graph::EdgeIt EdgeIt;
    28 
    29 
    30   Graph g;
    31   Node s, t;
    32   Graph::EdgeMap<int> cap(g);
    33   //readDimacsMaxFlow(std::cin, g, s, t, cap);
    34   readDimacs(std::cin, g, cap, s, t);
    35   Timer ts;
    36   Graph::EdgeMap<int> flow(g); //0 flow
    37   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    38     max_flow_test(g, s, t, cap, flow);
    39 
    40   {
    41     std::cout << "preflow ..." << std::endl;
    42     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    43     ts.reset();
    44     max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
    45     std::cout << "elapsed time: " << ts << std::endl;
    46     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    47   }
    48 
    49   {
    50     std::cout << "preflow ..." << std::endl;
    51     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
    52     ts.reset();
    53     max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::ZERO_FLOW);
    54     std::cout << "elapsed time: " << ts << std::endl;
    55     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    56   }
    57 
    58 
    59   return 0;
    60 }