ceph/src/boost/libs/msm/include/boost/msm/mpl_graph/detail/adjacency_list_graph.ipp

   1 // Copyright 2008-2010 Gordon Woodhull
   2 // Distributed under the Boost Software License, Version 1.0.
   3 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   4
   5 #ifndef BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
   6 #define BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
   7
   8 // implementation of a graph declared in adjacency list format
   9 // sequence< pair< source_vertex, sequence< pair<edge, target_vertex> > > >
  10
  11 #include <boost/msm/mpl_graph/mpl_utils.hpp>
  12 #include <boost/msm/mpl_graph/detail/incidence_list_graph.ipp>
  13
  14 #include <boost/mpl/copy.hpp>
  15 #include <boost/mpl/inserter.hpp>
  16 #include <boost/mpl/map.hpp>
  17 #include <boost/mpl/insert.hpp>
  18 #include <boost/mpl/fold.hpp>
  19 #include <boost/mpl/pair.hpp>
  20 #include <boost/mpl/at.hpp>
  21 #include <boost/mpl/push_back.hpp>
  22
  23 namespace boost {
  24 namespace msm {
  25 namespace mpl_graph {
  26 namespace detail {
  27
  28 // tag identifying graph implementation as adjacency list (not defined)
  29 struct adjacency_list_tag;
  30
  31 // outs map is really just the same data with the sequences turned into maps
  32 // it might make sense to make another adjacency_map implementation for that case
  33 template<typename AdjacencyList>
  34 struct produce_al_outs_map :
  35     mpl::reverse_fold<AdjacencyList,
  36               mpl::map<>,
  37               mpl::insert<mpl::_1,
  38                           mpl::pair<mpl::first<mpl::_2>, mpl_utils::as_map<mpl::second<mpl::_2> > > > >
  39 {};
  40
  41 // Edge->Target map for a Source for out_*, degree
  42 template<typename Source, typename GraphData>
  43 struct produce_out_map<adjacency_list_tag, Source, GraphData> :
  44     mpl::at<typename produce_al_outs_map<GraphData>::type, Source>
  45 {};
  46
  47 template<typename InsMap, typename Source, typename Adjacencies>
  48 struct produce_in_adjacencies :
  49     mpl::reverse_fold<Adjacencies,
  50               InsMap,
  51               mpl::insert<mpl::_1,
  52                           mpl::pair<mpl::second<mpl::_2>,
  53                                     mpl::insert<mpl_utils::at_or_default<mpl::_1, mpl::second<mpl::_2>, mpl::map<> >,
  54                                                 mpl::pair<mpl::first<mpl::_2>, Source> > > > >
  55 {};
  56
  57 template<typename AdjacencyList>
  58 struct produce_al_ins_map :
  59     mpl::reverse_fold<AdjacencyList,
  60               mpl::map<>,
  61               produce_in_adjacencies<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
  62 {};
  63
  64 // Edge->Source map for a Target for in_*, degree
  65 template<typename Target, typename GraphData>
  66 struct produce_in_map<adjacency_list_tag, Target, GraphData> :
  67     mpl::at<typename produce_al_ins_map<GraphData>::type, Target>
  68 {};
  69
  70 // for everything else to do with edges,
  71 // just produce an incidence list and forward to that graph implementation
  72 // (produce_out_map could, and produce_in_map probably should, be implemented this way too)
  73 template<typename Incidences, typename Source, typename Adjacencies>
  74 struct produce_adjacencies_incidences : // adjacencies'
  75     mpl::reverse_fold<Adjacencies,
  76               Incidences,
  77               mpl::push_back<mpl::_1,
  78                              mpl::vector3<mpl::first<mpl::_2>, Source, mpl::second<mpl::_2> > > >
  79 {};
  80
  81 template<typename AdjacencyList>
  82 struct produce_incidence_list_from_adjacency_list :
  83     mpl::reverse_fold<AdjacencyList,
  84               mpl::vector<>,
  85               produce_adjacencies_incidences<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
  86 {};
  87
  88
  89 // Edge->pair<Source,Target> map for source, target
  90 template<typename GraphData>
  91 struct produce_edge_st_map<adjacency_list_tag, GraphData> :
  92     produce_edge_st_map<incidence_list_tag,
  93                         typename produce_incidence_list_from_adjacency_list<GraphData>::type>
  94 {};
  95
  96
  97 // adjacency list supports zero-degree vertices, which incidence list does not
  98 template<typename VertexSet, typename Adjacencies>
  99 struct insert_adjacencies_targets : // adjacencies'
 100     mpl::reverse_fold<Adjacencies,
 101               VertexSet,
 102               mpl::insert<mpl::_1, mpl::second<mpl::_2> > >
 103 {};
 104
 105 template<typename GraphData>
 106 struct produce_vertex_set<adjacency_list_tag, GraphData> :
 107     mpl::reverse_fold<GraphData,
 108               mpl::set<>,
 109               insert_adjacencies_targets<mpl::insert<mpl::_1, mpl::first<mpl::_2> >,
 110                                          mpl::second<mpl::_2> > >
 111 {};
 112
 113
 114 // Edge set for EdgeListGraph
 115 template<typename GraphData>
 116 struct produce_edge_set<adjacency_list_tag, GraphData> :
 117     produce_edge_set<incidence_list_tag,
 118                      typename produce_incidence_list_from_adjacency_list<GraphData>::type>
 119 {};
 120
 121
 122 } // namespaces
 123 }
 124 }
 125 }
 126
 127 #endif // BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
 128