]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/edmonds-karp-eg.cpp
1 //=======================================================================
2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
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 //=======================================================================
10 #define _CRT_SECURE_NO_WARNINGS
13 #include <boost/config.hpp>
16 #include <boost/graph/edmonds_karp_max_flow.hpp>
17 #include <boost/graph/adjacency_list.hpp>
18 #include <boost/graph/read_dimacs.hpp>
19 #include <boost/graph/graph_utility.hpp>
21 // Use a DIMACS network flow file as stdin.
22 // edmonds-karp-eg < 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
> > > > Graph
;
64 property_map
< Graph
, edge_capacity_t
>::type
65 capacity
= get(edge_capacity
, g
);
66 property_map
< Graph
, edge_reverse_t
>::type rev
= get(edge_reverse
, g
);
67 property_map
< Graph
, edge_residual_capacity_t
>::type
68 residual_capacity
= get(edge_residual_capacity
, g
);
70 Traits::vertex_descriptor s
, t
;
71 read_dimacs_max_flow(g
, capacity
, rev
, s
, t
);
73 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
74 std::vector
<default_color_type
> color(num_vertices(g
));
75 std::vector
<Traits::edge_descriptor
> pred(num_vertices(g
));
76 long flow
= edmonds_karp_max_flow
77 (g
, s
, t
, capacity
, residual_capacity
, rev
, &color
[0], &pred
[0]);
79 long flow
= edmonds_karp_max_flow(g
, s
, t
);
82 std::cout
<< "c The total flow:" << std::endl
;
83 std::cout
<< "s " << flow
<< std::endl
<< std::endl
;
85 std::cout
<< "c flow values:" << std::endl
;
86 graph_traits
< Graph
>::vertex_iterator u_iter
, u_end
;
87 graph_traits
< Graph
>::out_edge_iterator ei
, e_end
;
88 for (boost::tie(u_iter
, u_end
) = vertices(g
); u_iter
!= u_end
; ++u_iter
)
89 for (boost::tie(ei
, e_end
) = out_edges(*u_iter
, g
); ei
!= e_end
; ++ei
)
90 if (capacity
[*ei
] > 0)
91 std::cout
<< "f " << *u_iter
<< " " << target(*ei
, g
) << " "
92 << (capacity
[*ei
] - residual_capacity
[*ei
]) << std::endl
;