1 | // Boost Graph library |
2 | |
3 | // Copyright Douglas Gregor 2004. Use, modification and |
4 | // distribution is subject to the Boost Software License, Version |
5 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | |
8 | #include <boost/core/lightweight_test.hpp> |
9 | #include <boost/graph/adjacency_list.hpp> |
10 | #include <boost/graph/adjacency_matrix.hpp> |
11 | #include <boost/graph/filtered_graph.hpp> |
12 | #include <boost/graph/subgraph.hpp> |
13 | #include <string> |
14 | #include <vector> |
15 | #include <boost/graph/adjacency_list_io.hpp> |
16 | #include <sstream> |
17 | #include <boost/graph/iteration_macros.hpp> |
18 | #include <algorithm> |
19 | #include <iterator> |
20 | |
21 | using namespace std; |
22 | using namespace boost; |
23 | |
24 | struct City |
25 | { |
26 | City() {} |
27 | City(const std::string& name, int pop, int zipcode) |
28 | : name(name), population(pop) |
29 | { |
30 | zipcodes.push_back(x: zipcode); |
31 | } |
32 | |
33 | string name; |
34 | int population; |
35 | vector< int > zipcodes; |
36 | }; |
37 | |
38 | std::ostream& operator<<(std::ostream& out, const City& city) |
39 | { |
40 | out << city.name << ' ' << city.population << ' '; |
41 | copy(first: city.zipcodes.begin(), last: city.zipcodes.end(), |
42 | result: ostream_iterator< int >(out, " " )); |
43 | out << -1; |
44 | return out; |
45 | } |
46 | |
47 | std::istream& operator>>(std::istream& in, City& city) |
48 | { |
49 | if (in >> city.name >> city.population) |
50 | { |
51 | int zip; |
52 | city.zipcodes.clear(); |
53 | while (in >> zip && zip != -1) |
54 | city.zipcodes.push_back(x: zip); |
55 | } |
56 | return in; |
57 | } |
58 | |
59 | bool operator==(const City& c1, const City& c2) |
60 | { |
61 | return (c1.name == c2.name && c1.population == c2.population |
62 | && c1.zipcodes == c2.zipcodes); |
63 | } |
64 | |
65 | struct Highway |
66 | { |
67 | Highway() {} |
68 | Highway(const string& name, double miles, int speed_limit = 65, |
69 | int lanes = 4, bool divided = true) |
70 | : name(name) |
71 | , miles(miles) |
72 | , speed_limit(speed_limit) |
73 | , lanes(lanes) |
74 | , divided(divided) |
75 | { |
76 | } |
77 | |
78 | string name; |
79 | double miles; |
80 | int speed_limit; |
81 | int lanes; |
82 | bool divided; |
83 | }; |
84 | |
85 | std::ostream& operator<<(std::ostream& out, const Highway& highway) |
86 | { |
87 | return out << highway.name << ' ' << highway.miles << ' ' << highway.miles |
88 | << ' ' << highway.speed_limit << ' ' << highway.lanes << ' ' |
89 | << highway.divided; |
90 | } |
91 | |
92 | std::istream& operator>>(std::istream& in, Highway& highway) |
93 | { |
94 | return in >> highway.name >> highway.miles >> highway.miles |
95 | >> highway.speed_limit >> highway.lanes >> highway.divided; |
96 | } |
97 | |
98 | bool operator==(const Highway& h1, const Highway& h2) |
99 | { |
100 | return (h1.name == h2.name && h1.miles == h2.miles |
101 | && h1.speed_limit == h2.speed_limit && h1.lanes == h2.lanes |
102 | && h1.divided == h2.divided); |
103 | } |
104 | |
105 | template < bool > struct truth |
106 | { |
107 | }; |
108 | |
109 | template < typename Map, typename VertexIterator, typename Bundle > |
110 | typename boost::graph_traits< Map >::vertex_descriptor do_add_vertex( |
111 | Map& map, VertexIterator, const Bundle& bundle, truth< true >) |
112 | { |
113 | return add_vertex(bundle, map); |
114 | } |
115 | |
116 | template < typename Map, typename VertexIterator, typename Bundle > |
117 | typename boost::graph_traits< Map >::vertex_descriptor do_add_vertex( |
118 | Map& map, VertexIterator& vi, const Bundle& bundle, truth< false >) |
119 | { |
120 | get(boost::vertex_bundle, map)[*vi] = bundle; |
121 | return *vi++; |
122 | } |
123 | |
124 | template < class EL, class VL, class D, class VP, class EP, class GP > |
125 | void test_io(adjacency_list< EL, VL, D, VP, EP, GP >& map, int) |
126 | { |
127 | typedef adjacency_list< EL, VL, D, VP, EP, GP > Map; |
128 | |
129 | ostringstream out; |
130 | cout << write(map); |
131 | out << write(map); |
132 | |
133 | istringstream in(out.str()); |
134 | adjacency_list< EL, VL, D, VP, EP, GP > map2; |
135 | in >> read(map2); |
136 | typename graph_traits< |
137 | adjacency_list< EL, VL, D, VP, EP, GP > >::vertex_iterator v2 |
138 | = vertices(map2).first; |
139 | BGL_FORALL_VERTICES_T(v, map, Map) |
140 | { |
141 | BOOST_TEST(map[v] == map2[*v2]); |
142 | typename graph_traits< |
143 | adjacency_list< EL, VL, D, VP, EP, GP > >::out_edge_iterator e2 |
144 | = out_edges(*v2, map2).first; |
145 | BGL_FORALL_OUTEDGES_T(v, e, map, Map) |
146 | { |
147 | BOOST_TEST(map[e] == map[*e2]); |
148 | ++e2; |
149 | } |
150 | ++v2; |
151 | } |
152 | } |
153 | |
154 | template < typename Map > void test_io(const Map&, long) |
155 | { |
156 | // Nothing to test |
157 | } |
158 | |
159 | template < typename Map, bool CanAddVertex > |
160 | void test_bundled_properties(Map*, truth< CanAddVertex > can_add_vertex) |
161 | { |
162 | typedef |
163 | typename boost::graph_traits< Map >::vertex_iterator vertex_iterator; |
164 | typedef typename boost::graph_traits< Map >::vertex_descriptor |
165 | vertex_descriptor; |
166 | typedef |
167 | typename boost::graph_traits< Map >::edge_descriptor edge_descriptor; |
168 | |
169 | Map map(CanAddVertex ? 2 : 3); |
170 | |
171 | vertex_iterator vi = vertices(map).first; |
172 | vertex_descriptor v = *vi; |
173 | map[v].name = "Troy" ; |
174 | map[v].population = 49170; |
175 | map[v].zipcodes.push_back(12180); |
176 | |
177 | ++vi; |
178 | vertex_descriptor u = *vi++; |
179 | map[u].name = "Albany" ; |
180 | map[u].population = 95658; |
181 | map[u].zipcodes.push_back(12201); |
182 | |
183 | // Try adding a vertex with a property value |
184 | vertex_descriptor bloomington = do_add_vertex( |
185 | map, vi, City("Bloomington" , 39000, 47401), can_add_vertex); |
186 | BOOST_TEST( |
187 | get(boost::vertex_bundle, map)[bloomington].zipcodes[0] == 47401); |
188 | |
189 | edge_descriptor e = add_edge(v, u, map).first; |
190 | map[e].name = "I-87" ; |
191 | map[e].miles = 10; |
192 | map[e].speed_limit = 65; |
193 | map[e].lanes = 4; |
194 | map[e].divided = true; |
195 | |
196 | edge_descriptor our_trip |
197 | = add_edge(v, bloomington, Highway("Long" , 1000), map).first; |
198 | BOOST_TEST(get(boost::edge_bundle, map, our_trip).miles == 1000); |
199 | |
200 | BOOST_TEST(get(get(&City::name, map), v) == "Troy" ); |
201 | BOOST_TEST(get(get(&Highway::name, map), e) == "I-87" ); |
202 | BOOST_TEST(get(&City::name, map, u) == "Albany" ); |
203 | BOOST_TEST(get(&Highway::name, map, e) == "I-87" ); |
204 | put(&City::population, map, v, 49168); |
205 | BOOST_TEST(get(&City::population, map)[v] == 49168); |
206 | |
207 | boost::filtered_graph< Map, boost::keep_all > fmap(map, boost::keep_all()); |
208 | BOOST_TEST(get(boost::edge_bundle, map, our_trip).miles == 1000); |
209 | |
210 | BOOST_TEST(get(get(&City::name, fmap), v) == "Troy" ); |
211 | BOOST_TEST(get(get(&Highway::name, fmap), e) == "I-87" ); |
212 | BOOST_TEST(get(&City::name, fmap, u) == "Albany" ); |
213 | BOOST_TEST(get(&Highway::name, fmap, e) == "I-87" ); |
214 | put(&City::population, fmap, v, 49169); |
215 | BOOST_TEST(get(&City::population, fmap)[v] == 49169); |
216 | |
217 | test_io(map, 0); |
218 | } |
219 | |
220 | void test_subgraph_bundled_properties() |
221 | { |
222 | typedef boost::subgraph< |
223 | boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, |
224 | City, boost::property< boost::edge_index_t, int, Highway > > > |
225 | SubMap; |
226 | typedef boost::graph_traits< SubMap >::vertex_descriptor Vertex; |
227 | typedef boost::graph_traits< SubMap >::vertex_iterator vertex_iterator; |
228 | |
229 | SubMap map(3); |
230 | vertex_iterator vi = vertices(g: map).first; |
231 | Vertex troy = *vi++; |
232 | map[troy].name = "Troy" ; |
233 | map[*vi++].name = "Bloomington" ; |
234 | map[*vi++].name = "Endicott" ; |
235 | |
236 | SubMap& g1 = map.create_subgraph(); |
237 | Vertex troy1 = add_vertex(u_global: *vertices(g: map).first, g&: g1); |
238 | BOOST_TEST(map[troy1].name == g1[troy1].name); |
239 | } |
240 | |
241 | int main(int, char*[]) |
242 | { |
243 | typedef boost::adjacency_list< boost::listS, boost::vecS, |
244 | boost::bidirectionalS, City, Highway > |
245 | Map1; |
246 | typedef boost::adjacency_matrix< boost::directedS, City, Highway > Map2; |
247 | |
248 | test_bundled_properties(static_cast< Map1* >(0), can_add_vertex: truth< true >()); |
249 | test_bundled_properties(static_cast< Map2* >(0), can_add_vertex: truth< false >()); |
250 | test_subgraph_bundled_properties(); |
251 | return boost::report_errors(); |
252 | } |
253 | |