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