boost/graph/graph_utility.hpp
// //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // #ifndef BOOST_GRAPH_UTILITY_HPP #define BOOST_GRAPH_UTILITY_HPP #include <stdlib.h> #include <iostream> #include <algorithm> #include <assert.h> #include <boost/config.hpp> #include <boost/tuple/tuple.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/properties.hpp> #include <boost/pending/container_traits.hpp> #include <boost/graph/depth_first_search.hpp> // iota moved to detail/algorithm.hpp #include <boost/detail/algorithm.hpp> namespace boost { // Provide an undirected graph interface alternative to the // the source() and target() edge functions. template < class UndirectedGraph > inline std::pair< typename graph_traits< UndirectedGraph >::vertex_descriptor, typename graph_traits< UndirectedGraph >::vertex_descriptor > incident(typename graph_traits< UndirectedGraph >::edge_descriptor e, UndirectedGraph& g) { return std::make_pair(source(e, g), target(e, g)); } // Provide an undirected graph interface alternative // to the out_edges() function. template < class Graph > inline std::pair< typename graph_traits< Graph >::out_edge_iterator, typename graph_traits< Graph >::out_edge_iterator > incident_edges(typename graph_traits< Graph >::vertex_descriptor u, Graph& g) { return out_edges(u, g); } template < class Graph > inline typename graph_traits< Graph >::vertex_descriptor opposite( typename graph_traits< Graph >::edge_descriptor e, typename graph_traits< Graph >::vertex_descriptor v, const Graph& g) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; if (v == source(e, g)) return target(e, g); else if (v == target(e, g)) return source(e, g); else return vertex_descriptor(); } //=========================================================================== // Some handy predicates template < typename Vertex, typename Graph > struct incident_from_predicate { incident_from_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} template < class Edge > bool operator()(const Edge& e) const { return source(e, m_g) == m_u; } Vertex m_u; const Graph& m_g; }; template < typename Vertex, typename Graph > inline incident_from_predicate< Vertex, Graph > incident_from( Vertex u, const Graph& g) { return incident_from_predicate< Vertex, Graph >(u, g); } template < typename Vertex, typename Graph > struct incident_to_predicate { incident_to_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} template < class Edge > bool operator()(const Edge& e) const { return target(e, m_g) == m_u; } Vertex m_u; const Graph& m_g; }; template < typename Vertex, typename Graph > inline incident_to_predicate< Vertex, Graph > incident_to( Vertex u, const Graph& g) { return incident_to_predicate< Vertex, Graph >(u, g); } template < typename Vertex, typename Graph > struct incident_on_predicate { incident_on_predicate(Vertex u, const Graph& g) : m_u(u), m_g(g) {} template < class Edge > bool operator()(const Edge& e) const { return source(e, m_g) == m_u || target(e, m_g) == m_u; } Vertex m_u; const Graph& m_g; }; template < typename Vertex, typename Graph > inline incident_on_predicate< Vertex, Graph > incident_on( Vertex u, const Graph& g) { return incident_on_predicate< Vertex, Graph >(u, g); } template < typename Vertex, typename Graph > struct connects_predicate { connects_predicate(Vertex u, Vertex v, const Graph& g) : m_u(u), m_v(v), m_g(g) { } template < class Edge > bool operator()(const Edge& e) const { if (is_directed(m_g)) return source(e, m_g) == m_u && target(e, m_g) == m_v; else return (source(e, m_g) == m_u && target(e, m_g) == m_v) || (source(e, m_g) == m_v && target(e, m_g) == m_u); } Vertex m_u, m_v; const Graph& m_g; }; template < typename Vertex, typename Graph > inline connects_predicate< Vertex, Graph > connects( Vertex u, Vertex v, const Graph& g) { return connects_predicate< Vertex, Graph >(u, v, g); } // Need to convert all of these printing functions to take an ostream object // -JGS template < class IncidenceGraph, class Name > void print_in_edges( const IncidenceGraph& G, Name name, std::ostream& os = std::cout) { typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) { os << get(name, *ui) << " <-- "; typename graph_traits< IncidenceGraph >::in_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = in_edges(*ui, G); ei != ei_end; ++ei) os << get(name, source(*ei, G)) << " "; os << '\n'; } } template < class IncidenceGraph, class Name > void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag, std::ostream& os = std::cout) { typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) { os << get(name, *ui) << " --> "; typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei) os << get(name, target(*ei, G)) << " "; os << '\n'; } } template < class IncidenceGraph, class Name > void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag, std::ostream& os = std::cout) { typename graph_traits< IncidenceGraph >::vertex_iterator ui, ui_end; for (boost::tie(ui, ui_end) = vertices(G); ui != ui_end; ++ui) { os << get(name, *ui) << " <--> "; typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(*ui, G); ei != ei_end; ++ei) os << get(name, target(*ei, G)) << " "; os << '\n'; } } template < class IncidenceGraph, class Name > void print_graph( const IncidenceGraph& G, Name name, std::ostream& os = std::cout) { typedef typename graph_traits< IncidenceGraph >::directed_category Cat; print_graph_dispatch(G, name, Cat(), os); } template < class IncidenceGraph > void print_graph(const IncidenceGraph& G, std::ostream& os = std::cout) { print_graph(G, get(vertex_index, G), os); } template < class EdgeListGraph, class Name > void print_edges( const EdgeListGraph& G, Name name, std::ostream& os = std::cout) { typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) os << "(" << get(name, source(*ei, G)) << "," << get(name, target(*ei, G)) << ") "; os << '\n'; } template < class EdgeListGraph, class VertexName, class EdgeName > void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename, std::ostream& os = std::cout) { typename graph_traits< EdgeListGraph >::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) os << get(ename, *ei) << "(" << get(vname, source(*ei, G)) << "," << get(vname, target(*ei, G)) << ") "; os << '\n'; } template < class VertexListGraph, class Name > void print_vertices( const VertexListGraph& G, Name name, std::ostream& os = std::cout) { typename graph_traits< VertexListGraph >::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) os << get(name, *vi) << " "; os << '\n'; } template < class Graph, class Vertex > bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag) { typename graph_traits< Graph >::adjacency_iterator vi, viend, adj_found; boost::tie(vi, viend) = adjacent_vertices(a, g); adj_found = std::find(vi, viend, b); if (adj_found == viend) return false; typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found; boost::tie(oi, oiend) = out_edges(a, g); out_found = std::find_if(oi, oiend, incident_to(b, g)); if (out_found == oiend) return false; typename graph_traits< Graph >::in_edge_iterator ii, iiend, in_found; boost::tie(ii, iiend) = in_edges(b, g); in_found = std::find_if(ii, iiend, incident_from(a, g)); if (in_found == iiend) return false; return true; } template < class Graph, class Vertex > bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag) { typename graph_traits< Graph >::adjacency_iterator vi, viend, found; boost::tie(vi, viend) = adjacent_vertices(a, g); found = std::find(vi, viend, b); if (found == viend) return false; typename graph_traits< Graph >::out_edge_iterator oi, oiend, out_found; boost::tie(oi, oiend) = out_edges(a, g); out_found = std::find_if(oi, oiend, incident_to(b, g)); if (out_found == oiend) return false; return true; } template < class Graph, class Vertex > bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag) { return is_adj_dispatch(g, a, b, directed_tag()); } template < class Graph, class Vertex > bool is_adjacent(Graph& g, Vertex a, Vertex b) { typedef typename graph_traits< Graph >::directed_category Cat; return is_adj_dispatch(g, a, b, Cat()); } template < class Graph, class Edge > bool in_edge_set(Graph& g, Edge e) { typename Graph::edge_iterator ei, ei_end, found; boost::tie(ei, ei_end) = edges(g); found = std::find(ei, ei_end, e); return found != ei_end; } template < class Graph, class Vertex > bool in_vertex_set(Graph& g, Vertex v) { typename Graph::vertex_iterator vi, vi_end, found; boost::tie(vi, vi_end) = vertices(g); found = std::find(vi, vi_end, v); return found != vi_end; } template < class Graph, class Vertex > bool in_edge_set(Graph& g, Vertex u, Vertex v) { typename Graph::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) if (source(*ei, g) == u && target(*ei, g) == v) return true; return false; } // is x a descendant of y? template < typename ParentMap > inline bool is_descendant(typename property_traits< ParentMap >::value_type x, typename property_traits< ParentMap >::value_type y, ParentMap parent) { if (get(parent, x) == x) // x is the root of the tree return false; else if (get(parent, x) == y) return true; else return is_descendant(get(parent, x), y, parent); } // is y reachable from x? template < typename IncidenceGraph, typename VertexColorMap > inline bool is_reachable( typename graph_traits< IncidenceGraph >::vertex_descriptor x, typename graph_traits< IncidenceGraph >::vertex_descriptor y, const IncidenceGraph& g, VertexColorMap color) // should start out white for every vertex { typedef typename property_traits< VertexColorMap >::value_type ColorValue; dfs_visitor<> vis; depth_first_visit(g, x, vis, color); return get(color, y) != color_traits< ColorValue >::white(); } // Is the undirected graph connected? // Is the directed graph strongly connected? template < typename VertexListGraph, typename VertexColorMap > inline bool is_connected(const VertexListGraph& g, VertexColorMap color) { typedef typename property_traits< VertexColorMap >::value_type ColorValue; typedef color_traits< ColorValue > Color; typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end, vi, vi_end, ci, ci_end; for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) if (*ui != *vi) { for (boost::tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci) put(color, *ci, Color::white()); if (!is_reachable(*ui, *vi, g, color)) return false; } return true; } template < typename Graph > bool is_self_loop( typename graph_traits< Graph >::edge_descriptor e, const Graph& g) { return source(e, g) == target(e, g); } template < class T1, class T2 > std::pair< T1, T2 > make_list(const T1& t1, const T2& t2) { return std::make_pair(t1, t2); } template < class T1, class T2, class T3 > std::pair< T1, std::pair< T2, T3 > > make_list( const T1& t1, const T2& t2, const T3& t3) { return std::make_pair(t1, std::make_pair(t2, t3)); } template < class T1, class T2, class T3, class T4 > std::pair< T1, std::pair< T2, std::pair< T3, T4 > > > make_list( const T1& t1, const T2& t2, const T3& t3, const T4& t4) { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); } template < class T1, class T2, class T3, class T4, class T5 > std::pair< T1, std::pair< T2, std::pair< T3, std::pair< T4, T5 > > > > make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5) { return std::make_pair( t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); } namespace graph { // Functor for remove_parallel_edges: edge property of the removed edge is // added to the remaining template < typename EdgeProperty > struct add_removed_edge_property { add_removed_edge_property(EdgeProperty ep) : ep(ep) {} template < typename Edge > void operator()(Edge stay, Edge away) { put(ep, stay, get(ep, stay) + get(ep, away)); } EdgeProperty ep; }; // Same as above: edge property is capacity here template < typename Graph > struct add_removed_edge_capacity : add_removed_edge_property< typename property_map< Graph, edge_capacity_t >::type > { typedef add_removed_edge_property< typename property_map< Graph, edge_capacity_t >::type > base; add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {} }; template < typename Graph > bool has_no_vertices(const Graph& g) { typedef typename boost::graph_traits< Graph >::vertex_iterator vi; std::pair< vi, vi > p = vertices(g); return (p.first == p.second); } template < typename Graph > bool has_no_edges(const Graph& g) { typedef typename boost::graph_traits< Graph >::edge_iterator ei; std::pair< ei, ei > p = edges(g); return (p.first == p.second); } template < typename Graph > bool has_no_out_edges( const typename boost::graph_traits< Graph >::vertex_descriptor& v, const Graph& g) { typedef typename boost::graph_traits< Graph >::out_edge_iterator ei; std::pair< ei, ei > p = out_edges(v, g); return (p.first == p.second); } } // namespace graph template < class PropertyIn, class PropertyOut, class Graph > void copy_vertex_property(PropertyIn p_in, PropertyOut p_out, Graph& g) { BGL_FORALL_VERTICES_T(u, g, Graph) put(p_out, u, get(p_in, g)); } template < class PropertyIn, class PropertyOut, class Graph > void copy_edge_property(PropertyIn p_in, PropertyOut p_out, Graph& g) { BGL_FORALL_EDGES_T(e, g, Graph) put(p_out, e, get(p_in, g)); } // Return true if property_map1 and property_map2 differ // for any of the vertices in graph. template < typename PropertyMapFirst, typename PropertyMapSecond, typename Graph > bool are_property_maps_different(const PropertyMapFirst property_map1, const PropertyMapSecond property_map2, const Graph& graph) { BGL_FORALL_VERTICES_T(vertex, graph, Graph) { if (get(property_map1, vertex) != get(property_map2, vertex)) { return (true); } } return (false); } } /* namespace boost */ #endif /* BOOST_GRAPH_UTILITY_HPP*/