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