1 // Copyright (c) 2006, Stephan Diederich
2 //
3 // This code may be used under either of the following two licences:
4 //
5 // Permission is hereby granted, free of charge, to any person
6 // obtaining a copy of this software and associated documentation
7 // files (the "Software"), to deal in the Software without
8 // restriction, including without limitation the rights to use,
9 // copy, modify, merge, publish, distribute, sublicense, and/or
10 // sell copies of the Software, and to permit persons to whom the
11 // Software is furnished to do so, subject to the following
12 // conditions:
13 //
14 // The above copyright notice and this permission notice shall be
15 // included in all copies or substantial portions of the Software.
16 //
17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
25 //
26 // Or:
27 //
28 // Distributed under the Boost Software License, Version 1.0.
29 // (See accompanying file LICENSE_1_0.txt or copy at
30 // http://www.boost.org/LICENSE_1_0.txt)
31
32 #ifdef _MSC_VER
33 #define _CRT_SECURE_NO_WARNINGS
34 #endif
35 #include <boost/config.hpp>
36 #include <iostream>
37 #include <string>
38 #include <boost/graph/adjacency_list.hpp>
39 #include <boost/graph/read_dimacs.hpp>
40 #include <boost/graph/write_dimacs.hpp>
41
42 /*************************************
43 *
44 * example which reads in a max-flow problem from std::cin, augments all paths
45 *from source->NODE->sink and writes the graph back to std::cout
46 *
47 **************************************/
48
49 template < typename EdgeCapacityMap > struct zero_edge_capacity
50 {
51
zero_edge_capacityzero_edge_capacity52 zero_edge_capacity() {}
zero_edge_capacityzero_edge_capacity53 zero_edge_capacity(EdgeCapacityMap cap_map) : m_cap_map(cap_map) {};
54
operator ()zero_edge_capacity55 template < typename Edge > bool operator()(const Edge& e) const
56 {
57 return get(m_cap_map, e) == 0;
58 }
59
60 EdgeCapacityMap m_cap_map;
61 };
62
main()63 int main()
64 {
65 using namespace boost;
66 typedef adjacency_list_traits< vecS, vecS, directedS > Traits;
67 typedef adjacency_list< vecS, vecS, directedS, no_property,
68 property< edge_capacity_t, long,
69 property< edge_reverse_t, Traits::edge_descriptor > > >
70 Graph;
71
72 typedef graph_traits< Graph >::out_edge_iterator out_edge_iterator;
73 typedef graph_traits< Graph >::edge_descriptor edge_descriptor;
74 typedef graph_traits< Graph >::vertex_descriptor vertex_descriptor;
75
76 Graph g;
77
78 typedef property_map< Graph, edge_capacity_t >::type tCapMap;
79 typedef tCapMap::value_type tCapMapValue;
80
81 typedef property_map< Graph, edge_reverse_t >::type tRevEdgeMap;
82
83 tCapMap capacity = get(edge_capacity, g);
84 tRevEdgeMap rev = get(edge_reverse, g);
85
86 vertex_descriptor s, t;
87 /*reading the graph from stdin*/
88 read_dimacs_max_flow(g, capacity, rev, s, t, std::cin);
89
90 /*process graph*/
91 tCapMapValue augmented_flow = 0;
92
93 // we take the source node and check for each outgoing edge e which has a
94 // target(p) if we can augment that path
95 out_edge_iterator oei, oe_end;
96 for (boost::tie(oei, oe_end) = out_edges(s, g); oei != oe_end; ++oei)
97 {
98 edge_descriptor from_source = *oei;
99 vertex_descriptor v = target(from_source, g);
100 edge_descriptor to_sink;
101 bool is_there;
102 boost::tie(to_sink, is_there) = edge(v, t, g);
103 if (is_there)
104 {
105 if (get(capacity, to_sink) > get(capacity, from_source))
106 {
107 tCapMapValue to_augment = get(capacity, from_source);
108 capacity[from_source] = 0;
109 capacity[to_sink] -= to_augment;
110 augmented_flow += to_augment;
111 }
112 else
113 {
114 tCapMapValue to_augment = get(capacity, to_sink);
115 capacity[to_sink] = 0;
116 capacity[from_source] -= to_augment;
117 augmented_flow += to_augment;
118 }
119 }
120 }
121
122 // remove edges with zero capacity (most of them are the reverse edges)
123 zero_edge_capacity< tCapMap > filter(capacity);
124 remove_edge_if(filter, g);
125
126 /*write the graph back to stdout */
127 write_dimacs_max_flow(
128 g, capacity, identity_property_map(), s, t, std::cout);
129 // print flow we augmented to std::cerr
130 std::cerr << "removed " << augmented_flow
131 << " from SOURCE->NODE->SINK connects" << std::endl;
132 return 0;
133 }
134