epoc32/include/stdapis/boost/graph/graph_concepts.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
     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_CONCEPTS_HPP
    12 #define BOOST_GRAPH_CONCEPTS_HPP
    13 
    14 #include <boost/config.hpp>
    15 #include <boost/graph/graph_traits.hpp>
    16 #include <boost/property_map.hpp>
    17 #include <boost/graph/properties.hpp>
    18 #include <boost/concept_check.hpp>
    19 #include <boost/detail/workaround.hpp>
    20 
    21 namespace boost {
    22 
    23   template <class T>
    24   struct MultiPassInputIteratorConcept {
    25     void constraints() {
    26       function_requires< InputIteratorConcept<T> >();
    27     }
    28   };
    29 
    30   template <class G>
    31   struct GraphConcept
    32   {
    33     typedef typename graph_traits<G>::vertex_descriptor vertex_descriptor;
    34     typedef typename graph_traits<G>::directed_category directed_category;
    35     typedef typename graph_traits<G>::edge_parallel_category
    36       edge_parallel_category;
    37     typedef typename graph_traits<G>::traversal_category
    38       traversal_category;
    39     void constraints() {
    40       function_requires< DefaultConstructibleConcept<vertex_descriptor> >();
    41       function_requires< EqualityComparableConcept<vertex_descriptor> >();
    42       function_requires< AssignableConcept<vertex_descriptor> >();
    43     }
    44     G g;
    45   };
    46 
    47   template <class G>
    48   struct IncidenceGraphConcept
    49   {
    50     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
    51     typedef typename graph_traits<G>::out_edge_iterator
    52       out_edge_iterator;
    53     typedef typename graph_traits<G>::traversal_category
    54       traversal_category;
    55     void constraints() {
    56       function_requires< GraphConcept<G> >();
    57       function_requires< MultiPassInputIteratorConcept<out_edge_iterator> >();
    58       function_requires< DefaultConstructibleConcept<edge_descriptor> >();
    59       function_requires< EqualityComparableConcept<edge_descriptor> >();
    60       function_requires< AssignableConcept<edge_descriptor> >();
    61       function_requires< ConvertibleConcept<traversal_category,
    62         incidence_graph_tag> >();
    63 
    64       p = out_edges(u, g);
    65       n = out_degree(u, g);
    66       e = *p.first;
    67       u = source(e, g);
    68       v = target(e, g);
    69       const_constraints(g);
    70     }
    71     void const_constraints(const G& cg) {
    72       p = out_edges(u, cg);
    73       n = out_degree(u, cg);
    74       e = *p.first;
    75       u = source(e, cg);
    76       v = target(e, cg);
    77     }
    78     std::pair<out_edge_iterator, out_edge_iterator> p;
    79     typename graph_traits<G>::vertex_descriptor u, v;
    80     typename graph_traits<G>::edge_descriptor e;
    81     typename graph_traits<G>::degree_size_type n;
    82     G g;
    83   };
    84 
    85   template <class G>
    86   struct BidirectionalGraphConcept
    87   {
    88     typedef typename graph_traits<G>::in_edge_iterator
    89       in_edge_iterator;
    90     typedef typename graph_traits<G>::traversal_category
    91       traversal_category;
    92     void constraints() {
    93       function_requires< IncidenceGraphConcept<G> >();
    94       function_requires< MultiPassInputIteratorConcept<in_edge_iterator> >();
    95       function_requires< ConvertibleConcept<traversal_category,
    96         bidirectional_graph_tag> >();
    97 
    98       p = in_edges(v, g);
    99       n = in_degree(v, g);
   100       e = *p.first;
   101       const_constraints(g);
   102     }
   103     void const_constraints(const G& cg) {
   104       p = in_edges(v, cg);
   105       n = in_degree(v, cg);
   106       e = *p.first;
   107     }
   108     std::pair<in_edge_iterator, in_edge_iterator> p;
   109     typename graph_traits<G>::vertex_descriptor v;
   110     typename graph_traits<G>::edge_descriptor e;
   111     typename graph_traits<G>::degree_size_type n;
   112     G g;
   113   };
   114 
   115   template <class G>
   116   struct AdjacencyGraphConcept
   117   {
   118     typedef typename graph_traits<G>::adjacency_iterator
   119       adjacency_iterator;
   120     typedef typename graph_traits<G>::traversal_category
   121       traversal_category;
   122     void constraints() {
   123       function_requires< GraphConcept<G> >();
   124       function_requires< MultiPassInputIteratorConcept<adjacency_iterator> >();
   125       function_requires< ConvertibleConcept<traversal_category,
   126         adjacency_graph_tag> >();
   127 
   128       p = adjacent_vertices(v, g);
   129       v = *p.first;
   130       const_constraints(g);
   131     }
   132     void const_constraints(const G& cg) {
   133       p = adjacent_vertices(v, cg);
   134     }
   135     std::pair<adjacency_iterator,adjacency_iterator> p;
   136     typename graph_traits<G>::vertex_descriptor v;
   137     G g;
   138   };
   139 
   140 // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
   141 // you want to use vector_as_graph, it is!  I'm sure the graph
   142 // library leaves these out all over the place.  Probably a
   143 // redesign involving specializing a template with a static
   144 // member function is in order :(
   145 //
   146 // It is needed in order to allow us to write using boost::vertices as
   147 // needed for ADL when using vector_as_graph below.
   148 #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)            \
   149  && !BOOST_WORKAROUND(__GNUC__, <= 2)                       \
   150  && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
   151 # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
   152 #endif 
   153 
   154 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
   155 template <class T>
   156 typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
   157 #endif      
   158 
   159   template <class G>
   160   struct VertexListGraphConcept
   161   {
   162     typedef typename graph_traits<G>::vertex_iterator vertex_iterator;
   163     typedef typename graph_traits<G>::vertices_size_type vertices_size_type;
   164     typedef typename graph_traits<G>::traversal_category
   165       traversal_category;
   166     void constraints() {
   167       function_requires< GraphConcept<G> >();
   168       function_requires< MultiPassInputIteratorConcept<vertex_iterator> >();
   169       function_requires< ConvertibleConcept<traversal_category,
   170         vertex_list_graph_tag> >();
   171 
   172 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
   173       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
   174       // you want to use vector_as_graph, it is!  I'm sure the graph
   175       // library leaves these out all over the place.  Probably a
   176       // redesign involving specializing a template with a static
   177       // member function is in order :(
   178       using boost::vertices;
   179 #endif      
   180       p = vertices(g);
   181       v = *p.first;
   182       const_constraints(g);
   183     }
   184     void const_constraints(const G& cg) {
   185 #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
   186       // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if
   187       // you want to use vector_as_graph, it is!  I'm sure the graph
   188       // library leaves these out all over the place.  Probably a
   189       // redesign involving specializing a template with a static
   190       // member function is in order :(
   191       using boost::vertices;
   192 #endif 
   193       
   194       p = vertices(cg);
   195       v = *p.first;
   196       V = num_vertices(cg);
   197     }
   198     std::pair<vertex_iterator,vertex_iterator> p;
   199     typename graph_traits<G>::vertex_descriptor v;
   200     G g;
   201     vertices_size_type V;
   202   };
   203 
   204   template <class G>
   205   struct EdgeListGraphConcept
   206   {
   207     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   208     typedef typename graph_traits<G>::edge_iterator edge_iterator;
   209     typedef typename graph_traits<G>::edges_size_type edges_size_type;
   210     typedef typename graph_traits<G>::traversal_category
   211       traversal_category;
   212     void constraints() {
   213       function_requires< GraphConcept<G> >();
   214       function_requires< MultiPassInputIteratorConcept<edge_iterator> >();
   215       function_requires< DefaultConstructibleConcept<edge_descriptor> >();
   216       function_requires< EqualityComparableConcept<edge_descriptor> >();
   217       function_requires< AssignableConcept<edge_descriptor> >();
   218       function_requires< ConvertibleConcept<traversal_category,
   219         edge_list_graph_tag> >();
   220 
   221       p = edges(g);
   222       e = *p.first;
   223       u = source(e, g);
   224       v = target(e, g);
   225       const_constraints(g);
   226     }
   227     void const_constraints(const G& cg) {
   228       p = edges(cg);
   229       E = num_edges(cg);
   230       e = *p.first;
   231       u = source(e, cg);
   232       v = target(e, cg);
   233     }
   234     std::pair<edge_iterator,edge_iterator> p;
   235     typename graph_traits<G>::vertex_descriptor u, v;
   236     typename graph_traits<G>::edge_descriptor e;
   237     edges_size_type E;
   238     G g;
   239   };
   240 
   241   template <class G>
   242   struct VertexAndEdgeListGraphConcept
   243   {
   244     void constraints() {
   245       function_requires< VertexListGraphConcept<G> >();    
   246       function_requires< EdgeListGraphConcept<G> >();
   247     }
   248   };
   249 
   250   // Where to put the requirement for this constructor?
   251   //      G g(n_vertices);
   252   // Not in mutable graph, then LEDA graph's can't be models of
   253   // MutableGraph.
   254 
   255   template <class G>
   256   struct EdgeMutableGraphConcept
   257   {
   258     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   259     void constraints() {
   260       p = add_edge(u, v, g);
   261       remove_edge(u, v, g);
   262       remove_edge(e, g);
   263       clear_vertex(v, g);
   264     }
   265     G g;
   266     edge_descriptor e;
   267     std::pair<edge_descriptor, bool> p;
   268     typename graph_traits<G>::vertex_descriptor u, v;
   269   };
   270 
   271   template <class G>
   272   struct VertexMutableGraphConcept
   273   {
   274     void constraints() {
   275       v = add_vertex(g);
   276       remove_vertex(v, g);
   277     }
   278     G g;
   279     typename graph_traits<G>::vertex_descriptor u, v;
   280   };
   281 
   282   template <class G>
   283   struct MutableGraphConcept
   284   {
   285     void constraints() {
   286       function_requires< EdgeMutableGraphConcept<G> >();
   287       function_requires< VertexMutableGraphConcept<G> >();
   288     }
   289   };
   290 
   291   template <class edge_descriptor>
   292   struct dummy_edge_predicate {
   293     bool operator()(const edge_descriptor&) const {
   294       return false;
   295     }
   296   };
   297 
   298   template <class G>
   299   struct MutableIncidenceGraphConcept
   300   {
   301     void constraints() {
   302       function_requires< MutableGraphConcept<G> >();
   303       remove_edge(iter, g);
   304       remove_out_edge_if(u, p, g);
   305     }
   306     G g;
   307     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   308     dummy_edge_predicate<edge_descriptor> p;
   309     typename boost::graph_traits<G>::vertex_descriptor u;
   310     typename boost::graph_traits<G>::out_edge_iterator iter;
   311   };
   312 
   313   template <class G>
   314   struct MutableBidirectionalGraphConcept
   315   {
   316     void constraints() {
   317       function_requires< MutableIncidenceGraphConcept<G> >();
   318       remove_in_edge_if(u, p, g);
   319     }
   320     G g;
   321     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   322     dummy_edge_predicate<edge_descriptor> p;
   323     typename boost::graph_traits<G>::vertex_descriptor u;
   324   };
   325 
   326   template <class G>
   327   struct MutableEdgeListGraphConcept
   328   {
   329     void constraints() {
   330       function_requires< EdgeMutableGraphConcept<G> >();
   331       remove_edge_if(p, g);
   332     }
   333     G g;
   334     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   335     dummy_edge_predicate<edge_descriptor> p;
   336   };
   337 
   338   template <class G>
   339   struct VertexMutablePropertyGraphConcept
   340   {
   341     void constraints() {
   342       function_requires< VertexMutableGraphConcept<G> >();
   343       v = add_vertex(vp, g);
   344     }
   345     G g;
   346     typename graph_traits<G>::vertex_descriptor v;
   347     typename vertex_property<G>::type vp;
   348   };
   349 
   350   template <class G>
   351   struct EdgeMutablePropertyGraphConcept
   352   {
   353     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   354     void constraints() {
   355       function_requires< EdgeMutableGraphConcept<G> >();
   356       p = add_edge(u, v, ep, g);
   357     }
   358     G g;
   359     std::pair<edge_descriptor, bool> p;
   360     typename graph_traits<G>::vertex_descriptor u, v;
   361     typename edge_property<G>::type ep;
   362   };
   363 
   364   template <class G>
   365   struct AdjacencyMatrixConcept
   366   {
   367     typedef typename graph_traits<G>::edge_descriptor edge_descriptor;
   368     void constraints() {
   369       function_requires< GraphConcept<G> >();
   370       
   371       p = edge(u, v, g);
   372       const_constraints(g);
   373     }
   374     void const_constraints(const G& cg) {
   375       p = edge(u, v, cg);
   376     }
   377     typename graph_traits<G>::vertex_descriptor u, v;
   378     std::pair<edge_descriptor, bool> p;
   379     G g;
   380   };
   381 
   382   template <class G, class X, class Property>
   383   struct ReadablePropertyGraphConcept
   384   {
   385     typedef typename property_map<G, Property>::const_type const_Map;
   386     void constraints() {
   387       function_requires< GraphConcept<G> >();
   388       function_requires< ReadablePropertyMapConcept<const_Map, X> >();
   389 
   390       const_constraints(g);
   391     }
   392     void const_constraints(const G& cg) {
   393       const_Map pmap = get(Property(), cg);
   394       pval = get(Property(), cg, x);
   395       ignore_unused_variable_warning(pmap);
   396     }
   397     G g;
   398     X x;
   399     typename property_traits<const_Map>::value_type pval;
   400   };
   401 
   402   template <class G, class X, class Property>
   403   struct PropertyGraphConcept
   404   {
   405     typedef typename property_map<G, Property>::type Map;
   406     void constraints() {
   407       function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
   408       function_requires< ReadWritePropertyMapConcept<Map, X> >();
   409 
   410       Map pmap = get(Property(), g);
   411       pval = get(Property(), g, x);
   412       put(Property(), g, x, pval);
   413       ignore_unused_variable_warning(pmap);
   414     }
   415     G g;
   416     X x;
   417     typename property_traits<Map>::value_type pval;
   418   };
   419 
   420   template <class G, class X, class Property>
   421   struct LvaluePropertyGraphConcept
   422   {
   423     typedef typename property_map<G, Property>::type Map;
   424     typedef typename property_map<G, Property>::const_type const_Map;
   425     void constraints() {
   426       function_requires< ReadablePropertyGraphConcept<G, X, Property> >();
   427       function_requires< LvaluePropertyMapConcept<const_Map, X> >();
   428 
   429       pval = get(Property(), g, x);
   430       put(Property(), g, x, pval);
   431     }
   432     G g;
   433     X x;
   434     typename property_traits<Map>::value_type pval;
   435   };
   436 
   437   // This needs to move out of the graph library
   438   template <class B>
   439   struct BufferConcept
   440   {
   441     void constraints() {
   442       b.push(t);
   443       b.pop();
   444       typename B::value_type& v = b.top();
   445       const_constraints(b);
   446       ignore_unused_variable_warning(v);
   447     }
   448     void const_constraints(const B& cb) {
   449       const typename B::value_type& v = cb.top();
   450       n = cb.size();
   451       bool e = cb.empty();
   452       ignore_unused_variable_warning(v);
   453       ignore_unused_variable_warning(e);
   454     }
   455     typename B::size_type n;
   456     typename B::value_type t;
   457     B b;
   458   };
   459 
   460   template <class C>
   461   struct ColorValueConcept
   462   {
   463     void constraints() {
   464       function_requires< EqualityComparableConcept<C> >();
   465       function_requires< DefaultConstructibleConcept<C> >();
   466 
   467       c = color_traits<C>::white();
   468       c = color_traits<C>::gray();
   469       c = color_traits<C>::black();
   470     }
   471     C c;
   472   };
   473 
   474   template <class M, class I, class V>
   475   struct BasicMatrixConcept
   476   {
   477     void constraints() {
   478       V& elt = A[i][j];
   479       const_constraints(A);
   480       ignore_unused_variable_warning(elt);      
   481     }
   482     void const_constraints(const M& cA) {
   483       const V& elt = cA[i][j];
   484       ignore_unused_variable_warning(elt);      
   485     }
   486     M A;
   487     I i, j;
   488   };
   489 
   490 } // namespace boost
   491 
   492 #endif /* BOOST_GRAPH_CONCEPTS_H */