COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/read_dimacs_demo.cc @ 71:1d8d806ac8e0

Last change on this file since 71:1d8d806ac8e0 was 71:1d8d806ac8e0, checked in by marci, 16 years ago

read_dimacs_demo: measures elapsed time

File size: 1.2 KB
Line 
1#include <sys/time.h>
2#include <iostream>
3#include <fstream>
4
5#include <list_graph.hh>
6#include <dimacs.hh>
7#include <edmonds_karp.hh>
8
9using namespace marci;
10
11double currTime() {
12  timeval tv;
13  //timezone tz;
14  gettimeofday(&tv, 0);
15  return double(tv.tv_sec)+double(tv.tv_usec)/1000000.0;
16}
17
18// Use a DIMACS max flow file as stdin.
19// read_dimacs_demo < dimacs_flow_file
20int main(int, char **) {
21  typedef ListGraph::NodeIt NodeIt;
22  typedef ListGraph::EachEdgeIt EachEdgeIt;
23
24  ListGraph G;
25  NodeIt s, t;
26  ListGraph::EdgeMap<int> cap(G);
27  readDimacsMaxFlow(std::cin, G, s, t, cap);
28
29  std::cout << "augmenting path flow algorithm demo..." << std::endl;
30  ListGraph::EdgeMap<int> flow(G); //0 flow
31
32  double preTime=currTime();
33  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
34  max_flow_test.run();
35  double pushTime=currTime();
36  std::cout << "maximum flow: "<< std::endl;
37  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
38    std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
39  }
40  std::cout<<std::endl;
41  std::cout << "elapsed time: " << pushTime-preTime << " sec"<< std::endl;
42  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
43
44  return 0;
45}
Note: See TracBrowser for help on using the repository browser.