123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128 |
- // Copyright 2008-2010 Gordon Woodhull
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
- #define BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
- // implementation of a graph declared in adjacency list format
- // sequence< pair< source_vertex, sequence< pair<edge, target_vertex> > > >
- #include <boost/msm/mpl_graph/mpl_utils.hpp>
- #include <boost/msm/mpl_graph/detail/incidence_list_graph.ipp>
- #include <boost/mpl/copy.hpp>
- #include <boost/mpl/inserter.hpp>
- #include <boost/mpl/map.hpp>
- #include <boost/mpl/insert.hpp>
- #include <boost/mpl/fold.hpp>
- #include <boost/mpl/pair.hpp>
- #include <boost/mpl/at.hpp>
- #include <boost/mpl/push_back.hpp>
- namespace boost {
- namespace msm {
- namespace mpl_graph {
- namespace detail {
-
- // tag identifying graph implementation as adjacency list (not defined)
- struct adjacency_list_tag;
- // outs map is really just the same data with the sequences turned into maps
- // it might make sense to make another adjacency_map implementation for that case
- template<typename AdjacencyList>
- struct produce_al_outs_map :
- mpl::reverse_fold<AdjacencyList,
- mpl::map<>,
- mpl::insert<mpl::_1,
- mpl::pair<mpl::first<mpl::_2>, mpl_utils::as_map<mpl::second<mpl::_2> > > > >
- {};
-
- // Edge->Target map for a Source for out_*, degree
- template<typename Source, typename GraphData>
- struct produce_out_map<adjacency_list_tag, Source, GraphData> :
- mpl::at<typename produce_al_outs_map<GraphData>::type, Source>
- {};
- template<typename InsMap, typename Source, typename Adjacencies>
- struct produce_in_adjacencies :
- mpl::reverse_fold<Adjacencies,
- InsMap,
- mpl::insert<mpl::_1,
- mpl::pair<mpl::second<mpl::_2>,
- mpl::insert<mpl_utils::at_or_default<mpl::_1, mpl::second<mpl::_2>, mpl::map<> >,
- mpl::pair<mpl::first<mpl::_2>, Source> > > > >
- {};
-
- template<typename AdjacencyList>
- struct produce_al_ins_map :
- mpl::reverse_fold<AdjacencyList,
- mpl::map<>,
- produce_in_adjacencies<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
- {};
- // Edge->Source map for a Target for in_*, degree
- template<typename Target, typename GraphData>
- struct produce_in_map<adjacency_list_tag, Target, GraphData> :
- mpl::at<typename produce_al_ins_map<GraphData>::type, Target>
- {};
- // for everything else to do with edges,
- // just produce an incidence list and forward to that graph implementation
- // (produce_out_map could, and produce_in_map probably should, be implemented this way too)
- template<typename Incidences, typename Source, typename Adjacencies>
- struct produce_adjacencies_incidences : // adjacencies'
- mpl::reverse_fold<Adjacencies,
- Incidences,
- mpl::push_back<mpl::_1,
- mpl::vector3<mpl::first<mpl::_2>, Source, mpl::second<mpl::_2> > > >
- {};
-
- template<typename AdjacencyList>
- struct produce_incidence_list_from_adjacency_list :
- mpl::reverse_fold<AdjacencyList,
- mpl::vector<>,
- produce_adjacencies_incidences<mpl::_1, mpl::first<mpl::_2>, mpl::second<mpl::_2> > >
- {};
- // Edge->pair<Source,Target> map for source, target
- template<typename GraphData>
- struct produce_edge_st_map<adjacency_list_tag, GraphData> :
- produce_edge_st_map<incidence_list_tag,
- typename produce_incidence_list_from_adjacency_list<GraphData>::type>
- {};
-
- // adjacency list supports zero-degree vertices, which incidence list does not
- template<typename VertexSet, typename Adjacencies>
- struct insert_adjacencies_targets : // adjacencies'
- mpl::reverse_fold<Adjacencies,
- VertexSet,
- mpl::insert<mpl::_1, mpl::second<mpl::_2> > >
- {};
- template<typename GraphData>
- struct produce_vertex_set<adjacency_list_tag, GraphData> :
- mpl::reverse_fold<GraphData,
- mpl::set<>,
- insert_adjacencies_targets<mpl::insert<mpl::_1, mpl::first<mpl::_2> >,
- mpl::second<mpl::_2> > >
- {};
-
- // Edge set for EdgeListGraph
- template<typename GraphData>
- struct produce_edge_set<adjacency_list_tag, GraphData> :
- produce_edge_set<incidence_list_tag,
- typename produce_incidence_list_from_adjacency_list<GraphData>::type>
- {};
- } // namespaces
- }
- }
- }
- #endif // BOOST_MSM_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
|