COIN-OR::LEMON - Graph Library

Changeset 220:7deda4d6a07a in lemon-0.x for src/work/jacint/preflow.cc


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

* empty log message *

File:
1 edited

Legend:

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

    r211 r220  
    22#include <fstream>
    33
     4#include <smart_graph.h>
    45#include <list_graph.h>
    56#include <dimacs.h>
     
    1213// read_dimacs_demo < dimacs_max_flow_file
    1314int main(int, char **) {
    14   typedef ListGraph::Node Node;
    15   typedef ListGraph::EdgeIt EdgeIt;
     15  typedef SmartGraph::Node Node;
     16  typedef SmartGraph::EdgeIt EdgeIt;
    1617
    17   ListGraph G;
     18  SmartGraph G;
    1819  Node s, t;
    19   ListGraph::EdgeMap<int> cap(G);
     20  SmartGraph::EdgeMap<int> cap(G);
    2021  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2122
     
    2526
    2627  for ( int i=1; i!=11; ++i ) {
    27     ListGraph::EdgeMap<int> flow(G);
     28    SmartGraph::EdgeMap<int> flow(G);
    2829    double pre_time=currTime();
    29     Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     30    Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
    3031    max_flow_test.run();
    3132    double post_time=currTime();
     
    3334  }
    3435
    35   ListGraph::EdgeMap<int> flow(G);
    36   Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     36  SmartGraph::EdgeMap<int> flow(G);
     37  Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
    3738  max_flow_test.run();
    3839 
    39   ListGraph::NodeMap<bool> cut(G);
     40  SmartGraph::NodeMap<bool> cut(G);
    4041  max_flow_test.minCut(cut);
    4142  int min_cut_value=0;
    4243  EdgeIt e;
    4344  for(G.first(e); G.valid(e); G.next(e)) {
    44     if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
     45    if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=cap[e];
    4546  }
    4647
    47   ListGraph::NodeMap<bool> cut1(G);
     48  SmartGraph::NodeMap<bool> cut1(G);
    4849  max_flow_test.minMinCut(cut1);
    4950  int min_min_cut_value=0;
    5051  for(G.first(e); G.valid(e); G.next(e)) {
    51     if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
    52       min_min_cut_value+=cap.get(e);
     52    if (cut[G.tail(e)] && !cut[G.head(e)])
     53      min_min_cut_value+=cap[e];
    5354  }
    5455
    55   ListGraph::NodeMap<bool> cut2(G);
     56  SmartGraph::NodeMap<bool> cut2(G);
    5657  max_flow_test.maxMinCut(cut2);
    5758  int max_min_cut_value=0;
    5859  for(G.first(e); G.valid(e); G.next(e)) {
    59     if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
    60       max_min_cut_value+=cap.get(e);
     60    if (cut2[G.tail(e)] && !cut2[G.head(e)])
     61      max_min_cut_value+=cap[e];
    6162      }
    6263 
Note: See TracChangeset for help on using the changeset viewer.