]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | //======================================================================= | |
3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | //======================================================================= | |
10 | // | |
11 | #ifndef BOOST_GRAPH_UTILITY_HPP | |
12 | #define BOOST_GRAPH_UTILITY_HPP | |
13 | ||
14 | #include <stdlib.h> | |
15 | #include <iostream> | |
16 | #include <algorithm> | |
17 | #include <assert.h> | |
18 | #include <boost/config.hpp> | |
19 | #include <boost/tuple/tuple.hpp> | |
20 | ||
21 | #include <boost/graph/graph_traits.hpp> | |
22 | #include <boost/graph/properties.hpp> | |
23 | #include <boost/pending/container_traits.hpp> | |
24 | #include <boost/graph/depth_first_search.hpp> | |
25 | // iota moved to detail/algorithm.hpp | |
26 | #include <boost/detail/algorithm.hpp> | |
27 | ||
f67539c2 TL |
28 | namespace boost |
29 | { | |
30 | ||
31 | // Provide an undirected graph interface alternative to the | |
32 | // the source() and target() edge functions. | |
33 | template < class UndirectedGraph > | |
34 | inline std::pair< typename graph_traits< UndirectedGraph >::vertex_descriptor, | |
35 | typename graph_traits< UndirectedGraph >::vertex_descriptor > | |
36 | incident(typename graph_traits< UndirectedGraph >::edge_descriptor e, | |
37 | UndirectedGraph& g) | |
38 | { | |
39 | return std::make_pair(source(e, g), target(e, g)); | |
40 | } | |
41 | ||
42 | // Provide an undirected graph interface alternative | |
43 | // to the out_edges() function. | |
44 | template < class Graph > | |
45 | inline std::pair< typename graph_traits< Graph >::out_edge_iterator, | |
46 | typename graph_traits< Graph >::out_edge_iterator > | |
47 | incident_edges(typename graph_traits< Graph >::vertex_descriptor u, Graph& g) | |
48 | { | |
7c673cae | 49 | return out_edges(u, g); |
f67539c2 TL |
50 | } |
51 | ||
52 | template < class Graph > | |
53 | inline typename graph_traits< Graph >::vertex_descriptor opposite( | |
54 | typename graph_traits< Graph >::edge_descriptor e, | |
55 | typename graph_traits< Graph >::vertex_descriptor v, const Graph& g) | |
56 | { | |
57 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; | |
7c673cae | 58 | if (v == source(e, g)) |
f67539c2 | 59 | return target(e, g); |
7c673cae | 60 | else if (v == target(e, g)) |
f67539c2 | 61 | return source(e, g); |
7c673cae | 62 | else |
f67539c2 TL |
63 | return vertex_descriptor(); |
64 | } | |
65 | ||
66 | //=========================================================================== | |
67 | // Some handy predicates | |
68 | ||
69 | template < typename Vertex, typename Graph > struct incident_from_predicate | |
70 | { | |
71 | incident_from_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} | |
72 | template < class Edge > bool operator()(const Edge& e) const | |
73 | { | |
74 | return source(e, m_g) == m_u; | |
7c673cae FG |
75 | } |
76 | Vertex m_u; | |
77 | const Graph& m_g; | |
f67539c2 TL |
78 | }; |
79 | template < typename Vertex, typename Graph > | |
80 | inline incident_from_predicate< Vertex, Graph > incident_from( | |
81 | Vertex u, const Graph& g) | |
82 | { | |
83 | return incident_from_predicate< Vertex, Graph >(u, g); | |
84 | } | |
85 | ||
86 | template < typename Vertex, typename Graph > struct incident_to_predicate | |
87 | { | |
88 | incident_to_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} | |
89 | template < class Edge > bool operator()(const Edge& e) const | |
90 | { | |
91 | return target(e, m_g) == m_u; | |
7c673cae FG |
92 | } |
93 | Vertex m_u; | |
94 | const Graph& m_g; | |
f67539c2 TL |
95 | }; |
96 | template < typename Vertex, typename Graph > | |
97 | inline incident_to_predicate< Vertex, Graph > incident_to( | |
98 | Vertex u, const Graph& g) | |
99 | { | |
100 | return incident_to_predicate< Vertex, Graph >(u, g); | |
101 | } | |
102 | ||
103 | template < typename Vertex, typename Graph > struct incident_on_predicate | |
104 | { | |
105 | incident_on_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} | |
106 | template < class Edge > bool operator()(const Edge& e) const | |
107 | { | |
108 | return source(e, m_g) == m_u || target(e, m_g) == m_u; | |
7c673cae FG |
109 | } |
110 | Vertex m_u; | |
111 | const Graph& m_g; | |
f67539c2 TL |
112 | }; |
113 | template < typename Vertex, typename Graph > | |
114 | inline incident_on_predicate< Vertex, Graph > incident_on( | |
115 | Vertex u, const Graph& g) | |
116 | { | |
117 | return incident_on_predicate< Vertex, Graph >(u, g); | |
118 | } | |
119 | ||
120 | template < typename Vertex, typename Graph > struct connects_predicate | |
121 | { | |
7c673cae | 122 | connects_predicate(Vertex u, Vertex v, const Graph& g) |
f67539c2 TL |
123 | : m_u(u), m_v(v), m_g(g) |
124 | { | |
125 | } | |
126 | template < class Edge > bool operator()(const Edge& e) const | |
127 | { | |
128 | if (is_directed(m_g)) | |
129 | return source(e, m_g) == m_u && target(e, m_g) == m_v; | |
130 | else | |
131 | return (source(e, m_g) == m_u && target(e, m_g) == m_v) | |
132 | || (source(e, m_g) == m_v && target(e, m_g) == m_u); | |
7c673cae FG |
133 | } |
134 | Vertex m_u, m_v; | |
135 | const Graph& m_g; | |
f67539c2 TL |
136 | }; |
137 | template < typename Vertex, typename Graph > | |
138 | inline connects_predicate< Vertex, Graph > connects( | |
139 | Vertex u, Vertex v, const Graph& g) | |
140 | { | |
141 | return connects_predicate< Vertex, Graph >(u, v, g); | |
142 | } | |
143 | ||
144 | // Need to convert all of these printing functions to take an ostream object | |
145 | // -JGS | |
146 | ||
147 | template < class IncidenceGraph, class Name > | |
148 | void print_in_edges( | |
149 | const IncidenceGraph& G, Name name, std::ostream& os = std::cout) | |
150 | { | |
151 | typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; | |
152 | for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) | |
153 | { | |
154 | os << get(name, *ui) << " <-- "; | |
155 | typename graph_traits< IncidenceGraph >::in_edge_iterator ei, ei_end; | |
156 | for (boost::tie(ei, ei_end) = in_edges(*ui, G); ei != ei_end; ++ei) | |
157 | os << get(name, source(*ei, G)) << " "; | |
158 | os << '\n'; | |
7c673cae | 159 | } |
f67539c2 TL |
160 | } |
161 | ||
162 | template < class IncidenceGraph, class Name > | |
163 | void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag, | |
164 | std::ostream& os = std::cout) | |
165 | { | |
166 | typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; | |
167 | for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) | |
168 | { | |
169 | os << get(name, *ui) << " --> "; | |
170 | typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; | |
171 | for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei) | |
172 | os << get(name, target(*ei, G)) << " "; | |
173 | os << '\n'; | |
7c673cae | 174 | } |
f67539c2 TL |
175 | } |
176 | template < class IncidenceGraph, class Name > | |
177 | void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag, | |
178 | std::ostream& os = std::cout) | |
179 | { | |
180 | typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; | |
181 | for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) | |
182 | { | |
183 | os << get(name, *ui) << " <--> "; | |
184 | typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; | |
185 | for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei) | |
186 | os << get(name, target(*ei, G)) << " "; | |
187 | os << '\n'; | |
7c673cae | 188 | } |
f67539c2 TL |
189 | } |
190 | template < class IncidenceGraph, class Name > | |
191 | void print_graph( | |
192 | const IncidenceGraph& G, Name name, std::ostream& os = std::cout) | |
193 | { | |
194 | typedef typename graph_traits< IncidenceGraph >::directed_category Cat; | |
7c673cae | 195 | print_graph_dispatch(G, name, Cat(), os); |
f67539c2 TL |
196 | } |
197 | template < class IncidenceGraph > | |
198 | void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout) | |
199 | { | |
7c673cae | 200 | print_graph(G, get(vertex_index, G), os); |
f67539c2 | 201 | } |
7c673cae | 202 | |
f67539c2 TL |
203 | template < class EdgeListGraph, class Name > |
204 | void print_edges( | |
205 | const EdgeListGraph& G, Name name, std::ostream& os = std::cout) | |
206 | { | |
207 | typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end; | |
7c673cae | 208 | for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) |
f67539c2 TL |
209 | os << "(" << get(name, source(*ei, G)) << "," |
210 | << get(name, target(*ei, G)) << ") "; | |
7c673cae | 211 | os << '\n'; |
f67539c2 | 212 | } |
7c673cae | 213 | |
f67539c2 TL |
214 | template < class EdgeListGraph, class VertexName, class EdgeName > |
215 | void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename, | |
216 | std::ostream& os = std::cout) | |
217 | { | |
218 | typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end; | |
7c673cae | 219 | for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) |
f67539c2 TL |
220 | os << get(ename, *ei) << "(" << get(vname, source(*ei, G)) << "," |
221 | << get(vname, target(*ei, G)) << ") "; | |
7c673cae | 222 | os << '\n'; |
f67539c2 TL |
223 | } |
224 | ||
225 | template < class VertexListGraph, class Name > | |
226 | void print_vertices( | |
227 | const VertexListGraph& G, Name name, std::ostream& os = std::cout) | |
228 | { | |
229 | typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end; | |
230 | for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) | |
231 | os << get(name, *vi) << " "; | |
7c673cae | 232 | os << '\n'; |
f67539c2 | 233 | } |
7c673cae | 234 | |
f67539c2 TL |
235 | template < class Graph, class Vertex > |
236 | bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag) | |
237 | { | |
238 | typename graph_traits< Graph >::adjacency_iterator vi, viend, adj_found; | |
7c673cae FG |
239 | boost::tie(vi, viend) = adjacent_vertices(a, g); |
240 | adj_found = std::find(vi, viend, b); | |
241 | if (adj_found == viend) | |
f67539c2 | 242 | return false; |
7c673cae | 243 | |
f67539c2 | 244 | typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found; |
7c673cae FG |
245 | boost::tie(oi, oiend) = out_edges(a, g); |
246 | out_found = std::find_if(oi, oiend, incident_to(b, g)); | |
247 | if (out_found == oiend) | |
f67539c2 | 248 | return false; |
7c673cae | 249 | |
f67539c2 | 250 | typename graph_traits< Graph >::in_edge_iterator ii, iiend, in_found; |
7c673cae FG |
251 | boost::tie(ii, iiend) = in_edges(b, g); |
252 | in_found = std::find_if(ii, iiend, incident_from(a, g)); | |
253 | if (in_found == iiend) | |
f67539c2 | 254 | return false; |
7c673cae FG |
255 | |
256 | return true; | |
f67539c2 TL |
257 | } |
258 | template < class Graph, class Vertex > | |
259 | bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag) | |
260 | { | |
261 | typename graph_traits< Graph >::adjacency_iterator vi, viend, found; | |
7c673cae FG |
262 | boost::tie(vi, viend) = adjacent_vertices(a, g); |
263 | found = std::find(vi, viend, b); | |
f67539c2 TL |
264 | if (found == viend) |
265 | return false; | |
7c673cae | 266 | |
f67539c2 | 267 | typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found; |
7c673cae FG |
268 | boost::tie(oi, oiend) = out_edges(a, g); |
269 | ||
270 | out_found = std::find_if(oi, oiend, incident_to(b, g)); | |
271 | if (out_found == oiend) | |
f67539c2 | 272 | return false; |
7c673cae | 273 | return true; |
f67539c2 TL |
274 | } |
275 | template < class Graph, class Vertex > | |
276 | bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag) | |
277 | { | |
7c673cae | 278 | return is_adj_dispatch(g, a, b, directed_tag()); |
f67539c2 | 279 | } |
7c673cae | 280 | |
f67539c2 TL |
281 | template < class Graph, class Vertex > |
282 | bool is_adjacent(Graph& g, Vertex a, Vertex b) | |
283 | { | |
284 | typedef typename graph_traits< Graph >::directed_category Cat; | |
7c673cae | 285 | return is_adj_dispatch(g, a, b, Cat()); |
f67539c2 | 286 | } |
7c673cae | 287 | |
f67539c2 TL |
288 | template < class Graph, class Edge > bool in_edge_set(Graph& g, Edge e) |
289 | { | |
7c673cae FG |
290 | typename Graph::edge_iterator ei, ei_end, found; |
291 | boost::tie(ei, ei_end) = edges(g); | |
292 | found = std::find(ei, ei_end, e); | |
293 | return found != ei_end; | |
f67539c2 | 294 | } |
7c673cae | 295 | |
f67539c2 TL |
296 | template < class Graph, class Vertex > bool in_vertex_set(Graph& g, Vertex v) |
297 | { | |
7c673cae FG |
298 | typename Graph::vertex_iterator vi, vi_end, found; |
299 | boost::tie(vi, vi_end) = vertices(g); | |
300 | found = std::find(vi, vi_end, v); | |
301 | return found != vi_end; | |
f67539c2 | 302 | } |
7c673cae | 303 | |
f67539c2 TL |
304 | template < class Graph, class Vertex > |
305 | bool in_edge_set(Graph& g, Vertex u, Vertex v) | |
306 | { | |
7c673cae | 307 | typename Graph::edge_iterator ei, ei_end; |
f67539c2 TL |
308 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) |
309 | if (source(*ei, g) == u && target(*ei, g) == v) | |
310 | return true; | |
7c673cae | 311 | return false; |
f67539c2 TL |
312 | } |
313 | ||
314 | // is x a descendant of y? | |
315 | template < typename ParentMap > | |
316 | inline bool is_descendant(typename property_traits< ParentMap >::value_type x, | |
317 | typename property_traits< ParentMap >::value_type y, ParentMap parent) | |
318 | { | |
7c673cae | 319 | if (get(parent, x) == x) // x is the root of the tree |
f67539c2 | 320 | return false; |
7c673cae | 321 | else if (get(parent, x) == y) |
f67539c2 | 322 | return true; |
7c673cae | 323 | else |
f67539c2 TL |
324 | return is_descendant(get(parent, x), y, parent); |
325 | } | |
326 | ||
327 | // is y reachable from x? | |
328 | template < typename IncidenceGraph, typename VertexColorMap > | |
329 | inline bool is_reachable( | |
330 | typename graph_traits< IncidenceGraph >::vertex_descriptor x, | |
331 | typename graph_traits< IncidenceGraph >::vertex_descriptor y, | |
332 | const IncidenceGraph& g, | |
333 | VertexColorMap color) // should start out white for every vertex | |
334 | { | |
335 | typedef typename property_traits< VertexColorMap >::value_type ColorValue; | |
7c673cae FG |
336 | dfs_visitor<> vis; |
337 | depth_first_visit(g, x, vis, color); | |
f67539c2 TL |
338 | return get(color, y) != color_traits< ColorValue >::white(); |
339 | } | |
340 | ||
341 | // Is the undirected graph connected? | |
342 | // Is the directed graph strongly connected? | |
343 | template < typename VertexListGraph, typename VertexColorMap > | |
344 | inline bool is_connected(const VertexListGraph& g, VertexColorMap color) | |
345 | { | |
346 | typedef typename property_traits< VertexColorMap >::value_type ColorValue; | |
347 | typedef color_traits< ColorValue > Color; | |
348 | typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end, vi, | |
349 | vi_end, ci, ci_end; | |
7c673cae | 350 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
f67539c2 TL |
351 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
352 | if (*ui != *vi) | |
353 | { | |
354 | for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci) | |
355 | put(color, *ci, Color::white()); | |
356 | if (!is_reachable(*ui, *vi, g, color)) | |
357 | return false; | |
358 | } | |
7c673cae | 359 | return true; |
f67539c2 | 360 | } |
7c673cae | 361 | |
f67539c2 TL |
362 | template < typename Graph > |
363 | bool is_self_loop( | |
364 | typename graph_traits< Graph >::edge_descriptor e, const Graph& g) | |
365 | { | |
7c673cae | 366 | return source(e, g) == target(e, g); |
f67539c2 TL |
367 | } |
368 | ||
369 | template < class T1, class T2 > | |
370 | std::pair< T1, T2 > make_list(const T1& t1, const T2& t2) | |
371 | { | |
372 | return std::make_pair(t1, t2); | |
373 | } | |
374 | ||
375 | template < class T1, class T2, class T3 > | |
376 | std::pair< T1, std::pair< T2, T3 > > make_list( | |
377 | const T1& t1, const T2& t2, const T3& t3) | |
378 | { | |
379 | return std::make_pair(t1, std::make_pair(t2, t3)); | |
380 | } | |
381 | ||
382 | template < class T1, class T2, class T3, class T4 > | |
383 | std::pair< T1, std::pair< T2, std::pair< T3, T4 > > > make_list( | |
384 | const T1& t1, const T2& t2, const T3& t3, const T4& t4) | |
385 | { | |
386 | return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); | |
387 | } | |
388 | ||
389 | template < class T1, class T2, class T3, class T4, class T5 > | |
390 | std::pair< T1, std::pair< T2, std::pair< T3, std::pair< T4, T5 > > > > | |
391 | make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5) | |
392 | { | |
393 | return std::make_pair( | |
394 | t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); | |
395 | } | |
396 | ||
397 | namespace graph | |
398 | { | |
399 | ||
400 | // Functor for remove_parallel_edges: edge property of the removed edge is | |
401 | // added to the remaining | |
402 | template < typename EdgeProperty > struct add_removed_edge_property | |
7c673cae | 403 | { |
f67539c2 TL |
404 | add_removed_edge_property(EdgeProperty ep) : ep(ep) {} |
405 | ||
406 | template < typename Edge > void operator()(Edge stay, Edge away) | |
407 | { | |
408 | put(ep, stay, get(ep, stay) + get(ep, away)); | |
409 | } | |
410 | EdgeProperty ep; | |
7c673cae FG |
411 | }; |
412 | ||
413 | // Same as above: edge property is capacity here | |
f67539c2 | 414 | template < typename Graph > |
7c673cae | 415 | struct add_removed_edge_capacity |
f67539c2 TL |
416 | : add_removed_edge_property< |
417 | typename property_map< Graph, edge_capacity_t >::type > | |
418 | { | |
419 | typedef add_removed_edge_property< | |
420 | typename property_map< Graph, edge_capacity_t >::type > | |
421 | base; | |
422 | add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {} | |
423 | }; | |
424 | ||
425 | template < typename Graph > bool has_no_vertices(const Graph& g) | |
7c673cae | 426 | { |
f67539c2 TL |
427 | typedef typename boost::graph_traits< Graph >::vertex_iterator vi; |
428 | std::pair< vi, vi > p = vertices(g); | |
429 | return (p.first == p.second); | |
7c673cae FG |
430 | } |
431 | ||
f67539c2 TL |
432 | template < typename Graph > bool has_no_edges(const Graph& g) |
433 | { | |
434 | typedef typename boost::graph_traits< Graph >::edge_iterator ei; | |
435 | std::pair< ei, ei > p = edges(g); | |
436 | return (p.first == p.second); | |
7c673cae FG |
437 | } |
438 | ||
f67539c2 TL |
439 | template < typename Graph > |
440 | bool has_no_out_edges( | |
441 | const typename boost::graph_traits< Graph >::vertex_descriptor& v, | |
442 | const Graph& g) | |
443 | { | |
444 | typedef typename boost::graph_traits< Graph >::out_edge_iterator ei; | |
445 | std::pair< ei, ei > p = out_edges(v, g); | |
446 | return (p.first == p.second); | |
7c673cae FG |
447 | } |
448 | ||
f67539c2 | 449 | } // namespace graph |
7c673cae | 450 | |
f67539c2 | 451 | #include <boost/graph/iteration_macros.hpp> |
7c673cae | 452 | |
f67539c2 TL |
453 | template < class PropertyIn, class PropertyOut, class Graph > |
454 | void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g) | |
455 | { | |
7c673cae | 456 | BGL_FORALL_VERTICES_T(u, g, Graph) |
f67539c2 TL |
457 | put(p_out, u, get(p_in, g)); |
458 | } | |
7c673cae | 459 | |
f67539c2 TL |
460 | template < class PropertyIn, class PropertyOut, class Graph > |
461 | void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g) | |
462 | { | |
7c673cae | 463 | BGL_FORALL_EDGES_T(e, g, Graph) |
f67539c2 TL |
464 | put(p_out, e, get(p_in, g)); |
465 | } | |
466 | ||
467 | // Return true if property_map1 and property_map2 differ | |
468 | // for any of the vertices in graph. | |
469 | template < typename PropertyMapFirst, typename PropertyMapSecond, | |
470 | typename Graph > | |
471 | bool are_property_maps_different(const PropertyMapFirst property_map1, | |
472 | const PropertyMapSecond property_map2, const Graph& graph) | |
473 | { | |
474 | ||
475 | BGL_FORALL_VERTICES_T(vertex, graph, Graph) | |
476 | { | |
477 | if (get(property_map1, vertex) != get(property_map2, vertex)) | |
478 | { | |
479 | ||
480 | return (true); | |
481 | } | |
7c673cae FG |
482 | } |
483 | ||
484 | return (false); | |
f67539c2 | 485 | } |
7c673cae FG |
486 | |
487 | } /* namespace boost */ | |
488 | ||
489 | #endif /* BOOST_GRAPH_UTILITY_HPP*/ |