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