COIN-OR::LEMON - Graph Library

Changeset 211:9222a9b8b323 in lemon-0.x for src/work/jacint/preflow.cc


Ignore:
Timestamp:
03/19/04 23:16:05 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@306
Message:

updating

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow.cc

    r113 r211  
    22#include <fstream>
    33
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
     4#include <list_graph.h>
     5#include <dimacs.h>
    66#include <preflow.h>
    77#include <time_measure.h>
     
    1212// read_dimacs_demo < dimacs_max_flow_file
    1313int main(int, char **) {
    14   typedef ListGraph::NodeIt NodeIt;
    15   typedef ListGraph::EachEdgeIt EachEdgeIt;
     14  typedef ListGraph::Node Node;
     15  typedef ListGraph::EdgeIt EdgeIt;
    1616
    1717  ListGraph G;
    18   NodeIt s, t;
     18  Node s, t;
    1919  ListGraph::EdgeMap<int> cap(G);
    2020  readDimacsMaxFlow(std::cin, G, s, t, cap);
     
    2525
    2626  for ( int i=1; i!=11; ++i ) {
     27    ListGraph::EdgeMap<int> flow(G);
    2728    double pre_time=currTime();
    28     preflow<ListGraph, int> max_flow_test(G, s, t, cap);
     29    Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     30    max_flow_test.run();
    2931    double post_time=currTime();
    3032    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
    3133  }
    3234
    33   double pre_time=currTime();
    34     preflow<ListGraph, int> max_flow_test(G, s, t, cap);
    35   double post_time=currTime();
    36    
     35  ListGraph::EdgeMap<int> flow(G);
     36  Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     37  max_flow_test.run();
     38 
    3739  ListGraph::NodeMap<bool> cut(G);
    3840  max_flow_test.minCut(cut);
    3941  int min_cut_value=0;
    40   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     42  EdgeIt e;
     43  for(G.first(e); G.valid(e); G.next(e)) {
    4144    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
    4245  }
     
    4548  max_flow_test.minMinCut(cut1);
    4649  int min_min_cut_value=0;
    47   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     50  for(G.first(e); G.valid(e); G.next(e)) {
    4851    if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
    4952      min_min_cut_value+=cap.get(e);
     
    5356  max_flow_test.maxMinCut(cut2);
    5457  int max_min_cut_value=0;
    55   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     58  for(G.first(e); G.valid(e); G.next(e)) {
    5659    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
    5760      max_min_cut_value+=cap.get(e);
     
    5962 
    6063  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
    61   std::cout << "phase 0: " << max_flow_test.time-pre_time
    62             << " sec"<< std::endl;
    63   std::cout << "phase 1: " << post_time-max_flow_test.time
    64             << " sec"<< std::endl;
    65   std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
     64  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6665  std::cout << "min cut value: "<< min_cut_value << std::endl;
    6766  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
Note: See TracChangeset for help on using the changeset viewer.