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
36namespace 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

source code of boost/boost/graph/graph_utility.hpp