mpl_graph/detail/adjacency_list_graph.ipp

0001 // Copyright 2008-2010 Gordon Woodhull
0002 // Distributed under the Boost Software License, Version 1.0.
0003 // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0004
0005 #ifndef BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
0006 #define BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
0007
0008 // implementation of a graph declared in adjacency list format
0009 // sequence< pair< source_vertex, sequence< pair<edge, target_vertex> > > >
0010
0011 #include <boost/msm/mpl_graph/mpl_utils.hpp>
0012 #include <boost/msm/mpl_graph/detail/incidence_list_graph.ipp>
0013
0014 #include <boost/mpl/copy.hpp>
0015 #include <boost/mpl/inserter.hpp>
0016 #include <boost/mpl/map.hpp>
0017 #include <boost/mpl/insert.hpp>
0018 #include <boost/mpl/fold.hpp>
0019 #include <boost/mpl/pair.hpp>
0020 #include <boost/mpl/at.hpp>
0021 #include <boost/mpl/push_back.hpp>
0022
0023 namespace boost {
0024 namespace msm {
0025 namespace mpl_graph {
0026 namespace detail {
0027
0028 // tag identifying graph implementation as adjacency list (not defined)
0029 struct adjacency_list_tag;
0030
0031 // outs map is really just the same data with the sequences turned into maps
0032 // it might make sense to make another adjacency_map implementation for that case
0033 template<typename AdjacencyList>
0034 struct produce_al_outs_map :
0035     mpl::reverse_fold<AdjacencyList,
0036               mpl::map<>,
0037               mpl::insert<mpl::_1,
0038                           mpl::pair<mpl::first<mpl::_2>, mpl_utils::as_map<mpl::second<mpl::_2> > > > >
0039 {};
0040
0041 // Edge->Target map for a Source for out_*, degree
0042 template<typename Source, typename GraphData>
0043 struct produce_out_map<adjacency_list_tag, Source, GraphData> :
0044     mpl::at<typename produce_al_outs_map<GraphData>::type, Source>
0045 {};
0046
0047 template<typename InsMap, typename Source, typename Adjacencies>
0048 struct produce_in_adjacencies :
0049     mpl::reverse_fold<Adjacencies,
0050               InsMap,
0051               mpl::insert<mpl::_1,
0052                           mpl::pair<mpl::second<mpl::_2>,
0053                                     mpl::insert<mpl_utils::at_or_default<mpl::_1, mpl::second<mpl::_2>, mpl::map<> >,
0054                                                 mpl::pair<mpl::first<mpl::_2>, Source> > > > >
0055 {};
0056
0057 template<typename AdjacencyList>
0058 struct produce_al_ins_map :
0059     mpl::reverse_fold<AdjacencyList,
0060               mpl::map<>,
0061               produce_in_adjacencies<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
0062 {};
0063
0064 // Edge->Source map for a Target for in_*, degree
0065 template<typename Target, typename GraphData>
0066 struct produce_in_map<adjacency_list_tag, Target, GraphData> :
0067     mpl::at<typename produce_al_ins_map<GraphData>::type, Target>
0068 {};
0069
0070 // for everything else to do with edges,
0071 // just produce an incidence list and forward to that graph implementation
0072 // (produce_out_map could, and produce_in_map probably should, be implemented this way too)
0073 template<typename Incidences, typename Source, typename Adjacencies>
0074 struct produce_adjacencies_incidences : // adjacencies'
0075     mpl::reverse_fold<Adjacencies,
0076               Incidences,
0077               mpl::push_back<mpl::_1,
0078                              mpl::vector3<mpl::first<mpl::_2>, Source, mpl::second<mpl::_2> > > >
0079 {};
0080
0081 template<typename AdjacencyList>
0082 struct produce_incidence_list_from_adjacency_list :
0083     mpl::reverse_fold<AdjacencyList,
0084               mpl::vector<>,
0085               produce_adjacencies_incidences<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
0086 {};
0087
0088
0089 // Edge->pair<Source,Target> map for source, target
0090 template<typename GraphData>
0091 struct produce_edge_st_map<adjacency_list_tag, GraphData> :
0092     produce_edge_st_map<incidence_list_tag,
0093                         typename produce_incidence_list_from_adjacency_list<GraphData>::type>
0094 {};
0095
0096
0097 // adjacency list supports zero-degree vertices, which incidence list does not
0098 template<typename VertexSet, typename Adjacencies>
0099 struct insert_adjacencies_targets : // adjacencies'
0100     mpl::reverse_fold<Adjacencies,
0101               VertexSet,
0102               mpl::insert<mpl::_1, mpl::second<mpl::_2> > >
0103 {};
0104
0105 template<typename GraphData>
0106 struct produce_vertex_set<adjacency_list_tag, GraphData> :
0107     mpl::reverse_fold<GraphData,
0108               mpl::set<>,
0109               insert_adjacencies_targets<mpl::insert<mpl::_1, mpl::first<mpl::_2> >,
0110                                          mpl::second<mpl::_2> > >
0111 {};
0112
0113
0114 // Edge set for EdgeListGraph
0115 template<typename GraphData>
0116 struct produce_edge_set<adjacency_list_tag, GraphData> :
0117     produce_edge_set<incidence_list_tag,
0118                      typename produce_incidence_list_from_adjacency_list<GraphData>::type>
0119 {};
0120
0121
0122 } // namespaces
0123 }
0124 }
0125 }
0126
0127 #endif // BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
0128