| 1 | #include <fstream>
|
|---|
| 2 | #include <boost/graph/adjacency_list.hpp>
|
|---|
| 3 | #include <boost/graph/graph_traits.hpp>
|
|---|
| 4 | #include <boost/graph/properties.hpp>
|
|---|
| 5 | #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
|
|---|
| 6 | #include <boost/graph/push_relabel_max_flow.hpp>
|
|---|
| 7 | #include <boost/graph/read_dimacs.hpp>
|
|---|
| 8 |
|
|---|
| 9 | typedef int FlowValue;
|
|---|
| 10 |
|
|---|
| 11 | int main (int argc, char **argv) {
|
|---|
| 12 | using namespace boost;
|
|---|
| 13 | typedef adjacency_list_traits <vecS, vecS, directedS> Traits;
|
|---|
| 14 | typedef adjacency_list <vecS, vecS, directedS,
|
|---|
| 15 | property <vertex_predecessor_t, Traits::edge_descriptor,
|
|---|
| 16 | property <vertex_color_t, default_color_type,
|
|---|
| 17 | property <vertex_distance_t, size_t> > >,
|
|---|
| 18 |
|
|---|
| 19 | property <edge_capacity_t, FlowValue,
|
|---|
| 20 | property <edge_residual_capacity_t, FlowValue,
|
|---|
| 21 | property <edge_reverse_t, Traits::edge_descriptor > > > > Graph;
|
|---|
| 22 |
|
|---|
| 23 | typedef Graph::vertex_descriptor Vertex;
|
|---|
| 24 |
|
|---|
| 25 | if (argc != 2) {
|
|---|
| 26 | std::cout << "Usage: test-flow infile.dimacs\n";
|
|---|
| 27 | exit(-1);
|
|---|
| 28 | }
|
|---|
| 29 |
|
|---|
| 30 | std::ifstream infile(argv[1]);
|
|---|
| 31 |
|
|---|
| 32 | Graph g;
|
|---|
| 33 | Vertex s, t;
|
|---|
| 34 |
|
|---|
| 35 | read_dimacs_max_flow(g, boost::get(edge_capacity, g), boost::get(edge_reverse, g), s, t, infile);
|
|---|
| 36 |
|
|---|
| 37 | FlowValue flow = boykov_kolmogorov_max_flow(g, s, t);
|
|---|
| 38 | std::cout << "BK flow: " << flow << "\n";
|
|---|
| 39 | flow = push_relabel_max_flow(g, s, t);
|
|---|
| 40 | std::cout << "PR flow: " << flow << "\n";
|
|---|
| 41 | }
|
|---|
