epoc32/include/stdapis/boost/graph/graph_utility.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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*/