2 //=======================================================================
3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
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 //=======================================================================
11 #ifndef BOOST_GRAPH_UTILITY_HPP
12 #define BOOST_GRAPH_UTILITY_HPP
18 #include <boost/config.hpp>
19 #include <boost/tuple/tuple.hpp>
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>
30 // Provide an undirected graph interface alternative to the
31 // the source() and target() edge functions.
32 template <class UndirectedGraph>
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,
39 return std::make_pair(source(e,g), target(e,g));
42 // Provide an undirected graph interface alternative
43 // to the out_edges() function.
44 template <class Graph>
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,
51 return out_edges(u, g);
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,
60 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
61 if (v == source(e, g))
63 else if (v == target(e, g))
66 return vertex_descriptor();
69 //===========================================================================
70 // Some handy predicates
72 template <typename Vertex, typename Graph>
73 struct incident_from_predicate {
74 incident_from_predicate(Vertex u, const Graph& g)
77 bool operator()(const Edge& e) const {
78 return source(e, m_g) == m_u;
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);
89 template <typename Vertex, typename Graph>
90 struct incident_to_predicate {
91 incident_to_predicate(Vertex u, const Graph& g)
94 bool operator()(const Edge& e) const {
95 return target(e, m_g) == m_u;
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);
106 template <typename Vertex, typename Graph>
107 struct incident_on_predicate {
108 incident_on_predicate(Vertex u, const Graph& 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;
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);
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;
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);
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);
145 // Need to convert all of these printing functions to take an ostream object
148 template <class IncidenceGraph, class Name>
149 void print_in_edges(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
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)) << " ";
162 template <class IncidenceGraph, class Name>
163 void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag, std::ostream& os = std::cout)
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)) << " ";
175 template <class IncidenceGraph, class Name>
176 void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag, std::ostream& os = std::cout)
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)) << " ";
188 template <class IncidenceGraph, class Name>
189 void print_graph(const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
191 typedef typename graph_traits<IncidenceGraph>
192 ::directed_category Cat;
193 print_graph_dispatch(G, name, Cat(), os);
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);
200 template <class EdgeListGraph, class Name>
201 void print_edges(const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
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)) << ") ";
210 template <class EdgeListGraph, class VertexName, class EdgeName>
211 void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename, std::ostream& os = std::cout)
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)) << ") ";
220 template <class VertexListGraph, class Name>
221 void print_vertices(const VertexListGraph& G, Name name, std::ostream& os = std::cout)
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) << " ";
229 template <class Graph, class Vertex>
230 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
232 typename graph_traits<Graph>::adjacency_iterator vi, viend,
234 boost::tie(vi, viend) = adjacent_vertices(a, g);
235 adj_found = std::find(vi, viend, b);
236 if (adj_found == viend)
239 typename graph_traits<Graph>::out_edge_iterator oi, oiend,
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)
246 typename graph_traits<Graph>::in_edge_iterator ii, iiend,
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)
255 template <class Graph, class Vertex>
256 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
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 )
264 typename graph_traits<Graph>::out_edge_iterator oi, oiend,
266 boost::tie(oi, oiend) = out_edges(a, g);
268 out_found = std::find_if(oi, oiend, incident_to(b, g));
269 if (out_found == oiend)
273 template <class Graph, class Vertex>
274 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
276 return is_adj_dispatch(g, a, b, directed_tag());
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());
285 template <class Graph, class Edge>
286 bool in_edge_set(Graph& g, Edge e)
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;
294 template <class Graph, class Vertex>
295 bool in_vertex_set(Graph& g, Vertex v)
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;
303 template <class Graph, class Vertex>
304 bool in_edge_set(Graph& g, Vertex u, Vertex v)
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)
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,
320 if (get(parent, x) == x) // x is the root of the tree
322 else if (get(parent, x) == y)
325 return is_descendant(get(parent, x), y, parent);
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
336 typedef typename property_traits<VertexColorMap>::value_type ColorValue;
338 depth_first_visit(g, x, vis, color);
339 return get(color, y) != color_traits<ColorValue>::white();
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)
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)
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))
362 template <typename Graph>
364 (typename graph_traits<Graph>::edge_descriptor e,
367 return source(e, g) == target(e, g);
371 template <class T1, class T2>
373 make_list(const T1& t1, const T2& t2)
374 { return std::make_pair(t1, t2); }
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)); }
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))); }
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)))); }
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
397 add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
399 template <typename Edge>
400 void operator() (Edge stay, Edge away)
402 put(ep, stay, get(ep, stay) + get(ep, away));
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>
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)) {}
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);
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);
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);
439 #include <boost/graph/iteration_macros.hpp>
441 template <class PropertyIn, class PropertyOut, class Graph>
442 void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
444 BGL_FORALL_VERTICES_T(u, g, Graph)
445 put(p_out, u, get(p_in, g));
448 template <class PropertyIn, class PropertyOut, class Graph>
449 void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
451 BGL_FORALL_EDGES_T(e, g, Graph)
452 put(p_out, e, get(p_in, g));
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,
460 bool are_property_maps_different
461 (const PropertyMapFirst property_map1,
462 const PropertyMapSecond property_map2,
463 const Graph& graph) {
465 BGL_FORALL_VERTICES_T(vertex, graph, Graph) {
466 if (get(property_map1, vertex) !=
467 get(property_map2, vertex)) {
476 } /* namespace boost */
478 #endif /* BOOST_GRAPH_UTILITY_HPP*/