williamr@2: //
williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: //
williamr@2: #ifndef BOOST_GRAPH_UTILITY_HPP
williamr@2: #define BOOST_GRAPH_UTILITY_HPP
williamr@2: 
williamr@2: #include <stdlib.h>
williamr@2: #include <iostream>
williamr@2: #include <algorithm>
williamr@2: #include <assert.h>
williamr@2: #include <boost/config.hpp>
williamr@2: #include <boost/tuple/tuple.hpp>
williamr@2: 
williamr@2: #if !defined BOOST_NO_SLIST
williamr@2: #  ifdef BOOST_SLIST_HEADER
williamr@2: #    include BOOST_SLIST_HEADER
williamr@2: #  else
williamr@2: #    include <slist>
williamr@2: #  endif
williamr@2: #endif
williamr@2: 
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: #include <boost/pending/container_traits.hpp>
williamr@2: #include <boost/graph/depth_first_search.hpp>
williamr@2: // iota moved to detail/algorithm.hpp
williamr@2: #include <boost/detail/algorithm.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   // Provide an undirected graph interface alternative to the
williamr@2:   // the source() and target() edge functions.
williamr@2:   template <class UndirectedGraph>
williamr@2:   inline 
williamr@2:   std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,
williamr@2:             typename graph_traits<UndirectedGraph>::vertex_descriptor>
williamr@2:   incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,
williamr@2:            UndirectedGraph& g)
williamr@2:   {
williamr@2:     return std::make_pair(source(e,g), target(e,g));
williamr@2:   }
williamr@2: 
williamr@2:   // Provide an undirected graph interface alternative
williamr@2:   // to the out_edges() function.
williamr@2:   template <class Graph>
williamr@2:   inline 
williamr@2:   std::pair<typename graph_traits<Graph>::out_edge_iterator,
williamr@2:             typename graph_traits<Graph>::out_edge_iterator>
williamr@2:   incident_edges(typename graph_traits<Graph>::vertex_descriptor u,
williamr@2:                  Graph& g)
williamr@2:   {
williamr@2:     return out_edges(u, g);
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph>
williamr@2:   inline typename graph_traits<Graph>::vertex_descriptor
williamr@2:   opposite(typename graph_traits<Graph>::edge_descriptor e,
williamr@2:            typename graph_traits<Graph>::vertex_descriptor v,
williamr@2:            const Graph& g)
williamr@2:   {
williamr@2:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
williamr@2:     if (v == source(e, g))
williamr@2:       return target(e, g);
williamr@2:     else if (v == target(e, g))
williamr@2:       return source(e, g);
williamr@2:     else
williamr@2:       return vertex_descriptor();
williamr@2:   }
williamr@2: 
williamr@2:   //===========================================================================
williamr@2:   // Some handy predicates
williamr@2: 
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   struct incident_from_predicate {
williamr@2:     incident_from_predicate(Vertex u, const Graph& g)
williamr@2:       : m_u(u), m_g(g) { }
williamr@2:     template <class Edge>
williamr@2:     bool operator()(const Edge& e) const {
williamr@2:       return source(e, m_g) == m_u;
williamr@2:     }
williamr@2:     Vertex m_u;
williamr@2:     const Graph& m_g;
williamr@2:   };
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   inline incident_from_predicate<Vertex, Graph>
williamr@2:   incident_from(Vertex u, const Graph& g) {
williamr@2:     return incident_from_predicate<Vertex, Graph>(u, g);
williamr@2:   }
williamr@2:   
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   struct incident_to_predicate {
williamr@2:     incident_to_predicate(Vertex u, const Graph& g)
williamr@2:       : m_u(u), m_g(g) { }
williamr@2:     template <class Edge>
williamr@2:     bool operator()(const Edge& e) const {
williamr@2:       return target(e, m_g) == m_u;
williamr@2:     }
williamr@2:     Vertex m_u;
williamr@2:     const Graph& m_g;
williamr@2:   };
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   inline incident_to_predicate<Vertex, Graph>
williamr@2:   incident_to(Vertex u, const Graph& g) {
williamr@2:     return incident_to_predicate<Vertex, Graph>(u, g);
williamr@2:   }
williamr@2: 
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   struct incident_on_predicate {
williamr@2:     incident_on_predicate(Vertex u, const Graph& g)
williamr@2:       : m_u(u), m_g(g) { }
williamr@2:     template <class Edge>
williamr@2:     bool operator()(const Edge& e) const {
williamr@2:       return source(e, m_g) == m_u || target(e, m_g) == m_u;
williamr@2:     }
williamr@2:     Vertex m_u;
williamr@2:     const Graph& m_g;
williamr@2:   };
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   inline incident_on_predicate<Vertex, Graph>
williamr@2:   incident_on(Vertex u, const Graph& g) {
williamr@2:     return incident_on_predicate<Vertex, Graph>(u, g);
williamr@2:   }
williamr@2:   
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   struct connects_predicate {
williamr@2:     connects_predicate(Vertex u, Vertex v, const Graph& g)
williamr@2:       : m_u(u), m_v(v), m_g(g) { }
williamr@2:     template <class Edge>
williamr@2:     bool operator()(const Edge& e) const {
williamr@2:       if (is_directed(m_g))
williamr@2:         return source(e, m_g) == m_u && target(e, m_g) == m_v;
williamr@2:       else
williamr@2:         return (source(e, m_g) == m_u && target(e, m_g) == m_v)
williamr@2:           || (source(e, m_g) == m_v && target(e, m_g) == m_u);
williamr@2:     }
williamr@2:     Vertex m_u, m_v;
williamr@2:     const Graph& m_g;
williamr@2:   };
williamr@2:   template <typename Vertex, typename Graph>
williamr@2:   inline connects_predicate<Vertex, Graph>
williamr@2:   connects(Vertex u, Vertex v, const Graph& g) {
williamr@2:           return connects_predicate<Vertex, Graph>(u, v, g);
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   // Need to convert all of these printing functions to take an ostream object
williamr@2:   // -JGS
williamr@2: 
williamr@2:   template <class IncidenceGraph, class Name>
williamr@2:   void print_in_edges(const IncidenceGraph& G, Name name)
williamr@2:   {
williamr@2:     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
williamr@2:     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
williamr@2:       std::cout << get(name,*ui) << " <-- ";
williamr@2:       typename graph_traits<IncidenceGraph>
williamr@2:         ::in_edge_iterator ei, ei_end;
williamr@2:       for(tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)
williamr@2:         std::cout << get(name,source(*ei,G)) << " ";
williamr@2:       std::cout << std::endl;
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   template <class IncidenceGraph, class Name>
williamr@2:   void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag)
williamr@2:   {
williamr@2:     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
williamr@2:     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
williamr@2:       std::cout << get(name,*ui) << " --> ";
williamr@2:       typename graph_traits<IncidenceGraph>
williamr@2:         ::out_edge_iterator ei, ei_end;
williamr@2:       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
williamr@2:         std::cout << get(name,target(*ei,G)) << " ";
williamr@2:       std::cout << std::endl;
williamr@2:     }
williamr@2:   }
williamr@2:   template <class IncidenceGraph, class Name>
williamr@2:   void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag)
williamr@2:   {
williamr@2:     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;
williamr@2:     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {
williamr@2:       std::cout << get(name,*ui) << " <--> ";
williamr@2:       typename graph_traits<IncidenceGraph>
williamr@2:         ::out_edge_iterator ei, ei_end;
williamr@2:       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)
williamr@2:         std::cout << get(name,target(*ei,G)) << " ";
williamr@2:       std::cout << std::endl;
williamr@2:     }
williamr@2:   }
williamr@2:   template <class IncidenceGraph, class Name>
williamr@2:   void print_graph(const IncidenceGraph& G, Name name)
williamr@2:   {
williamr@2:     typedef typename graph_traits<IncidenceGraph>
williamr@2:       ::directed_category Cat;
williamr@2:     print_graph_dispatch(G, name, Cat());
williamr@2:   }
williamr@2:   template <class IncidenceGraph>
williamr@2:   void print_graph(const IncidenceGraph& G) {
williamr@2:     print_graph(G, get(vertex_index, G));
williamr@2:   }
williamr@2: 
williamr@2:   template <class EdgeListGraph, class Name>
williamr@2:   void print_edges(const EdgeListGraph& G, Name name)
williamr@2:   {
williamr@2:     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
williamr@2:     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
williamr@2:       std::cout << "(" << get(name, source(*ei, G))
williamr@2:                 << "," << get(name, target(*ei, G)) << ") ";
williamr@2:     std::cout << std::endl;
williamr@2:   }
williamr@2: 
williamr@2:   template <class EdgeListGraph, class VertexName, class EdgeName>
williamr@2:   void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename)
williamr@2:   {
williamr@2:     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;
williamr@2:     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
williamr@2:       std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G))
williamr@2:                 << "," << get(vname, target(*ei, G)) << ") ";
williamr@2:     std::cout << std::endl;
williamr@2:   }
williamr@2: 
williamr@2:   template <class VertexListGraph, class Name>
williamr@2:   void print_vertices(const VertexListGraph& G, Name name)
williamr@2:   {
williamr@2:     typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;
williamr@2:     for (tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)
williamr@2:       std::cout << get(name,*vi) << " ";
williamr@2:     std::cout << std::endl;
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)
williamr@2:   {
williamr@2:     typedef typename graph_traits<Graph>::edge_descriptor 
williamr@2:       edge_descriptor;
williamr@2:     typename graph_traits<Graph>::adjacency_iterator vi, viend, 
williamr@2:       adj_found;
williamr@2:     tie(vi, viend) = adjacent_vertices(a, g);
williamr@2:     adj_found = std::find(vi, viend, b);
williamr@2:     if (adj_found == viend)
williamr@2:       return false;  
williamr@2: 
williamr@2:     typename graph_traits<Graph>::out_edge_iterator oi, oiend, 
williamr@2:       out_found;
williamr@2:     tie(oi, oiend) = out_edges(a, g);
williamr@2:     out_found = std::find_if(oi, oiend, incident_to(b, g));
williamr@2:     if (out_found == oiend)
williamr@2:       return false;
williamr@2: 
williamr@2:     typename graph_traits<Graph>::in_edge_iterator ii, iiend, 
williamr@2:       in_found;
williamr@2:     tie(ii, iiend) = in_edges(b, g);
williamr@2:     in_found = std::find_if(ii, iiend, incident_from(a, g));
williamr@2:     if (in_found == iiend)
williamr@2:       return false;
williamr@2: 
williamr@2:     return true;
williamr@2:   }
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)
williamr@2:   {
williamr@2:     typedef typename graph_traits<Graph>::edge_descriptor 
williamr@2:       edge_descriptor;
williamr@2:     typename graph_traits<Graph>::adjacency_iterator vi, viend, found;
williamr@2:     tie(vi, viend) = adjacent_vertices(a, g);
williamr@2: #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
williamr@2:     // Getting internal compiler error with std::find()
williamr@2:     found = viend;
williamr@2:     for (; vi != viend; ++vi)
williamr@2:       if (*vi == b) {
williamr@2:         found = vi;
williamr@2:         break;
williamr@2:       }
williamr@2: #else
williamr@2:     found = std::find(vi, viend, b);
williamr@2: #endif
williamr@2:     if ( found == viend )
williamr@2:       return false;
williamr@2: 
williamr@2:     typename graph_traits<Graph>::out_edge_iterator oi, oiend, 
williamr@2:       out_found;
williamr@2:     tie(oi, oiend) = out_edges(a, g);
williamr@2: 
williamr@2: #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)
williamr@2:     // Getting internal compiler error with std::find()
williamr@2:     out_found = oiend;
williamr@2:     for (; oi != oiend; ++oi)
williamr@2:       if (target(*oi, g) == b) {
williamr@2:         out_found = oi;
williamr@2:         break;
williamr@2:       }
williamr@2: #else
williamr@2:     out_found = std::find_if(oi, oiend, incident_to(b, g));
williamr@2: #endif
williamr@2:     if (out_found == oiend)
williamr@2:       return false;
williamr@2:     return true;
williamr@2:   }
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)
williamr@2:   {
williamr@2:     return is_adj_dispatch(g, a, b, directed_tag());
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool is_adjacent(Graph& g, Vertex a, Vertex b) {
williamr@2:     typedef typename graph_traits<Graph>::directed_category Cat;
williamr@2:     return is_adj_dispatch(g, a, b, Cat());
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph, class Edge>
williamr@2:   bool in_edge_set(Graph& g, Edge e)
williamr@2:   {
williamr@2:     typename Graph::edge_iterator ei, ei_end, found;
williamr@2:     tie(ei, ei_end) = edges(g);
williamr@2:     found = std::find(ei, ei_end, e);
williamr@2:     return found != ei_end;
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool in_vertex_set(Graph& g, Vertex v)
williamr@2:   {
williamr@2:     typename Graph::vertex_iterator vi, vi_end, found;
williamr@2:     tie(vi, vi_end) = vertices(g);
williamr@2:     found = std::find(vi, vi_end, v);
williamr@2:     return found != vi_end;
williamr@2:   }
williamr@2: 
williamr@2:   template <class Graph, class Vertex>
williamr@2:   bool in_edge_set(Graph& g, Vertex u, Vertex v)
williamr@2:   {
williamr@2:     typename Graph::edge_iterator ei, ei_end;
williamr@2:     for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
williamr@2:       if (source(*ei,g) == u && target(*ei,g) == v)
williamr@2:         return true;
williamr@2:     return false;
williamr@2:   }
williamr@2: 
williamr@2:   // is x a descendant of y?
williamr@2:   template <typename ParentMap>
williamr@2:   inline bool is_descendant
williamr@2:   (typename property_traits<ParentMap>::value_type x,
williamr@2:    typename property_traits<ParentMap>::value_type y,
williamr@2:    ParentMap parent) 
williamr@2:   {
williamr@2:     if (get(parent, x) == x) // x is the root of the tree
williamr@2:       return false;
williamr@2:     else if (get(parent, x) == y)
williamr@2:       return true;
williamr@2:     else
williamr@2:       return is_descendant(get(parent, x), y, parent);
williamr@2:   }
williamr@2: 
williamr@2:   // is y reachable from x?
williamr@2:   template <typename IncidenceGraph, typename VertexColorMap>
williamr@2:   inline bool is_reachable
williamr@2:     (typename graph_traits<IncidenceGraph>::vertex_descriptor x,
williamr@2:      typename graph_traits<IncidenceGraph>::vertex_descriptor y,
williamr@2:      const IncidenceGraph& g,
williamr@2:      VertexColorMap color) // should start out white for every vertex
williamr@2:   {
williamr@2:     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
williamr@2:     dfs_visitor<> vis;
williamr@2:     depth_first_visit(g, x, vis, color);
williamr@2:     return get(color, y) != color_traits<ColorValue>::white();
williamr@2:   }
williamr@2: 
williamr@2:   // Is the undirected graph connected?
williamr@2:   // Is the directed graph strongly connected?
williamr@2:   template <typename VertexListGraph, typename VertexColorMap>
williamr@2:   inline bool is_connected(const VertexListGraph& g, VertexColorMap color)
williamr@2:   {
williamr@2:     typedef typename property_traits<VertexColorMap>::value_type ColorValue;
williamr@2:     typedef color_traits<ColorValue> Color;
williamr@2:     typename graph_traits<VertexListGraph>::vertex_iterator 
williamr@2:       ui, ui_end, vi, vi_end, ci, ci_end;
williamr@2:     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
williamr@2:       for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
williamr@2:         if (*ui != *vi) {
williamr@2:           for (tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci) 
williamr@2:             put(color, *ci, Color::white());
williamr@2:           if (! is_reachable(*ui, *vi, color))
williamr@2:             return false;
williamr@2:         }
williamr@2:     return true;
williamr@2:   }
williamr@2: 
williamr@2:   template <typename Graph>
williamr@2:   bool is_self_loop
williamr@2:     (typename graph_traits<Graph>::edge_descriptor e,
williamr@2:      const Graph& g)
williamr@2:   {
williamr@2:     return source(e, g) == target(e, g);
williamr@2:   }
williamr@2: 
williamr@2: 
williamr@2:   template <class T1, class T2>
williamr@2:   std::pair<T1,T2> 
williamr@2:   make_list(const T1& t1, const T2& t2) 
williamr@2:     { return std::make_pair(t1, t2); }
williamr@2: 
williamr@2:   template <class T1, class T2, class T3>
williamr@2:   std::pair<T1,std::pair<T2,T3> > 
williamr@2:   make_list(const T1& t1, const T2& t2, const T3& t3)
williamr@2:     { return std::make_pair(t1, std::make_pair(t2, t3)); }
williamr@2: 
williamr@2:   template <class T1, class T2, class T3, class T4>
williamr@2:   std::pair<T1,std::pair<T2,std::pair<T3,T4> > > 
williamr@2:   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)
williamr@2:     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }
williamr@2: 
williamr@2:   template <class T1, class T2, class T3, class T4, class T5>
williamr@2:   std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > > 
williamr@2:   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
williamr@2:     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
williamr@2: 
williamr@2: } /* namespace boost */
williamr@2: 
williamr@2: #endif /* BOOST_GRAPH_UTILITY_HPP*/