1 //

     2 //=======================================================================

     3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

     5 //

     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 //=======================================================================

    10 //

    11 #ifndef BOOST_GRAPH_UTILITY_HPP

    12 #define BOOST_GRAPH_UTILITY_HPP

    13 

    14 #include <stdlib.h>

    15 #include <iostream>

    16 #include <algorithm>

    17 #include <assert.h>

    18 #include <boost/config.hpp>

    19 #include <boost/tuple/tuple.hpp>

    20 

    21 #if !defined BOOST_NO_SLIST

    22 #  ifdef BOOST_SLIST_HEADER

    23 #    include BOOST_SLIST_HEADER

    24 #  else

    25 #    include <slist>

    26 #  endif

    27 #endif

    28 

    29 #include <boost/graph/graph_traits.hpp>

    30 #include <boost/graph/properties.hpp>

    31 #include <boost/pending/container_traits.hpp>

    32 #include <boost/graph/depth_first_search.hpp>

    33 // iota moved to detail/algorithm.hpp

    34 #include <boost/detail/algorithm.hpp>

    35 

    36 namespace boost {

    37 

    38   // Provide an undirected graph interface alternative to the

    39   // the source() and target() edge functions.

    40   template <class UndirectedGraph>

    41   inline 

    42   std::pair<typename graph_traits<UndirectedGraph>::vertex_descriptor,

    43             typename graph_traits<UndirectedGraph>::vertex_descriptor>

    44   incident(typename graph_traits<UndirectedGraph>::edge_descriptor e,

    45            UndirectedGraph& g)

    46   {

    47     return std::make_pair(source(e,g), target(e,g));

    48   }

    49 

    50   // Provide an undirected graph interface alternative

    51   // to the out_edges() function.

    52   template <class Graph>

    53   inline 

    54   std::pair<typename graph_traits<Graph>::out_edge_iterator,

    55             typename graph_traits<Graph>::out_edge_iterator>

    56   incident_edges(typename graph_traits<Graph>::vertex_descriptor u,

    57                  Graph& g)

    58   {

    59     return out_edges(u, g);

    60   }

    61 

    62   template <class Graph>

    63   inline typename graph_traits<Graph>::vertex_descriptor

    64   opposite(typename graph_traits<Graph>::edge_descriptor e,

    65            typename graph_traits<Graph>::vertex_descriptor v,

    66            const Graph& g)

    67   {

    68     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

    69     if (v == source(e, g))

    70       return target(e, g);

    71     else if (v == target(e, g))

    72       return source(e, g);

    73     else

    74       return vertex_descriptor();

    75   }

    76 

    77   //===========================================================================

    78   // Some handy predicates

    79 

    80   template <typename Vertex, typename Graph>

    81   struct incident_from_predicate {

    82     incident_from_predicate(Vertex u, const Graph& g)

    83       : m_u(u), m_g(g) { }

    84     template <class Edge>

    85     bool operator()(const Edge& e) const {

    86       return source(e, m_g) == m_u;

    87     }

    88     Vertex m_u;

    89     const Graph& m_g;

    90   };

    91   template <typename Vertex, typename Graph>

    92   inline incident_from_predicate<Vertex, Graph>

    93   incident_from(Vertex u, const Graph& g) {

    94     return incident_from_predicate<Vertex, Graph>(u, g);

    95   }

    96   

    97   template <typename Vertex, typename Graph>

    98   struct incident_to_predicate {

    99     incident_to_predicate(Vertex u, const Graph& g)

   100       : m_u(u), m_g(g) { }

   101     template <class Edge>

   102     bool operator()(const Edge& e) const {

   103       return target(e, m_g) == m_u;

   104     }

   105     Vertex m_u;

   106     const Graph& m_g;

   107   };

   108   template <typename Vertex, typename Graph>

   109   inline incident_to_predicate<Vertex, Graph>

   110   incident_to(Vertex u, const Graph& g) {

   111     return incident_to_predicate<Vertex, Graph>(u, g);

   112   }

   113 

   114   template <typename Vertex, typename Graph>

   115   struct incident_on_predicate {

   116     incident_on_predicate(Vertex u, const Graph& g)

   117       : m_u(u), m_g(g) { }

   118     template <class Edge>

   119     bool operator()(const Edge& e) const {

   120       return source(e, m_g) == m_u || target(e, m_g) == m_u;

   121     }

   122     Vertex m_u;

   123     const Graph& m_g;

   124   };

   125   template <typename Vertex, typename Graph>

   126   inline incident_on_predicate<Vertex, Graph>

   127   incident_on(Vertex u, const Graph& g) {

   128     return incident_on_predicate<Vertex, Graph>(u, g);

   129   }

   130   

   131   template <typename Vertex, typename Graph>

   132   struct connects_predicate {

   133     connects_predicate(Vertex u, Vertex v, const Graph& g)

   134       : m_u(u), m_v(v), m_g(g) { }

   135     template <class Edge>

   136     bool operator()(const Edge& e) const {

   137       if (is_directed(m_g))

   138         return source(e, m_g) == m_u && target(e, m_g) == m_v;

   139       else

   140         return (source(e, m_g) == m_u && target(e, m_g) == m_v)

   141           || (source(e, m_g) == m_v && target(e, m_g) == m_u);

   142     }

   143     Vertex m_u, m_v;

   144     const Graph& m_g;

   145   };

   146   template <typename Vertex, typename Graph>

   147   inline connects_predicate<Vertex, Graph>

   148   connects(Vertex u, Vertex v, const Graph& g) {

   149           return connects_predicate<Vertex, Graph>(u, v, g);

   150   }

   151 

   152 

   153   // Need to convert all of these printing functions to take an ostream object

   154   // -JGS

   155 

   156   template <class IncidenceGraph, class Name>

   157   void print_in_edges(const IncidenceGraph& G, Name name)

   158   {

   159     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;

   160     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {

   161       std::cout << get(name,*ui) << " <-- ";

   162       typename graph_traits<IncidenceGraph>

   163         ::in_edge_iterator ei, ei_end;

   164       for(tie(ei,ei_end) = in_edges(*ui,G); ei != ei_end; ++ei)

   165         std::cout << get(name,source(*ei,G)) << " ";

   166       std::cout << std::endl;

   167     }

   168   }

   169 

   170   template <class IncidenceGraph, class Name>

   171   void print_graph_dispatch(const IncidenceGraph& G, Name name, directed_tag)

   172   {

   173     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;

   174     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {

   175       std::cout << get(name,*ui) << " --> ";

   176       typename graph_traits<IncidenceGraph>

   177         ::out_edge_iterator ei, ei_end;

   178       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)

   179         std::cout << get(name,target(*ei,G)) << " ";

   180       std::cout << std::endl;

   181     }

   182   }

   183   template <class IncidenceGraph, class Name>

   184   void print_graph_dispatch(const IncidenceGraph& G, Name name, undirected_tag)

   185   {

   186     typename graph_traits<IncidenceGraph>::vertex_iterator ui,ui_end;

   187     for (tie(ui,ui_end) = vertices(G); ui != ui_end; ++ui) {

   188       std::cout << get(name,*ui) << " <--> ";

   189       typename graph_traits<IncidenceGraph>

   190         ::out_edge_iterator ei, ei_end;

   191       for(tie(ei,ei_end) = out_edges(*ui,G); ei != ei_end; ++ei)

   192         std::cout << get(name,target(*ei,G)) << " ";

   193       std::cout << std::endl;

   194     }

   195   }

   196   template <class IncidenceGraph, class Name>

   197   void print_graph(const IncidenceGraph& G, Name name)

   198   {

   199     typedef typename graph_traits<IncidenceGraph>

   200       ::directed_category Cat;

   201     print_graph_dispatch(G, name, Cat());

   202   }

   203   template <class IncidenceGraph>

   204   void print_graph(const IncidenceGraph& G) {

   205     print_graph(G, get(vertex_index, G));

   206   }

   207 

   208   template <class EdgeListGraph, class Name>

   209   void print_edges(const EdgeListGraph& G, Name name)

   210   {

   211     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;

   212     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)

   213       std::cout << "(" << get(name, source(*ei, G))

   214                 << "," << get(name, target(*ei, G)) << ") ";

   215     std::cout << std::endl;

   216   }

   217 

   218   template <class EdgeListGraph, class VertexName, class EdgeName>

   219   void print_edges2(const EdgeListGraph& G, VertexName vname, EdgeName ename)

   220   {

   221     typename graph_traits<EdgeListGraph>::edge_iterator ei, ei_end;

   222     for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)

   223       std::cout << get(ename, *ei) << "(" << get(vname, source(*ei, G))

   224                 << "," << get(vname, target(*ei, G)) << ") ";

   225     std::cout << std::endl;

   226   }

   227 

   228   template <class VertexListGraph, class Name>

   229   void print_vertices(const VertexListGraph& G, Name name)

   230   {

   231     typename graph_traits<VertexListGraph>::vertex_iterator vi,vi_end;

   232     for (tie(vi,vi_end) = vertices(G); vi != vi_end; ++vi)

   233       std::cout << get(name,*vi) << " ";

   234     std::cout << std::endl;

   235   }

   236 

   237   template <class Graph, class Vertex>

   238   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, bidirectional_tag)

   239   {

   240     typedef typename graph_traits<Graph>::edge_descriptor 

   241       edge_descriptor;

   242     typename graph_traits<Graph>::adjacency_iterator vi, viend, 

   243       adj_found;

   244     tie(vi, viend) = adjacent_vertices(a, g);

   245     adj_found = std::find(vi, viend, b);

   246     if (adj_found == viend)

   247       return false;  

   248 

   249     typename graph_traits<Graph>::out_edge_iterator oi, oiend, 

   250       out_found;

   251     tie(oi, oiend) = out_edges(a, g);

   252     out_found = std::find_if(oi, oiend, incident_to(b, g));

   253     if (out_found == oiend)

   254       return false;

   255 

   256     typename graph_traits<Graph>::in_edge_iterator ii, iiend, 

   257       in_found;

   258     tie(ii, iiend) = in_edges(b, g);

   259     in_found = std::find_if(ii, iiend, incident_from(a, g));

   260     if (in_found == iiend)

   261       return false;

   262 

   263     return true;

   264   }

   265   template <class Graph, class Vertex>

   266   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, directed_tag)

   267   {

   268     typedef typename graph_traits<Graph>::edge_descriptor 

   269       edge_descriptor;

   270     typename graph_traits<Graph>::adjacency_iterator vi, viend, found;

   271     tie(vi, viend) = adjacent_vertices(a, g);

   272 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)

   273     // Getting internal compiler error with std::find()

   274     found = viend;

   275     for (; vi != viend; ++vi)

   276       if (*vi == b) {

   277         found = vi;

   278         break;

   279       }

   280 #else

   281     found = std::find(vi, viend, b);

   282 #endif

   283     if ( found == viend )

   284       return false;

   285 

   286     typename graph_traits<Graph>::out_edge_iterator oi, oiend, 

   287       out_found;

   288     tie(oi, oiend) = out_edges(a, g);

   289 

   290 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 && defined(__SGI_STL_PORT)

   291     // Getting internal compiler error with std::find()

   292     out_found = oiend;

   293     for (; oi != oiend; ++oi)

   294       if (target(*oi, g) == b) {

   295         out_found = oi;

   296         break;

   297       }

   298 #else

   299     out_found = std::find_if(oi, oiend, incident_to(b, g));

   300 #endif

   301     if (out_found == oiend)

   302       return false;

   303     return true;

   304   }

   305   template <class Graph, class Vertex>

   306   bool is_adj_dispatch(Graph& g, Vertex a, Vertex b, undirected_tag)

   307   {

   308     return is_adj_dispatch(g, a, b, directed_tag());

   309   }

   310 

   311   template <class Graph, class Vertex>

   312   bool is_adjacent(Graph& g, Vertex a, Vertex b) {

   313     typedef typename graph_traits<Graph>::directed_category Cat;

   314     return is_adj_dispatch(g, a, b, Cat());

   315   }

   316 

   317   template <class Graph, class Edge>

   318   bool in_edge_set(Graph& g, Edge e)

   319   {

   320     typename Graph::edge_iterator ei, ei_end, found;

   321     tie(ei, ei_end) = edges(g);

   322     found = std::find(ei, ei_end, e);

   323     return found != ei_end;

   324   }

   325 

   326   template <class Graph, class Vertex>

   327   bool in_vertex_set(Graph& g, Vertex v)

   328   {

   329     typename Graph::vertex_iterator vi, vi_end, found;

   330     tie(vi, vi_end) = vertices(g);

   331     found = std::find(vi, vi_end, v);

   332     return found != vi_end;

   333   }

   334 

   335   template <class Graph, class Vertex>

   336   bool in_edge_set(Graph& g, Vertex u, Vertex v)

   337   {

   338     typename Graph::edge_iterator ei, ei_end;

   339     for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)

   340       if (source(*ei,g) == u && target(*ei,g) == v)

   341         return true;

   342     return false;

   343   }

   344 

   345   // is x a descendant of y?

   346   template <typename ParentMap>

   347   inline bool is_descendant

   348   (typename property_traits<ParentMap>::value_type x,

   349    typename property_traits<ParentMap>::value_type y,

   350    ParentMap parent) 

   351   {

   352     if (get(parent, x) == x) // x is the root of the tree

   353       return false;

   354     else if (get(parent, x) == y)

   355       return true;

   356     else

   357       return is_descendant(get(parent, x), y, parent);

   358   }

   359 

   360   // is y reachable from x?

   361   template <typename IncidenceGraph, typename VertexColorMap>

   362   inline bool is_reachable

   363     (typename graph_traits<IncidenceGraph>::vertex_descriptor x,

   364      typename graph_traits<IncidenceGraph>::vertex_descriptor y,

   365      const IncidenceGraph& g,

   366      VertexColorMap color) // should start out white for every vertex

   367   {

   368     typedef typename property_traits<VertexColorMap>::value_type ColorValue;

   369     dfs_visitor<> vis;

   370     depth_first_visit(g, x, vis, color);

   371     return get(color, y) != color_traits<ColorValue>::white();

   372   }

   373 

   374   // Is the undirected graph connected?

   375   // Is the directed graph strongly connected?

   376   template <typename VertexListGraph, typename VertexColorMap>

   377   inline bool is_connected(const VertexListGraph& g, VertexColorMap color)

   378   {

   379     typedef typename property_traits<VertexColorMap>::value_type ColorValue;

   380     typedef color_traits<ColorValue> Color;

   381     typename graph_traits<VertexListGraph>::vertex_iterator 

   382       ui, ui_end, vi, vi_end, ci, ci_end;

   383     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)

   384       for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   385         if (*ui != *vi) {

   386           for (tie(ci, ci_end) = vertices(g); ci != ci_end; ++ci) 

   387             put(color, *ci, Color::white());

   388           if (! is_reachable(*ui, *vi, color))

   389             return false;

   390         }

   391     return true;

   392   }

   393 

   394   template <typename Graph>

   395   bool is_self_loop

   396     (typename graph_traits<Graph>::edge_descriptor e,

   397      const Graph& g)

   398   {

   399     return source(e, g) == target(e, g);

   400   }

   401 

   402 

   403   template <class T1, class T2>

   404   std::pair<T1,T2> 

   405   make_list(const T1& t1, const T2& t2) 

   406     { return std::make_pair(t1, t2); }

   407 

   408   template <class T1, class T2, class T3>

   409   std::pair<T1,std::pair<T2,T3> > 

   410   make_list(const T1& t1, const T2& t2, const T3& t3)

   411     { return std::make_pair(t1, std::make_pair(t2, t3)); }

   412 

   413   template <class T1, class T2, class T3, class T4>

   414   std::pair<T1,std::pair<T2,std::pair<T3,T4> > > 

   415   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4)

   416     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, t4))); }

   417 

   418   template <class T1, class T2, class T3, class T4, class T5>

   419   std::pair<T1,std::pair<T2,std::pair<T3,std::pair<T4,T5> > > > 

   420   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)

   421     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }

   422 

   423 } /* namespace boost */

   424 

   425 #endif /* BOOST_GRAPH_UTILITY_HPP*/