projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | //======================================================================= |
| 2 | // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, | |
| 3 | // | |
| 4 | // Distributed under the Boost Software License, Version 1.0. (See | |
| 5 | // accompanying file LICENSE_1_0.txt or copy at | |
| 6 | // http://www.boost.org/LICENSE_1_0.txt) | |
| 7 | //======================================================================= | |
| 92f5a8d4 TL |
8 | #ifdef _MSC_VER |
| 9 | #define _CRT_SECURE_NO_WARNINGS | |
| 10 | #endif | |
| 7c673cae FG |
11 | #include <boost/config.hpp> |
| 12 | #include <iostream> | |
| 13 | #include <string> | |
| 14 | #include <boost/graph/push_relabel_max_flow.hpp> | |
| 15 | #include <boost/graph/adjacency_list.hpp> | |
| 16 | #include <boost/graph/read_dimacs.hpp> | |
| 17 | ||
| 18 | // Use a DIMACS network flow file as stdin. | |
| 19 | // push-relabel-eg < max_flow.dat | |
| 20 | // | |
| 21 | // Sample output: | |
| 22 | // c The total flow: | |
| 23 | // s 13 | |
| 24 | // | |
| 25 | // c flow values: | |
| 26 | // f 0 6 3 | |
| 27 | // f 0 1 0 | |
| 28 | // f 0 2 10 | |
| 29 | // f 1 5 1 | |
| 30 | // f 1 0 0 | |
| 31 | // f 1 3 0 | |
| 32 | // f 2 4 4 | |
| 33 | // f 2 3 6 | |
| 34 | // f 2 0 0 | |
| 35 | // f 3 7 5 | |
| 36 | // f 3 2 0 | |
| 37 | // f 3 1 1 | |
| 38 | // f 4 5 4 | |
| 39 | // f 4 6 0 | |
| 40 | // f 5 4 0 | |
| 41 | // f 5 7 5 | |
| 42 | // f 6 7 3 | |
| 43 | // f 6 4 0 | |
| 44 | // f 7 6 0 | |
| 45 | // f 7 5 0 | |
| 46 | ||
| 47 | ||
| 48 | int | |
| 49 | main() | |
| 50 | { | |
| 51 | using namespace boost; | |
| 52 | typedef adjacency_list_traits < vecS, vecS, directedS > Traits; | |
| 53 | typedef adjacency_list < vecS, vecS, directedS, | |
| 54 | property < vertex_name_t, std::string >, | |
| 55 | property < edge_capacity_t, long, | |
| 56 | property < edge_residual_capacity_t, long, | |
| 57 | property < edge_reverse_t, Traits::edge_descriptor > > > > Graph; | |
| 58 | Graph g; | |
| 59 | ||
| 60 | property_map < Graph, edge_capacity_t >::type | |
| 61 | capacity = get(edge_capacity, g); | |
| 62 | property_map < Graph, edge_residual_capacity_t >::type | |
| 63 | residual_capacity = get(edge_residual_capacity, g); | |
| 64 | property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g); | |
| 65 | Traits::vertex_descriptor s, t; | |
| 66 | read_dimacs_max_flow(g, capacity, rev, s, t); | |
| 67 | ||
| 68 | #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 | |
| 69 | property_map<Graph, vertex_index_t>::type indexmap = get(vertex_index, g); | |
| 70 | long flow = push_relabel_max_flow(g, s, t, capacity, residual_capacity, rev, | |
| 71 | indexmap); | |
| 72 | #else | |
| 73 | long flow = push_relabel_max_flow(g, s, t); | |
| 74 | #endif | |
| 75 | ||
| 76 | std::cout << "c The total flow:" << std::endl; | |
| 77 | std::cout << "s " << flow << std::endl << std::endl; | |
| 78 | std::cout << "c flow values:" << std::endl; | |
| 79 | graph_traits < Graph >::vertex_iterator u_iter, u_end; | |
| 80 | graph_traits < Graph >::out_edge_iterator ei, e_end; | |
| 81 | for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) | |
| 82 | for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) | |
| 83 | if (capacity[*ei] > 0) | |
| 84 | std::cout << "f " << *u_iter << " " << target(*ei, g) << " " | |
| 85 | << (capacity[*ei] - residual_capacity[*ei]) << std::endl; | |
| 86 | return EXIT_SUCCESS; | |
| 87 | } |