• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
23namespace boost {
24namespace msm {
25namespace mpl_graph {
26namespace detail {
27
28// tag identifying graph implementation as adjacency list (not defined)
29struct 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
33template<typename AdjacencyList>
34struct 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
42template<typename Source, typename GraphData>
43struct produce_out_map<adjacency_list_tag, Source, GraphData> :
44    mpl::at<typename produce_al_outs_map<GraphData>::type, Source>
45{};
46
47template<typename InsMap, typename Source, typename Adjacencies>
48struct 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
57template<typename AdjacencyList>
58struct 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
65template<typename Target, typename GraphData>
66struct 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)
73template<typename Incidences, typename Source, typename Adjacencies>
74struct 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
81template<typename AdjacencyList>
82struct 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
90template<typename GraphData>
91struct 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
98template<typename VertexSet, typename Adjacencies>
99struct insert_adjacencies_targets : // adjacencies'
100    mpl::reverse_fold<Adjacencies,
101              VertexSet,
102              mpl::insert<mpl::_1, mpl::second<mpl::_2> > >
103{};
104
105template<typename GraphData>
106struct 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
115template<typename GraphData>
116struct 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
129