]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/graph/example/push-relabel-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 //=======================================================================
8 #include <boost/config.hpp>
11 #include <boost/graph/push_relabel_max_flow.hpp>
12 #include <boost/graph/adjacency_list.hpp>
13 #include <boost/graph/read_dimacs.hpp>
15 // Use a DIMACS network flow file as stdin.
16 // push-relabel-eg < max_flow.dat
48 using namespace boost
;
49 typedef adjacency_list_traits
< vecS
, vecS
, directedS
> Traits
;
50 typedef adjacency_list
< vecS
, vecS
, directedS
,
51 property
< vertex_name_t
, std::string
>,
52 property
< edge_capacity_t
, long,
53 property
< edge_residual_capacity_t
, long,
54 property
< edge_reverse_t
, Traits::edge_descriptor
> > > > Graph
;
57 property_map
< Graph
, edge_capacity_t
>::type
58 capacity
= get(edge_capacity
, g
);
59 property_map
< Graph
, edge_residual_capacity_t
>::type
60 residual_capacity
= get(edge_residual_capacity
, g
);
61 property_map
< Graph
, edge_reverse_t
>::type rev
= get(edge_reverse
, g
);
62 Traits::vertex_descriptor s
, t
;
63 read_dimacs_max_flow(g
, capacity
, rev
, s
, t
);
65 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
66 property_map
<Graph
, vertex_index_t
>::type indexmap
= get(vertex_index
, g
);
67 long flow
= push_relabel_max_flow(g
, s
, t
, capacity
, residual_capacity
, rev
,
70 long flow
= push_relabel_max_flow(g
, s
, t
);
73 std::cout
<< "c The total flow:" << std::endl
;
74 std::cout
<< "s " << flow
<< std::endl
<< std::endl
;
75 std::cout
<< "c flow values:" << std::endl
;
76 graph_traits
< Graph
>::vertex_iterator u_iter
, u_end
;
77 graph_traits
< Graph
>::out_edge_iterator ei
, e_end
;
78 for (boost::tie(u_iter
, u_end
) = vertices(g
); u_iter
!= u_end
; ++u_iter
)
79 for (boost::tie(ei
, e_end
) = out_edges(*u_iter
, g
); ei
!= e_end
; ++ei
)
80 if (capacity
[*ei
] > 0)
81 std::cout
<< "f " << *u_iter
<< " " << target(*ei
, g
) << " "
82 << (capacity
[*ei
] - residual_capacity
[*ei
]) << std::endl
;