]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | // | |
f67539c2 | 12 | // 0 --(8, 10)--> 1 |
7c673cae | 13 | // |
f67539c2 TL |
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 | |
7c673cae FG |
30 | // |
31 | // | |
f67539c2 | 32 | // 0 --(8, 1)--> 1 |
7c673cae | 33 | // |
f67539c2 TL |
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 | |
7c673cae | 49 | // |
f67539c2 | 50 | |
7c673cae FG |
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 | ||
7c673cae FG |
58 | using namespace boost; |
59 | using namespace std; | |
60 | ||
f67539c2 TL |
61 | enum edge_myflow_t |
62 | { | |
63 | edge_myflow | |
64 | }; | |
65 | enum edge_mycapacity_t | |
66 | { | |
67 | edge_mycapacity | |
68 | }; | |
7c673cae | 69 | |
f67539c2 TL |
70 | namespace boost |
71 | { | |
72 | BOOST_INSTALL_PROPERTY(edge, myflow); | |
73 | BOOST_INSTALL_PROPERTY(edge, mycapacity); | |
7c673cae FG |
74 | } |
75 | ||
f67539c2 | 76 | template < class Graph > void print_network(const Graph& G) |
7c673cae | 77 | { |
f67539c2 TL |
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 | } | |
7c673cae FG |
110 | } |
111 | ||
f67539c2 | 112 | int main(int, char*[]) |
7c673cae | 113 | { |
f67539c2 TL |
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; | |
7c673cae | 118 | |
f67539c2 TL |
119 | const int num_vertices = 9; |
120 | Graph G(num_vertices); | |
7c673cae | 121 | |
f67539c2 TL |
122 | /* 2<----5 |
123 | / ^ | |
124 | / \ | |
125 | V \ | |
126 | 0 ---->1---->3----->6--->8 | |
127 | \ ^ | |
128 | \ / | |
129 | V / | |
130 | 4----->7 | |
131 | */ | |
7c673cae | 132 | |
f67539c2 | 133 | add_edge(0, 1, Flow(10, Cap(8)), G); |
7c673cae | 134 | |
f67539c2 TL |
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); | |
7c673cae | 138 | |
f67539c2 TL |
139 | add_edge(1, 3, Flow(40, Cap(12)), G); |
140 | add_edge(3, 6, Flow(40, Cap(12)), G); | |
7c673cae | 141 | |
f67539c2 TL |
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); | |
7c673cae | 145 | |
f67539c2 | 146 | add_edge(6, 8, Flow(10, Cap(8)), G); |
7c673cae | 147 | |
f67539c2 | 148 | print_network(G); |
7c673cae | 149 | |
f67539c2 | 150 | property_map< Graph, edge_myflow_t >::type flow = get(edge_myflow, G); |
7c673cae | 151 | |
f67539c2 TL |
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; | |
7c673cae | 159 | |
f67539c2 | 160 | remove_edge(6, 8, G); |
7c673cae | 161 | |
f67539c2 | 162 | print_network(G); |
7c673cae | 163 | |
f67539c2 | 164 | return 0; |
7c673cae | 165 | } |