]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/max_flow.cpp
1 //=======================================================================
2 // Copyright 2000 University of Notre Dame.
3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
11 #define _CRT_SECURE_NO_WARNINGS
14 #include <boost/config.hpp>
17 #include <boost/graph/push_relabel_max_flow.hpp>
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/read_dimacs.hpp>
20 #include <boost/graph/graph_utility.hpp>
22 // Use a DIMACS network flow file as stdin.
23 // max_flow < max_flow.dat
53 using namespace boost
;
55 typedef adjacency_list_traits
< vecS
, vecS
, directedS
> Traits
;
56 typedef adjacency_list
< listS
, vecS
, directedS
,
57 property
< vertex_name_t
, std::string
>,
58 property
< edge_capacity_t
, long,
59 property
< edge_residual_capacity_t
, long,
60 property
< edge_reverse_t
, Traits::edge_descriptor
> > > >
65 property_map
< Graph
, edge_capacity_t
>::type capacity
66 = get(edge_capacity
, g
);
67 property_map
< Graph
, edge_reverse_t
>::type rev
= get(edge_reverse
, g
);
68 property_map
< Graph
, edge_residual_capacity_t
>::type residual_capacity
69 = get(edge_residual_capacity
, g
);
71 Traits::vertex_descriptor s
, t
;
72 read_dimacs_max_flow(g
, capacity
, rev
, s
, t
);
75 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
76 // Use non-named parameter version
77 property_map
< Graph
, vertex_index_t
>::type indexmap
= get(vertex_index
, g
);
78 flow
= push_relabel_max_flow(
79 g
, s
, t
, capacity
, residual_capacity
, rev
, indexmap
);
81 flow
= push_relabel_max_flow(g
, s
, t
);
84 std::cout
<< "c The total flow:" << std::endl
;
85 std::cout
<< "s " << flow
<< std::endl
<< std::endl
;
87 std::cout
<< "c flow values:" << std::endl
;
88 graph_traits
< Graph
>::vertex_iterator u_iter
, u_end
;
89 graph_traits
< Graph
>::out_edge_iterator ei
, e_end
;
90 for (boost::tie(u_iter
, u_end
) = vertices(g
); u_iter
!= u_end
; ++u_iter
)
91 for (boost::tie(ei
, e_end
) = out_edges(*u_iter
, g
); ei
!= e_end
; ++ei
)
92 if (capacity
[*ei
] > 0)
93 std::cout
<< "f " << *u_iter
<< " " << target(*ei
, g
) << " "
94 << (capacity
[*ei
] - residual_capacity
[*ei
])