mpl_graph/detail/incidence_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_INCIDENCE_LIST_GRAPH_IPP_INCLUDED
0006
0007 #define BOOST_MSM_MPL_GRAPH_DETAIL_INCIDENCE_LIST_GRAPH_IPP_INCLUDED
0008
0009 // these metafunctions provide the metadata structures needed by the public interface
0010 // in mpl_graph.hpp
0011
0012 #include <boost/mpl/map.hpp>
0013 #include <boost/mpl/vector.hpp>
0014 #include <boost/mpl/copy.hpp>
0015 #include <boost/mpl/vector.hpp>
0016 #include <boost/mpl/next.hpp>
0017 #include <boost/mpl/front.hpp>
0018 #include <boost/mpl/back.hpp>
0019 #include <boost/mpl/deref.hpp>
0020 #include <boost/mpl/if.hpp>
0021 #include <boost/mpl/size.hpp>
0022 #include <boost/mpl/void.hpp>
0023 #include <boost/mpl/erase_key.hpp>
0024 #include <boost/mpl/has_key.hpp>
0025 #include <boost/mpl/inserter.hpp>
0026 #include <boost/mpl/back_inserter.hpp>
0027 #include <boost/mpl/set.hpp>
0028 #include <boost/mpl/insert.hpp>
0029 #include <boost/mpl/transform.hpp>
0030 #include <boost/mpl/pair.hpp>
0031 #include <boost/mpl/size.hpp>
0032 #include <boost/mpl/fold.hpp>
0033 #include <boost/mpl/transform.hpp>
0034 #include <boost/mpl/at.hpp>
0035 #include <boost/mpl/push_back.hpp>
0036 #include <boost/mpl/filter_view.hpp>
0037 #include <boost/mpl/transform_view.hpp>
0038 #include <boost/mpl/equal.hpp>
0039 #include <boost/type_traits.hpp>
0040
0041
0042 namespace boost {
0043 namespace msm {
0044 namespace mpl_graph {
0045 namespace detail {
0046
0047 // tag to identify this graph implementation (not defined)
0048 struct incidence_list_tag;
0049
0050 // clarifiers
0051 template<typename EST> struct fetch_edge :
0052     mpl::front<EST> {};
0053 template<typename EST> struct fetch_source :
0054     mpl::deref<typename mpl::next<typename mpl::begin<EST>::type>::type> {};
0055 template<typename EST> struct fetch_target :
0056     mpl::back<EST> {};
0057
0058 // Edge->Target map for an Source for out_*, adjacent_vertices
0059 template<typename Source, typename ESTSequence>
0060 struct produce_out_map<incidence_list_tag, Source, ESTSequence> :
0061     mpl::fold<typename mpl::filter_view<ESTSequence, boost::is_same<fetch_source<mpl::_1>,Source> >::type,
0062          mpl::map<>,
0063          mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > >
0064 {};
0065
0066 // Edge->Source map for a Target for in_*, degree
0067 template<typename Target, typename ESTSequence>
0068 struct produce_in_map<incidence_list_tag, Target, ESTSequence> :
0069     mpl::fold<typename mpl::filter_view<ESTSequence,
0070                                         boost::is_same<fetch_target<mpl::_1>,Target> >::type,
0071          mpl::map<>,
0072          mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_source<mpl::_2> > > >
0073
0074 {};
0075 // Edge->pair<Source,Target> map for source, target
0076 template<typename ESTSequence>
0077 struct produce_edge_st_map<incidence_list_tag, ESTSequence> :
0078     mpl::fold<ESTSequence,
0079          mpl::map<>,
0080          mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,
0081                         mpl::pair<fetch_source<mpl::_2>,
0082                              fetch_target<mpl::_2> > > > >
0083 {};
0084 // Vertex set for VertexListGraph
0085 template<typename ESTSequence>
0086 struct produce_vertex_set<incidence_list_tag, ESTSequence> :
0087     mpl::fold<ESTSequence,
0088          typename mpl::fold<ESTSequence,
0089                        mpl::set<>,
0090                        mpl::insert<mpl::_1,fetch_target<mpl::_2> >
0091                        >::type,
0092          mpl::insert<mpl::_1, fetch_source<mpl::_2> > >
0093 {};
0094 // Edge set for EdgeListGraph
0095 template<typename ESTSequence>
0096 struct produce_edge_set<incidence_list_tag, ESTSequence> :
0097     mpl::fold<ESTSequence,
0098         mpl::set<>,
0099         mpl::insert<mpl::_1,fetch_edge<mpl::_2> > >
0100 {};
0101 }
0102 }
0103 }
0104 }
0105
0106 #endif // BOOST_MSM_MPL_GRAPH_DETAIL_INCIDENCE_LIST_GRAPH_IPP_INCLUDED