// 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 | |