| // |
| //======================================================================= |
| // 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> |
| |
| #if !defined BOOST_NO_SLIST |
| # ifdef BOOST_SLIST_HEADER |
| # include BOOST_SLIST_HEADER |
| # else |
| # include <slist> |
| # endif |
| #endif |
| |
| #include <boost/graph/graph_traits.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) |
| { |
| typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end; |
| for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) { |
| std::cout << 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) |
| std::cout << get(name,source(*ei,G)) << " "; |
| std::cout << std::endl; |
| } |
| } |
| |
| template <class IncidenceGraph, class Name> |
| void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag) |
| { |
| typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end; |
| for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) { |
| std::cout << 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) |
| std::cout << get(name,target(*ei,G)) << " "; |
| std::cout << std::endl; |
| } |
| } |
| template <class IncidenceGraph, class Name> |
| void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag) |
| { |
| typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end; |
| for (boost::tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) { |
| std::cout << 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) |
| std::cout << get(name,target(*ei,G)) << " "; |
| std::cout << std::endl; |
| } |
| } |
| template <class IncidenceGraph, class Name> |
| void print_graph(const IncidenceGraph& G, Name name) |
| { |
| typedef typename graph_traits<IncidenceGraph> |
| ::directed_category Cat; |
| print_graph_dispatch(G, name, Cat()); |
| } |
| template <class IncidenceGraph> |
| void print_graph(const IncidenceGraph& G) { |
| print_graph(G, get(vertex_index, G)); |
| } |
| |
| template <class EdgeListGraph, class Name> |
| void print_edges(const EdgeListGraph& G, Name name) |
| { |
| typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end; |
| for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) |
| std::cout << "(" << get(name, source(*ei, G)) |
| << "," << get(name, target(*ei, G)) << ") "; |
| std::cout << std::endl; |
| } |
| |
| template <class EdgeListGraph, class VertexName, class EdgeName> |
| void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename) |
| { |
| typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end; |
| for (boost::tie(ei, ei_end) = edges(G); ei != ei_end; ++ei) |
| std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G)) |
| << "," << get(vname, target(*ei, G)) << ") "; |
| std::cout << std::endl; |
| } |
| |
| template <class VertexListGraph, class Name> |
| void print_vertices(const VertexListGraph& G, Name name) |
| { |
| typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end; |
| for (boost::tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi) |
| std::cout << get(name,*vi) << " "; |
| std::cout << std::endl; |
| } |
| |
| template <class Graph, class Vertex> |
| bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag) |
| { |
| typedef typename graph_traits<Graph>::edge_descriptor |
| edge_descriptor; |
| 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) |
| { |
| typedef typename graph_traits<Graph>::edge_descriptor |
| edge_descriptor; |
| typename graph_traits<Graph>::adjacency_iterator vi, viend, found; |
| boost::tie(vi, viend) = adjacent_vertices(a, g); |
| #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT) |
| // Getting internal compiler error with std::find() |
| found = viend; |
| for (; vi != viend; ++vi) |
| if (*vi == b) { |
| found = vi; |
| break; |
| } |
| #else |
| found = std::find(vi, viend, b); |
| #endif |
| if ( found == viend ) |
| return false; |
| |
| typename graph_traits<Graph>::out_edge_iterator oi, oiend, |
| out_found; |
| boost::tie(oi, oiend) = out_edges(a, g); |
| |
| #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT) |
| // Getting internal compiler error with std::find() |
| out_found = oiend; |
| for (; oi != oiend; ++oi) |
| if (target(*oi, g) == b) { |
| out_found = oi; |
| break; |
| } |
| #else |
| out_found = std::find_if(oi, oiend, incident_to(b, g)); |
| #endif |
| 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 |
| |
| #include <boost/graph/iteration_macros.hpp> |
| |
| 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*/ |