boost/graph/graph_utility.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_UTILITY_HPP
0012 #define BOOST_GRAPH_UTILITY_HPP
0013
0014 #include <stdlib.h>
0015 #include <iostream>
0016 #include <algorithm>
0017 #include <assert.h>
0018 #include <boost/config.hpp>
0019 #include <boost/tuple/tuple.hpp>
0020
0021 #include <boost/graph/graph_traits.hpp>
0022 #include <boost/graph/properties.hpp>
0023 #include <boost/pending/container_traits.hpp>
0024 #include <boost/graph/depth_first_search.hpp>
0025 // iota moved to detail/algorithm.hpp
0026 #include <boost/detail/algorithm.hpp>
0027
0028 namespace boost
0029 {
0030
0031 // Provide an undirected graph interface alternative to the
0032 // the source() and target() edge functions.
0033 template < class UndirectedGraph >
0034 inline std::pair< typename graph_traits< UndirectedGraph >::vertex_descriptor,
0035     typename graph_traits< UndirectedGraph >::vertex_descriptor >
0036 incident(typename graph_traits< UndirectedGraph >::edge_descriptor e,
0037     UndirectedGraph& g)
0038 {
0039     return std::make_pair(source(e, g), target(e, g));
0040 }
0041
0042 // Provide an undirected graph interface alternative
0043 // to the out_edges() function.
0044 template < class Graph >
0045 inline std::pair< typename graph_traits< Graph >::out_edge_iterator,
0046     typename graph_traits< Graph >::out_edge_iterator >
0047 incident_edges(typename graph_traits< Graph >::vertex_descriptor u, Graph& g)
0048 {
0049     return out_edges(u, g);
0050 }
0051
0052 template < class Graph >
0053 inline typename graph_traits< Graph >::vertex_descriptor opposite(
0054     typename graph_traits< Graph >::edge_descriptor e,
0055     typename graph_traits< Graph >::vertex_descriptor v, const Graph& g)
0056 {
0057     typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
0058     if (v == source(e, g))
0059         return target(e, g);
0060     else if (v == target(e, g))
0061         return source(e, g);
0062     else
0063         return vertex_descriptor();
0064 }
0065
0066 //===========================================================================
0067 // Some handy predicates
0068
0069 template < typename Vertex, typename Graph > struct incident_from_predicate
0070 {
0071     incident_from_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0072     template < class Edge > bool operator()(const Edge& e) const
0073     {
0074         return source(e, m_g) == m_u;
0075     }
0076     Vertex m_u;
0077     const Graph& m_g;
0078 };
0079 template < typename Vertex, typename Graph >
0080 inline incident_from_predicate< Vertex, Graph > incident_from(
0081     Vertex u, const Graph& g)
0082 {
0083     return incident_from_predicate< Vertex, Graph >(u, g);
0084 }
0085
0086 template < typename Vertex, typename Graph > struct incident_to_predicate
0087 {
0088     incident_to_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0089     template < class Edge > bool operator()(const Edge& e) const
0090     {
0091         return target(e, m_g) == m_u;
0092     }
0093     Vertex m_u;
0094     const Graph& m_g;
0095 };
0096 template < typename Vertex, typename Graph >
0097 inline incident_to_predicate< Vertex, Graph > incident_to(
0098     Vertex u, const Graph& g)
0099 {
0100     return incident_to_predicate< Vertex, Graph >(u, g);
0101 }
0102
0103 template < typename Vertex, typename Graph > struct incident_on_predicate
0104 {
0105     incident_on_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {}
0106     template < class Edge > bool operator()(const Edge& e) const
0107     {
0108         return source(e, m_g) == m_u || target(e, m_g) == m_u;
0109     }
0110     Vertex m_u;
0111     const Graph& m_g;
0112 };
0113 template < typename Vertex, typename Graph >
0114 inline incident_on_predicate< Vertex, Graph > incident_on(
0115     Vertex u, const Graph& g)
0116 {
0117     return incident_on_predicate< Vertex, Graph >(u, g);
0118 }
0119
0120 template < typename Vertex, typename Graph > struct connects_predicate
0121 {
0122     connects_predicate(Vertex u, Vertex v, const Graph& g)
0123     : m_u(u), m_v(v), m_g(g)
0124     {
0125     }
0126     template < class Edge > bool operator()(const Edge& e) const
0127     {
0128         if (is_directed(m_g))
0129             return source(e, m_g) == m_u && target(e, m_g) == m_v;
0130         else
0131             return (source(e, m_g) == m_u && target(e, m_g) == m_v)
0132                 || (source(e, m_g) == m_v && target(e, m_g) == m_u);
0133     }
0134     Vertex m_u, m_v;
0135     const Graph& m_g;
0136 };
0137 template < typename Vertex, typename Graph >
0138 inline connects_predicate< Vertex, Graph > connects(
0139     Vertex u, Vertex v, const Graph& g)
0140 {
0141     return connects_predicate< Vertex, Graph >(u, v, g);
0142 }
0143
0144 // Need to convert all of these printing functions to take an ostream object
0145 // -JGS
0146
0147 template < class IncidenceGraph, class Name >
0148 void print_in_edges(
0149     const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
0150 {
0151     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0152     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0153     {
0154         os << get(name, *ui) << " <-- ";
0155         typename graph_traits< IncidenceGraph >::in_edge_iterator ei, ei_end;
0156         for (boost::tie(ei, ei_end) = in_edges(*ui, G); ei != ei_end; ++ei)
0157             os << get(name, source(*ei, G)) << " ";
0158         os << '\n';
0159     }
0160 }
0161
0162 template < class IncidenceGraph, class Name >
0163 void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag,
0164     std::ostream& os = std::cout)
0165 {
0166     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0167     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0168     {
0169         os << get(name, *ui) << " --> ";
0170         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0171         for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
0172             os << get(name, target(*ei, G)) << " ";
0173         os << '\n';
0174     }
0175 }
0176 template < class IncidenceGraph, class Name >
0177 void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag,
0178     std::ostream& os = std::cout)
0179 {
0180     typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end;
0181     for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui)
0182     {
0183         os << get(name, *ui) << " <--> ";
0184         typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end;
0185         for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei)
0186             os << get(name, target(*ei, G)) << " ";
0187         os << '\n';
0188     }
0189 }
0190 template < class IncidenceGraph, class Name >
0191 void print_graph(
0192     const IncidenceGraph& G, Name name, std::ostream& os = std::cout)
0193 {
0194     typedef typename graph_traits< IncidenceGraph >::directed_category Cat;
0195     print_graph_dispatch(G, name, Cat(), os);
0196 }
0197 template < class IncidenceGraph >
0198 void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout)
0199 {
0200     print_graph(G, get(vertex_index, G), os);
0201 }
0202
0203 template < class EdgeListGraph, class Name >
0204 void print_edges(
0205     const EdgeListGraph& G, Name name, std::ostream& os = std::cout)
0206 {
0207     typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
0208     for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
0209         os << "(" << get(name, source(*ei, G)) << ","
0210            << get(name, target(*ei, G)) << ") ";
0211     os << '\n';
0212 }
0213
0214 template < class EdgeListGraph, class VertexName, class EdgeName >
0215 void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename,
0216     std::ostream& os = std::cout)
0217 {
0218     typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end;
0219     for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
0220         os << get(ename, *ei) << "(" << get(vname, source(*ei, G)) << ","
0221            << get(vname, target(*ei, G)) << ") ";
0222     os << '\n';
0223 }
0224
0225 template < class VertexListGraph, class Name >
0226 void print_vertices(
0227     const VertexListGraph& G, Name name, std::ostream& os = std::cout)
0228 {
0229     typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end;
0230     for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
0231         os << get(name, *vi) << " ";
0232     os << '\n';
0233 }
0234
0235 template < class Graph, class Vertex >
0236 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
0237 {
0238     typename graph_traits< Graph >::adjacency_iterator vi, viend, adj_found;
0239     boost::tie(vi, viend) = adjacent_vertices(a, g);
0240     adj_found = std::find(vi, viend, b);
0241     if (adj_found == viend)
0242         return false;
0243
0244     typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
0245     boost::tie(oi, oiend) = out_edges(a, g);
0246     out_found = std::find_if(oi, oiend, incident_to(b, g));
0247     if (out_found == oiend)
0248         return false;
0249
0250     typename graph_traits< Graph >::in_edge_iterator ii, iiend, in_found;
0251     boost::tie(ii, iiend) = in_edges(b, g);
0252     in_found = std::find_if(ii, iiend, incident_from(a, g));
0253     if (in_found == iiend)
0254         return false;
0255
0256     return true;
0257 }
0258 template < class Graph, class Vertex >
0259 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
0260 {
0261     typename graph_traits< Graph >::adjacency_iterator vi, viend, found;
0262     boost::tie(vi, viend) = adjacent_vertices(a, g);
0263     found = std::find(vi, viend, b);
0264     if (found == viend)
0265         return false;
0266
0267     typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found;
0268     boost::tie(oi, oiend) = out_edges(a, g);
0269
0270     out_found = std::find_if(oi, oiend, incident_to(b, g));
0271     if (out_found == oiend)
0272         return false;
0273     return true;
0274 }
0275 template < class Graph, class Vertex >
0276 bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
0277 {
0278     return is_adj_dispatch(g, a, b, directed_tag());
0279 }
0280
0281 template < class Graph, class Vertex >
0282 bool is_adjacent(Graph& g, Vertex a, Vertex b)
0283 {
0284     typedef typename graph_traits< Graph >::directed_category Cat;
0285     return is_adj_dispatch(g, a, b, Cat());
0286 }
0287
0288 template < class Graph, class Edge > bool in_edge_set(Graph& g, Edge e)
0289 {
0290     typename Graph::edge_iterator ei, ei_end, found;
0291     boost::tie(ei, ei_end) = edges(g);
0292     found = std::find(ei, ei_end, e);
0293     return found != ei_end;
0294 }
0295
0296 template < class Graph, class Vertex > bool in_vertex_set(Graph& g, Vertex v)
0297 {
0298     typename Graph::vertex_iterator vi, vi_end, found;
0299     boost::tie(vi, vi_end) = vertices(g);
0300     found = std::find(vi, vi_end, v);
0301     return found != vi_end;
0302 }
0303
0304 template < class Graph, class Vertex >
0305 bool in_edge_set(Graph& g, Vertex u, Vertex v)
0306 {
0307     typename Graph::edge_iterator ei, ei_end;
0308     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0309         if (source(*ei, g) == u && target(*ei, g) == v)
0310             return true;
0311     return false;
0312 }
0313
0314 // is x a descendant of y?
0315 template < typename ParentMap >
0316 inline bool is_descendant(typename property_traits< ParentMap >::value_type x,
0317     typename property_traits< ParentMap >::value_type y, ParentMap parent)
0318 {
0319     if (get(parent, x) == x) // x is the root of the tree
0320         return false;
0321     else if (get(parent, x) == y)
0322         return true;
0323     else
0324         return is_descendant(get(parent, x), y, parent);
0325 }
0326
0327 // is y reachable from x?
0328 template < typename IncidenceGraph, typename VertexColorMap >
0329 inline bool is_reachable(
0330     typename graph_traits< IncidenceGraph >::vertex_descriptor x,
0331     typename graph_traits< IncidenceGraph >::vertex_descriptor y,
0332     const IncidenceGraph& g,
0333     VertexColorMap color) // should start out white for every vertex
0334 {
0335     typedef typename property_traits< VertexColorMap >::value_type ColorValue;
0336     dfs_visitor<> vis;
0337     depth_first_visit(g, x, vis, color);
0338     return get(color, y) != color_traits< ColorValue >::white();
0339 }
0340
0341 // Is the undirected graph connected?
0342 // Is the directed graph strongly connected?
0343 template < typename VertexListGraph, typename VertexColorMap >
0344 inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
0345 {
0346     typedef typename property_traits< VertexColorMap >::value_type ColorValue;
0347     typedef color_traits< ColorValue > Color;
0348     typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end, vi,
0349         vi_end, ci, ci_end;
0350     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
0351         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
0352             if (*ui != *vi)
0353             {
0354                 for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci)
0355                     put(color, *ci, Color::white());
0356                 if (!is_reachable(*ui, *vi, g, color))
0357                     return false;
0358             }
0359     return true;
0360 }
0361
0362 template < typename Graph >
0363 bool is_self_loop(
0364     typename graph_traits< Graph >::edge_descriptor e, const Graph& g)
0365 {
0366     return source(e, g) == target(e, g);
0367 }
0368
0369 template < class T1, class T2 >
0370 std::pair< T1, T2 > make_list(const T1& t1, const T2& t2)
0371 {
0372     return std::make_pair(t1, t2);
0373 }
0374
0375 template < class T1, class T2, class T3 >
0376 std::pair< T1, std::pair< T2, T3 > > make_list(
0377     const T1& t1, const T2& t2, const T3& t3)
0378 {
0379     return std::make_pair(t1, std::make_pair(t2, t3));
0380 }
0381
0382 template < class T1, class T2, class T3, class T4 >
0383 std::pair< T1, std::pair< T2, std::pair< T3, T4 > > > make_list(
0384     const T1& t1, const T2& t2, const T3& t3, const T4& t4)
0385 {
0386     return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4)));
0387 }
0388
0389 template < class T1, class T2, class T3, class T4, class T5 >
0390 std::pair< T1, std::pair< T2, std::pair< T3, std::pair< T4, T5 > > > >
0391 make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
0392 {
0393     return std::make_pair(
0394         t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5))));
0395 }
0396
0397 namespace graph
0398 {
0399
0400     // Functor for remove_parallel_edges: edge property of the removed edge is
0401     // added to the remaining
0402     template < typename EdgeProperty > struct add_removed_edge_property
0403     {
0404         add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
0405
0406         template < typename Edge > void operator()(Edge stay, Edge away)
0407         {
0408             put(ep, stay, get(ep, stay) + get(ep, away));
0409         }
0410         EdgeProperty ep;
0411     };
0412
0413     // Same as above: edge property is capacity here
0414     template < typename Graph >
0415     struct add_removed_edge_capacity
0416     : add_removed_edge_property<
0417           typename property_map< Graph, edge_capacity_t >::type >
0418     {
0419         typedef add_removed_edge_property<
0420             typename property_map< Graph, edge_capacity_t >::type >
0421             base;
0422         add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
0423     };
0424
0425     template < typename Graph > bool has_no_vertices(const Graph& g)
0426     {
0427         typedef typename boost::graph_traits< Graph >::vertex_iterator vi;
0428         std::pair< vi, vi > p = vertices(g);
0429         return (p.first == p.second);
0430     }
0431
0432     template < typename Graph > bool has_no_edges(const Graph& g)
0433     {
0434         typedef typename boost::graph_traits< Graph >::edge_iterator ei;
0435         std::pair< ei, ei > p = edges(g);
0436         return (p.first == p.second);
0437     }
0438
0439     template < typename Graph >
0440     bool has_no_out_edges(
0441         const typename boost::graph_traits< Graph >::vertex_descriptor& v,
0442         const Graph& g)
0443     {
0444         typedef typename boost::graph_traits< Graph >::out_edge_iterator ei;
0445         std::pair< ei, ei > p = out_edges(v, g);
0446         return (p.first == p.second);
0447     }
0448
0449 } // namespace graph
0450
0451 #include <boost/graph/iteration_macros.hpp>
0452
0453 template < class PropertyIn, class PropertyOut, class Graph >
0454 void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0455 {
0456     BGL_FORALL_VERTICES_T(u, g, Graph)
0457     put(p_out, u, get(p_in, g));
0458 }
0459
0460 template < class PropertyIn, class PropertyOut, class Graph >
0461 void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g)
0462 {
0463     BGL_FORALL_EDGES_T(e, g, Graph)
0464     put(p_out, e, get(p_in, g));
0465 }
0466
0467 // Return true if property_map1 and property_map2 differ
0468 // for any of the vertices in graph.
0469 template < typename PropertyMapFirst, typename PropertyMapSecond,
0470     typename Graph >
0471 bool are_property_maps_different(const PropertyMapFirst property_map1,
0472     const PropertyMapSecond property_map2, const Graph& graph)
0473 {
0474
0475     BGL_FORALL_VERTICES_T(vertex, graph, Graph)
0476     {
0477         if (get(property_map1, vertex) != get(property_map2, vertex))
0478         {
0479
0480             return (true);
0481         }
0482     }
0483
0484     return (false);
0485 }
0486
0487 } /* namespace boost */
0488
0489 #endif /* BOOST_GRAPH_UTILITY_HPP*/