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
59 using namespace boost;
60 using namespace std;
61
62
63 enum edge_myflow_t { edge_myflow };
64 enum edge_mycapacity_t { edge_mycapacity };
65
66 namespace boost {
67 BOOST_INSTALL_PROPERTY(edge, myflow);
68 BOOST_INSTALL_PROPERTY(edge, mycapacity);
69 }
70
71
72 template <class Graph>
print_network(const Graph & G)73 void print_network(const Graph& G)
74 {
75 typedef typename boost::graph_traits<Graph>::vertex_iterator Viter;
76 typedef typename boost::graph_traits<Graph>::out_edge_iterator OutEdgeIter;
77 typedef typename boost::graph_traits<Graph>::in_edge_iterator InEdgeIter;
78
79 typename property_map<Graph, edge_mycapacity_t>::const_type
80 capacity = get(edge_mycapacity, G);
81 typename property_map<Graph, edge_myflow_t>::const_type
82 flow = get(edge_myflow, G);
83
84 Viter ui, uiend;
85 boost::tie(ui, uiend) = vertices(G);
86
87 for (; ui != uiend; ++ui) {
88 OutEdgeIter out, out_end;
89 cout << *ui << "\t";
90
91 boost::tie(out, out_end) = out_edges(*ui, G);
92 for(; out != out_end; ++out)
93 cout << "--(" << capacity[*out] << ", " << flow[*out] << ")--> "
94 << target(*out,G) << "\t";
95
96 InEdgeIter in, in_end;
97 cout << endl << "\t";
98 boost::tie(in, in_end) = in_edges(*ui, G);
99 for(; in != in_end; ++in)
100 cout << "<--(" << capacity[*in] << "," << flow[*in] << ")-- "
101 << source(*in,G) << "\t";
102
103 cout << endl;
104 }
105 }
106
107
main(int,char * [])108 int main(int , char* [])
109 {
110 typedef property<edge_mycapacity_t, int> Cap;
111 typedef property<edge_myflow_t, int, Cap> Flow;
112 typedef adjacency_list<vecS, vecS, bidirectionalS,
113 no_property, Flow> Graph;
114
115 const int num_vertices = 9;
116 Graph G(num_vertices);
117
118 /* 2<----5
119 / ^
120 / \
121 V \
122 0 ---->1---->3----->6--->8
123 \ ^
124 \ /
125 V /
126 4----->7
127 */
128
129 add_edge(0, 1, Flow(10, Cap(8)), G);
130
131 add_edge(1, 4, Flow(20, Cap(12)), G);
132 add_edge(4, 7, Flow(20, Cap(12)), G);
133 add_edge(7, 6, Flow(20, Cap(12)), G);
134
135 add_edge(1, 3, Flow(40, Cap(12)), G);
136 add_edge(3, 6, Flow(40, Cap(12)), G);
137
138 add_edge(6, 5, Flow(20, Cap(16)), G);
139 add_edge(5, 2, Flow(20, Cap(16)), G);
140 add_edge(2, 1, Flow(20, Cap(16)), G);
141
142 add_edge(6, 8, Flow(10, Cap(8)), G);
143
144 typedef boost::graph_traits<Graph>::edge_descriptor Edge;
145
146 print_network(G);
147
148 property_map<Graph, edge_myflow_t>::type
149 flow = get(edge_myflow, G);
150
151 boost::graph_traits<Graph>::vertex_iterator v, v_end;
152 boost::graph_traits<Graph>::out_edge_iterator e, e_end;
153 int f = 0;
154 for (boost::tie(v, v_end) = vertices(G); v != v_end; ++v)
155 for (boost::tie(e, e_end) = out_edges(*v, G); e != e_end; ++e)
156 flow[*e] = ++f;
157 cout << endl << endl;
158
159 remove_edge(6, 8, G);
160
161 print_network(G);
162
163
164 return 0;
165 }
166