src/work/marci/preflow_demo_jacint.cc
author athos
Tue, 11 May 2004 16:38:17 +0000
changeset 611 83530dad618a
parent 100 f1de2ab64e1c
child 921 818510fa3d99
permissions -rw-r--r--
Some modifications and another testfile.
     1 #include <iostream>
     2 #include <fstream>
     3 
     4 #include <list_graph.hh>
     5 #include <dimacs.hh>
     6 #include <preflow_push_max_flow.h>
     7 #include <preflow_push_hl.h>
     8 #include <time_measure.h>
     9 
    10 using namespace hugo;
    11 
    12 // Use a DIMACS max flow file as stdin.
    13 // read_dimacs_demo < dimacs_max_flow_file
    14 int main(int, char **) {
    15   typedef ListGraph::NodeIt NodeIt;
    16   typedef ListGraph::EachEdgeIt EachEdgeIt;
    17 
    18   ListGraph G;
    19   NodeIt s, t;
    20   ListGraph::EdgeMap<int> cap(G);
    21   readDimacsMaxFlow(std::cin, G, s, t, cap);
    22 
    23   {
    24   std::cout << "preflow demo (preflow_push_max_flow by JACINT)..." << std::endl;
    25   //ListGraph::EdgeMap<int> flow(G); //0 flow
    26 
    27   double pre_time=currTime();
    28   preflow_push_max_flow<ListGraph, int> max_flow_test(G, s, t, cap);
    29   max_flow_test.run();
    30   ListGraph::NodeMap<bool> cut(G); 
    31   max_flow_test.mincut(cut);
    32   int cut_value=0;
    33   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    34     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
    35   }
    36   double post_time=currTime();
    37   //std::cout << "maximum flow: "<< std::endl;
    38   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
    39   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    40   //}
    41   //std::cout<<std::endl;
    42   std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
    43   std::cout << "flow value: "<< max_flow_test.maxflow() << std::endl;
    44   std::cout << "cut value: "<< cut_value << std::endl;
    45   }
    46 
    47     {
    48   std::cout << "preflow demo (preflow_push_hl by JACINT)..." << std::endl;
    49   //ListGraph::EdgeMap<int> flow(G); //0 flow
    50 
    51   double pre_time=currTime();
    52   preflow_push_hl<ListGraph, int> max_flow_test(G, s, t, cap);
    53   max_flow_test.run();
    54   ListGraph::NodeMap<bool> cut(G);
    55   max_flow_test.mincut(cut);
    56   int cut_value=0;
    57   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    58     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
    59   }
    60   double post_time=currTime();
    61   //std::cout << "maximum flow: "<< std::endl;
    62   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
    63   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    64   //}
    65   //std::cout<<std::endl;
    66   std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
    67   std::cout << "flow value: "<< max_flow_test.maxflow() << std::endl;
    68   std::cout << "cut value: "<< cut_value << std::endl;
    69   }
    70 
    71 
    72   return 0;
    73 }