msm/mpl_graph/mpl_graph.hpp

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 // mpl_graph - defines a metadata implementation of the BGL immutable graph concepts
0006
0007 // (c) 2008 Gordon Woodhull
0008 // Distributed under the Boost Software License, Version 1.0.
0009 // (See accompanying file LICENSEmpl::_1_0.txt or copy at
0010 // http://www.boost.org/LICENSEmpl::_1_0.txt)
0011
0012 #ifndef BOOST_MSM_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED
0013 #define BOOST_MSM_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED
0014
0015 #include <boost/msm/mpl_graph/detail/graph_implementation_interface.ipp>
0016
0017 #include <boost/mpl/vector.hpp>
0018 #include <boost/mpl/pair.hpp>
0019 #include <boost/mpl/fold.hpp>
0020 #include <boost/mpl/push_back.hpp>
0021 #include <boost/mpl/at.hpp>
0022 #include <boost/mpl/size.hpp>
0023 #include <boost/mpl/plus.hpp>
0024 #include <boost/mpl/transform.hpp>
0025 #include <boost/mpl/back_inserter.hpp>
0026
0027 namespace boost {
0028 namespace msm {
0029 namespace mpl_graph {
0030
0031 // Boost Graph concepts, MPL style
0032
0033 // The metafunctions of the public interface rely
0034 // metafunctions in the graph implementation to transform the input
0035 // into the maps which are required to deliver results.  Since the
0036 // maps are produced lazily and are memoized, all of the graph
0037 // concepts can be supported with no cost until they are actually
0038 // used.
0039
0040 // Each of these dispatch to the correct producer metafunctions based
0041 // on the representation inner type tag
0042
0043
0044
0045 // IncidenceGraph
0046 template<typename Edge, typename Graph>
0047 struct source :
0048     mpl::first<typename mpl::at<typename detail::produce_edge_st_map<typename Graph::representation, typename Graph::data>::type,Edge>::type>
0049 {};
0050 template<typename Edge, typename Graph>
0051 struct target :
0052     mpl::second<typename mpl::at<typename detail::produce_edge_st_map<typename Graph::representation, typename Graph::data>::type,Edge>::type>
0053 {};
0054 template<typename Vertex, typename Graph>
0055 struct out_edges :
0056     mpl::fold<typename detail::produce_out_map<typename Graph::representation, Vertex, typename Graph::data>::type,
0057          mpl::vector<>,
0058          mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
0059 {};
0060 template<typename Vertex, typename Graph>
0061 struct out_degree :
0062     mpl::size<typename out_edges<Vertex, Graph>::type>
0063 {};
0064
0065 // BidirectionalGraph
0066 template<typename Vertex, typename Graph>
0067 struct in_edges :
0068     mpl::fold<typename detail::produce_in_map<typename Graph::representation, Vertex, typename Graph::data>::type,
0069          mpl::vector<>,
0070          mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
0071 {};
0072 template<typename Vertex, typename Graph>
0073 struct in_degree :
0074     mpl::size<typename in_edges<Vertex, Graph>::type>
0075 {};
0076 template<typename Vertex, typename Graph>
0077 struct degree :
0078     mpl::plus<typename out_degree<Vertex, Graph>::type,typename in_degree<Vertex, Graph>::type>
0079 {};
0080
0081 // AdjacencyGraph
0082 template<typename Vertex, typename Graph>
0083 struct adjacent_vertices :
0084     mpl::transform<typename detail::produce_out_map<typename Graph::representation, Vertex, typename Graph::data>::type,
0085               mpl::second<mpl::_1>,
0086               mpl::back_inserter<mpl::vector<> > >
0087 {};
0088
0089 // VertexListGraph
0090 template<typename Graph>
0091 struct vertices :
0092     detail::produce_vertex_set<typename Graph::representation, typename Graph::data>
0093 {};
0094 template<typename Graph>
0095 struct num_vertices :
0096     mpl::size<typename vertices<Graph>::type>
0097 {};
0098
0099 // EdgeListGraph
0100 template<typename Graph>
0101 struct edges :
0102     detail::produce_edge_set<typename Graph::representation, typename Graph::data>
0103 {};
0104 template<typename Graph>
0105 struct num_edges :
0106     mpl::size<typename edges<Graph>::type>
0107 {};
0108 // source and target are defined in IncidenceGraph
0109
0110 } // mpl_graph
0111 } // msm
0112 } // boost
0113
0114 #endif // BOOST_MSM_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED