1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
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 //=======================================================================
9 //
10 // Sample output:
11 //
12 // 0 --(8, 10)--> 1
13 //
14 // 1 --(12, 20)--> 4 --(12, 40)--> 3
15 // <--(8,10)-- 0 <--(16,20)-- 2
16 // 2 --(16, 20)--> 1
17 // <--(16,20)-- 5
18 // 3 --(12, 40)--> 6
19 // <--(12,40)-- 1
20 // 4 --(12, 20)--> 7
21 // <--(12,20)-- 1
22 // 5 --(16, 20)--> 2
23 // <--(16,20)-- 6
24 // 6 --(16, 20)--> 5 --(8, 10)--> 8
25 // <--(12,20)-- 7 <--(12,40)-- 3
26 // 7 --(12, 20)--> 6
27 // <--(12,20)-- 4
28 // 8
29 // <--(8,10)-- 6
30 //
31 //
32 // 0 --(8, 1)--> 1
33 //
34 // 1 --(12, 2)--> 4 --(12, 3)--> 3
35 // <--(8,1)-- 0 <--(16,4)-- 2
36 // 2 --(16, 4)--> 1
37 // <--(16,7)-- 5
38 // 3 --(12, 5)--> 6
39 // <--(12,3)-- 1
40 // 4 --(12, 6)--> 7
41 // <--(12,2)-- 1
42 // 5 --(16, 7)--> 2
43 // <--(16,8)-- 6
44 // 6 --(16, 8)--> 5
45 // <--(12,10)-- 7 <--(12,5)-- 3
46 // 7 --(12, 10)--> 6
47 // <--(12,6)-- 4
48 // 8
49 //
50
51 #include <boost/config.hpp>
52 #include <iostream>
53
54 #include <boost/utility.hpp>
55 #include <boost/property_map/property_map.hpp>
56 #include <boost/graph/adjacency_list.hpp>
57
58 using namespace boost;
59 using namespace std;
60
61 enum edge_myflow_t
62 {
63 edge_myflow
64 };
65 enum edge_mycapacity_t
66 {
67 edge_mycapacity
68 };
69
70 namespace boost
71 {
72 BOOST_INSTALL_PROPERTY(edge, myflow);
73 BOOST_INSTALL_PROPERTY(edge, mycapacity);
74 }
75
print_network(const Graph & G)76 template < class Graph > void print_network(const Graph& G)
77 {
78 typedef typename boost::graph_traits< Graph >::vertex_iterator Viter;
79 typedef
80 typename boost::graph_traits< Graph >::out_edge_iterator OutEdgeIter;
81 typedef typename boost::graph_traits< Graph >::in_edge_iterator InEdgeIter;
82
83 typename property_map< Graph, edge_mycapacity_t >::const_type capacity
84 = get(edge_mycapacity, G);
85 typename property_map< Graph, edge_myflow_t >::const_type flow
86 = get(edge_myflow, G);
87
88 Viter ui, uiend;
89 boost::tie(ui, uiend) = vertices(G);
90
91 for (; ui != uiend; ++ui)
92 {
93 OutEdgeIter out, out_end;
94 cout << *ui << "\t";
95
96 boost::tie(out, out_end) = out_edges(*ui, G);
97 for (; out != out_end; ++out)
98 cout << "--(" << capacity[*out] << ", " << flow[*out] << ")--> "
99 << target(*out, G) << "\t";
100
101 InEdgeIter in, in_end;
102 cout << endl << "\t";
103 boost::tie(in, in_end) = in_edges(*ui, G);
104 for (; in != in_end; ++in)
105 cout << "<--(" << capacity[*in] << "," << flow[*in] << ")-- "
106 << source(*in, G) << "\t";
107
108 cout << endl;
109 }
110 }
111
main(int,char * [])112 int main(int, char*[])
113 {
114 typedef property< edge_mycapacity_t, int > Cap;
115 typedef property< edge_myflow_t, int, Cap > Flow;
116 typedef adjacency_list< vecS, vecS, bidirectionalS, no_property, Flow >
117 Graph;
118
119 const int num_vertices = 9;
120 Graph G(num_vertices);
121
122 /* 2<----5
123 / ^
124 / \
125 V \
126 0 ---->1---->3----->6--->8
127 \ ^
128 \ /
129 V /
130 4----->7
131 */
132
133 add_edge(0, 1, Flow(10, Cap(8)), G);
134
135 add_edge(1, 4, Flow(20, Cap(12)), G);
136 add_edge(4, 7, Flow(20, Cap(12)), G);
137 add_edge(7, 6, Flow(20, Cap(12)), G);
138
139 add_edge(1, 3, Flow(40, Cap(12)), G);
140 add_edge(3, 6, Flow(40, Cap(12)), G);
141
142 add_edge(6, 5, Flow(20, Cap(16)), G);
143 add_edge(5, 2, Flow(20, Cap(16)), G);
144 add_edge(2, 1, Flow(20, Cap(16)), G);
145
146 add_edge(6, 8, Flow(10, Cap(8)), G);
147
148 print_network(G);
149
150 property_map< Graph, edge_myflow_t >::type flow = get(edge_myflow, G);
151
152 boost::graph_traits< Graph >::vertex_iterator v, v_end;
153 boost::graph_traits< Graph >::out_edge_iterator e, e_end;
154 int f = 0;
155 for (boost::tie(v, v_end) = vertices(G); v != v_end; ++v)
156 for (boost::tie(e, e_end) = out_edges(*v, G); e != e_end; ++e)
157 flow[*e] = ++f;
158 cout << endl << endl;
159
160 remove_edge(6, 8, G);
161
162 print_network(G);
163
164 return 0;
165 }
166