|
marci@69
|
1 |
#include <iostream>
|
|
marci@69
|
2 |
#include <fstream>
|
|
marci@69
|
3 |
#include <list_graph.hh>
|
|
marci@69
|
4 |
#include <dimacs.hh>
|
|
marci@69
|
5 |
#include <edmonds_karp.hh>
|
|
marci@69
|
6 |
|
|
marci@69
|
7 |
using namespace marci;
|
|
marci@69
|
8 |
|
|
marci@69
|
9 |
// Use a DIMACS max flow file as stdin.
|
|
marci@69
|
10 |
// read_dimacs_demo < dimacs_flow_file
|
|
marci@69
|
11 |
int main(int, char **) {
|
|
marci@69
|
12 |
typedef ListGraph::NodeIt NodeIt;
|
|
marci@69
|
13 |
typedef ListGraph::EachEdgeIt EachEdgeIt;
|
|
marci@69
|
14 |
|
|
marci@69
|
15 |
ListGraph G;
|
|
marci@69
|
16 |
NodeIt s, t;
|
|
marci@69
|
17 |
ListGraph::EdgeMap<int> cap(G);
|
|
marci@69
|
18 |
readDimacsMaxFlow(std::cin, G, s, t, cap);
|
|
marci@69
|
19 |
|
|
marci@69
|
20 |
std::cout << "augmenting path flow algorithm demo..." << std::endl;
|
|
marci@69
|
21 |
ListGraph::EdgeMap<int> flow(G); //0 flow
|
|
marci@69
|
22 |
MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
|
|
marci@69
|
23 |
max_flow_test.run();
|
|
marci@69
|
24 |
|
|
marci@69
|
25 |
std::cout << "maximum flow: "<< std::endl;
|
|
marci@69
|
26 |
for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
|
|
marci@69
|
27 |
std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
|
|
marci@69
|
28 |
}
|
|
marci@69
|
29 |
std::cout<<std::endl;
|
|
marci@69
|
30 |
std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
|
|
marci@69
|
31 |
|
|
marci@69
|
32 |
return 0;
|
|
marci@69
|
33 |
}
|