|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r48911 - in sandbox/metagraph: boost/metagraph/mpl_graph boost/metagraph/mpl_graph/detail libs/metagraph/example
From: gordon_at_[hidden]
Date: 2008-09-21 00:27:30
Author: gordon.woodhull
Date: 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
New Revision: 48911
URL: http://svn.boost.org/trac/boost/changeset/48911
Log:
mpl_graph indirection of implementation; adjacency list implementation
Added:
sandbox/metagraph/boost/metagraph/mpl_graph/adjacency_list_graph.hpp (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph/detail/
sandbox/metagraph/boost/metagraph/mpl_graph/detail/adjacency_list_graph.ipp (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph/detail/graph_implementation_interface.ipp (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph/incidence_list_graph.hpp (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph/mpl_utils.hpp (contents, props changed)
sandbox/metagraph/libs/metagraph/example/adjacency_list_graph.cpp (contents, props changed)
Text files modified:
sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp | 8 +
sandbox/metagraph/boost/metagraph/mpl_graph/mpl_graph.hpp | 189 +++++++++------------------------------
sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp | 94 ++++++++++++++-----
sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp | 6
sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp | 27 ++--
5 files changed, 137 insertions(+), 187 deletions(-)
Added: sandbox/metagraph/boost/metagraph/mpl_graph/adjacency_list_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/adjacency_list_graph.hpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,31 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_ADJACENCY_LIST_GRAPH_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_ADJACENCY_LIST_GRAPH_HPP_INCLUDED
+
+// graph implementation based on an adjacency list
+// sequence< pair< source_vertex, sequence< pair<edge, target_vertex> > > >
+
+// adjacency_list_graph labels such a sequence as manipulable by the metafunctions
+// in the corresponding implementation header detail/adjacency_list_graph.ipp
+// to produce the metadata structures needed by mpl_graph.hpp
+
+// the public interface
+#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
+
+// the implementation
+#include <boost/metagraph/mpl_graph/detail/adjacency_list_graph.ipp>
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+
+template<typename AdjacencyList>
+struct adjacency_list_graph {
+ typedef detail::adjacency_list_tag representation;
+ typedef AdjacencyList data;
+};
+
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_ADJACENCY_LIST_GRAPH_HPP_INCLUDED
Modified: sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp (original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/depth_first_search.hpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -1,6 +1,13 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
+
#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/has_key.hpp>
namespace boost {
namespace metagraph {
@@ -121,3 +128,4 @@
} // namespace boost
+#endif // BOOST_METAGRAPH_MPL_GRAPH_DEPTH_FIRST_SEARCH_HPP_INCLUDED
Added: sandbox/metagraph/boost/metagraph/mpl_graph/detail/adjacency_list_graph.ipp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/detail/adjacency_list_graph.ipp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,124 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
+#define BOOST_METAGRAPH_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/metagraph/mpl_graph/mpl_utils.hpp>
+#include <boost/metagraph/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 metagraph {
+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_METAGRAPH_MPL_GRAPH_DETAIL_ADJACENCY_LIST_GRAPH_IPP_INCLUDED
+
Added: sandbox/metagraph/boost/metagraph/mpl_graph/detail/graph_implementation_interface.ipp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/detail/graph_implementation_interface.ipp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,38 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_DETAIL_GRAPH_IMPLEMENTATION_INTERFACE_IPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_DETAIL_GRAPH_IMPLEMENTATION_INTERFACE_IPP_INCLUDED
+
+// forward definitions of the producer metafunctions that need to be specialized for
+// each graph representation
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+namespace detail {
+
+ // Edge->Target map for a Source for out_*, degree
+ template<typename RepresentationTag, typename Source, typename GraphData>
+ struct produce_out_map;
+
+ // Edge->Source map for a Target for in_*, degree
+ template<typename RepresentationTag, typename Target, typename GraphData>
+ struct produce_in_map;
+
+ // Edge->pair<Source,Target> map for source, target
+ template<typename RepresentationTag, typename GraphData>
+ struct produce_edge_st_map;
+
+ // Vertex set for VertexListGraph
+ template<typename RepresentationTag, typename GraphData>
+ struct produce_vertex_set;
+
+ // Edge set for EdgeListGraph
+ template<typename RepresentationTag, typename GraphData>
+ struct produce_edge_set;
+
+} // namespaces
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_DETAIL_GRAPH_IMPLEMENTATION_INTERFACE_IPP_INCLUDED
+
Added: sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,122 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_DETAIL_INCIDENCE_LIST_GRAPH_IPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_DETAIL_INCIDENCE_LIST_GRAPH_IPP_INCLUDED
+
+// these metafunctions provide the metadata structures needed by the public interface
+// in mpl_graph.hpp
+
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/copy.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/next.hpp>
+#include <boost/mpl/front.hpp>
+#include <boost/mpl/back.hpp>
+#include <boost/mpl/deref.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/void.hpp>
+#include <boost/mpl/erase_key.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/inserter.hpp>
+#include <boost/mpl/back_inserter.hpp>
+#include <boost/mpl/set.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/pair.hpp>
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/push_back.hpp>
+#include <boost/mpl/filter_view.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/type_traits.hpp>
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+namespace detail {
+
+// tag to identify this graph implementation (not defined)
+struct incidence_list_tag;
+
+// clarifiers
+template<typename EST> struct fetch_edge :
+ mpl::front<EST> {};
+template<typename EST> struct fetch_source :
+ mpl::deref<typename mpl::next<typename mpl::begin<EST>::type>::type> {};
+template<typename EST> struct fetch_target :
+ mpl::back<EST> {};
+
+//#define MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
+#ifdef MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
+ // this implementation didn't work on msvc - anyway not sure if it's more efficient
+ // to build all maps at once at the expense of lots of map updates, or to use
+ // the many pass, easier-to-read filter-and-build algs below.
+// Source->Edge->Target map for out_*, adjacent_vertices
+template<typename ESTSequence>
+struct produce_il_outs_map :
+ mpl::fold<ESTSequence,
+ mpl::map<>,
+ mpl::insert<mpl::_1,
+ mpl::pair<fetch_source<mpl::_2>,
+ mpl::insert<mpl::if_<mpl::has_key<mpl::_1,fetch_source<mpl::_2> >,
+ mpl::at<mpl::_1,fetch_source<mpl::_2> >,
+ mpl::map<> >,
+ mpl::pair<fetch_edge<mpl::_2>, fetch_target<mpl::_2> > > > > >
+{};
+template<typename Source, typename ESTSequence>
+struct produce_out_map<incidence_list_tag, Source, ESTSequence> :
+ mpl::at<typename produce_il_outs_map<ESTSequence>::type, Source>
+{};
+#else // produce out map by filtering est list
+// Edge->Target map for an Source for out_*, adjacent_vertices
+template<typename Source, typename ESTSequence>
+struct produce_out_map<incidence_list_tag, Source, ESTSequence> :
+ mpl::fold<typename mpl::filter_view<ESTSequence, boost::is_same<fetch_source<mpl::_1>,Source> >::type,
+ mpl::map<>,
+ mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > >
+{};
+#endif
+
+// Edge->Source map for a Target for in_*, degree
+template<typename Target, typename ESTSequence>
+struct produce_in_map<incidence_list_tag, Target, ESTSequence> :
+ mpl::fold<typename mpl::filter_view<ESTSequence,
+ boost::is_same<fetch_target<mpl::_1>,Target> >::type,
+ mpl::map<>,
+ mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_source<mpl::_2> > > >
+
+{};
+// Edge->pair<Source,Target> map for source, target
+template<typename ESTSequence>
+struct produce_edge_st_map<incidence_list_tag, ESTSequence> :
+ mpl::fold<ESTSequence,
+ mpl::map<>,
+ mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,
+ mpl::pair<fetch_source<mpl::_2>,
+ fetch_target<mpl::_2> > > > >
+{};
+// Vertex set for VertexListGraph
+template<typename ESTSequence>
+struct produce_vertex_set<incidence_list_tag, ESTSequence> :
+ mpl::fold<ESTSequence,
+ typename mpl::fold<ESTSequence,
+ mpl::set<>,
+ mpl::insert<mpl::_1,fetch_target<mpl::_2> >
+ >::type,
+ mpl::insert<mpl::_1, fetch_source<mpl::_2> > >
+{};
+// Edge set for EdgeListGraph
+template<typename ESTSequence>
+struct produce_edge_set<incidence_list_tag, ESTSequence> :
+ mpl::fold<ESTSequence,
+ mpl::set<>,
+ mpl::insert<mpl::_1,fetch_edge<mpl::_2> > >
+{};
+}
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_DETAIL_INCIDENCE_LIST_GRAPH_IPP_INCLUDED
Added: sandbox/metagraph/boost/metagraph/mpl_graph/incidence_list_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/incidence_list_graph.hpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,30 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_INCIDENCE_LIST_GRAPH_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_INCIDENCE_LIST_GRAPH_HPP_INCLUDED
+
+// graph implementation based on a an mpl sequence of sequences <Edge,Source,Target>
+
+// incidence_list_graph labels such a sequence as manipulable by the metafunctions
+// in the corresponding implementation header detail/incidence_list_graph.ipp
+// to produce the metadata structures needed by mpl_graph.hpp
+
+// the public interface
+#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
+
+// the implementation
+#include <boost/metagraph/mpl_graph/detail/incidence_list_graph.ipp>
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+
+template<typename EdgeSequence>
+struct incidence_list_graph {
+ typedef detail::incidence_list_tag representation;
+ typedef EdgeSequence data;
+};
+
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_INCIDENCE_LIST_GRAPH_HPP_INCLUDED
Modified: sandbox/metagraph/boost/metagraph/mpl_graph/mpl_graph.hpp
==============================================================================
--- sandbox/metagraph/boost/metagraph/mpl_graph/mpl_graph.hpp (original)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/mpl_graph.hpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -5,205 +5,104 @@
// (See accompanying file LICENSEmpl::_1_0.txt or copy at
// http://www.boost.org/LICENSEmpl::_1_0.txt)
-#ifndef BOOST_MPLGRAPH_H
-#define BOOST_MPLGRAPH_H
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED
+
+#include <boost/metagraph/mpl_graph/detail/graph_implementation_interface.ipp>
-#include <boost/mpl/map.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/copy.hpp>
#include <boost/mpl/vector.hpp>
-#include <boost/mpl/next.hpp>
-#include <boost/mpl/front.hpp>
-#include <boost/mpl/back.hpp>
-#include <boost/mpl/deref.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/size.hpp>
-#include <boost/mpl/void.hpp>
-#include <boost/mpl/erase_key.hpp>
-#include <boost/mpl/has_key.hpp>
-#include <boost/mpl/inserter.hpp>
-#include <boost/mpl/back_inserter.hpp>
-#include <boost/mpl/set.hpp>
-#include <boost/mpl/insert.hpp>
-#include <boost/mpl/transform.hpp>
#include <boost/mpl/pair.hpp>
-#include <boost/mpl/size.hpp>
#include <boost/mpl/fold.hpp>
-#include <boost/mpl/transform.hpp>
-#include <boost/mpl/at.hpp>
#include <boost/mpl/push_back.hpp>
-#include <boost/mpl/filter_view.hpp>
-#include <boost/mpl/equal.hpp>
-#include <boost/type_traits.hpp>
-
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/plus.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/back_inserter.hpp>
namespace boost {
namespace metagraph {
namespace mpl_graph {
-// idea is to lazily produce maps and other metadata structures
-// for looking up the various things U want to look up thru bgl-like interfaces
-
-// currently Edge types must be unique but it might make sense to make them
-// unique per Source and/or Target (which would require a different edge_descriptor)
-
-// also this doesn't provide for vertices with no edges
+// Boost Graph concepts, MPL style
-// edgeseq_graph takes an mpl sequence of sequences <Edge,Source,Target> and wraps it
-// so that the rest of the code knows what it is
-// edgeseq_graph doesn't do anything but label the data as usable by the metafunctions below
-// and provide indirection for other possible input formats (?)
-template<typename EdgeSequence>
-struct edgeseq_graph {
- typedef EdgeSequence est_sequence;
-};
-
-namespace detail {
- // clarifiers
- template<typename EST> struct fetch_edge :
- mpl::front<EST> {};
- template<typename EST> struct fetch_source :
- mpl::deref<typename mpl::next<typename mpl::begin<EST>::type>::type> {};
- template<typename EST> struct fetch_target :
- mpl::back<EST> {};
-
-//#define MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
-#ifdef MPL_GRAPH_PRODUCE_OUTMAP_AS_MAP
- // this implementation didn't work on msvc - anyway not sure if it's more efficient
- // to build all maps at once at the expense of lots of map updates, or to use
- // the many pass, easier-to-read filter-and-build algs below.
- // S->E->T map for out_*, adjacent_vertices
- template<typename EdgeSeqGraph>
- struct produce_outs_map :
- mpl::fold<typename EdgeSeqGraph::est_sequence,
- mpl::map<>,
- mpl::insert<mpl::_1,
- mpl::pair<fetch_source<mpl::_2>,
- mpl::insert<mpl::if_<mpl::has_key<mpl::_1,fetch_source<mpl::_2> >,
- mpl::at<mpl::_1,fetch_source<mpl::_2> >,
- mpl::map<> >,
- mpl::pair<fetch_edge<mpl::_2>, fetch_target<mpl::_2> > > > > >
- {};
- template<typename S, typename EdgeSeqGraph>
- struct produce_out_map :
- mpl::at<typename produce_outs_map<EdgeSeqGraph>::type, S>
- {};
-#else // produce out map via a filtered
- // E->T map for an S for out_*, adjacent_vertices
- template<typename S, typename EdgeSeqGraph>
- struct produce_out_map :
- mpl::fold<typename mpl::filter_view<typename EdgeSeqGraph::est_sequence, boost::is_same<fetch_source<mpl::_1>,S> >::type,
- mpl::map<>,
- mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > >
- {};
-#endif
-
- // E->S map for a T for in_*, degree
- template<typename T, typename EdgeSeqGraph>
- struct produce_in_map :
- mpl::fold<typename mpl::filter_view<typename EdgeSeqGraph::est_sequence,
- boost::is_same<fetch_target<mpl::_1>,T> >::type,
- mpl::map<>,
- mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,fetch_source<mpl::_2> > > >
-
- {};
- // E->pair<S,T> map for source, target
- template<typename EdgeSeqGraph>
- struct produce_edge_st_map :
- mpl::fold<typename EdgeSeqGraph::est_sequence,
- mpl::map<>,
- mpl::insert<mpl::_1,mpl::pair<fetch_edge<mpl::_2>,
- mpl::pair<fetch_source<mpl::_2>,
- fetch_target<mpl::_2> > > > >
- {};
- // Vertex set for VertexListGraph
- template<typename EdgeSeqGraph>
- struct produce_vertex_set :
- mpl::fold<typename EdgeSeqGraph::est_sequence,
- typename mpl::fold<typename EdgeSeqGraph::est_sequence,
- mpl::set<>,
- mpl::insert<mpl::_1,fetch_target<mpl::_2> >
- >::type,
- mpl::insert<mpl::_1, fetch_source<mpl::_2> > >
- {};
- // Edge set for EdgeListGraph
- template<typename EdgeSeqGraph>
- struct produce_edge_set :
- mpl::fold<typename EdgeSeqGraph::est_sequence,
- mpl::set<>,
- mpl::insert<mpl::_1,fetch_edge<mpl::_2> > >
- {};
-}
+// The metafunctions of the public interface rely
+// metafunctions in the graph implementation to transform the input
+// into the maps which are required to deliver results. Since the
+// maps are produced lazily and are memoized, all of the graph
+// concepts can be supported with no cost until they are actually
+// used.
-// Boost Graph concepts, MPL style
+// Each of these dispatch to the correct producer metafunctions based
+// on the representation inner type tag
// IncidenceGraph
-template<typename E, typename G>
+template<typename Edge, typename Graph>
struct source :
- mpl::first<typename mpl::at<typename detail::produce_edge_st_map<G>::type,E>::type>
+ mpl::first<typename mpl::at<typename detail::produce_edge_st_map<typename Graph::representation, typename Graph::data>::type,Edge>::type>
{};
-template<typename E, typename G>
+template<typename Edge, typename Graph>
struct target :
- mpl::second<typename mpl::at<typename detail::produce_edge_st_map<G>::type,E>::type>
+ mpl::second<typename mpl::at<typename detail::produce_edge_st_map<typename Graph::representation, typename Graph::data>::type,Edge>::type>
{};
-template<typename U, typename G>
+template<typename Vertex, typename Graph>
struct out_edges :
- mpl::fold<typename detail::produce_out_map<U,G>::type,
+ mpl::fold<typename detail::produce_out_map<typename Graph::representation, Vertex, typename Graph::data>::type,
mpl::vector<>,
mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
{};
-template<typename U, typename G>
+template<typename Vertex, typename Graph>
struct out_degree :
- mpl::size<typename out_edges<U,G>::type>
+ mpl::size<typename out_edges<Vertex, Graph>::type>
{};
// BidirectionalGraph
-template<typename V, typename G>
+template<typename Vertex, typename Graph>
struct in_edges :
- mpl::fold<typename detail::produce_in_map<V,G>::type,
+ mpl::fold<typename detail::produce_in_map<typename Graph::representation, Vertex, typename Graph::data>::type,
mpl::vector<>,
mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
{};
-template<typename V, typename G>
+template<typename Vertex, typename Graph>
struct in_degree :
- mpl::size<typename in_edges<V,G>::type>
+ mpl::size<typename in_edges<Vertex, Graph>::type>
{};
-template<typename V, typename G>
+template<typename Vertex, typename Graph>
struct degree :
- mpl::plus<typename out_degree<V,G>::type,typename in_degree<V,G>::type>
+ mpl::plus<typename out_degree<Vertex, Graph>::type,typename in_degree<Vertex, Graph>::type>
{};
// AdjacencyGraph
-template<typename V, typename G>
+template<typename Vertex, typename Graph>
struct adjacent_vertices :
- mpl::transform<typename detail::produce_out_map<V,G>::type,
+ mpl::transform<typename detail::produce_out_map<typename Graph::representation, Vertex, typename Graph::data>::type,
mpl::second<mpl::_1>,
mpl::back_inserter<mpl::vector<> > >
{};
// VertexListGraph
-template<typename G>
+template<typename Graph>
struct vertices :
- detail::produce_vertex_set<G>
+ detail::produce_vertex_set<typename Graph::representation, typename Graph::data>
{};
-template<typename G>
+template<typename Graph>
struct num_vertices :
- mpl::size<typename vertices<G>::type>
+ mpl::size<typename vertices<Graph>::type>
{};
// EdgeListGraph
-template<typename G>
+template<typename Graph>
struct edges :
- detail::produce_edge_set<G>
+ detail::produce_edge_set<typename Graph::representation, typename Graph::data>
{};
-template<typename G>
+template<typename Graph>
struct num_edges :
- mpl::size<typename edges<G>::type>
+ mpl::size<typename edges<Graph>::type>
{};
// source and target are defined in IncidenceGraph
-} // mplgraph
+} // mpl_graph
} // metagraph
} // boost
-#endif // BOOST_MPLGRAPH_H
+#endif // BOOST_METAGRAPH_MPL_GRAPH_MPL_GRAPH_HPP_INCLUDED
Added: sandbox/metagraph/boost/metagraph/mpl_graph/mpl_utils.hpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph/mpl_utils.hpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,58 @@
+#ifndef BOOST_METAGRAPH_MPL_GRAPH_MPL_UTILS_HPP_INCLUDED
+#define BOOST_METAGRAPH_MPL_GRAPH_MPL_UTILS_HPP_INCLUDED
+
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/map.hpp>
+#include <boost/mpl/set.hpp>
+#include <boost/mpl/insert.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/has_key.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/and.hpp>
+
+namespace boost {
+namespace metagraph {
+namespace mpl_graph {
+namespace mpl_utils {
+
+// This is a grab bag of little metafunctions I expect already
+// exist under some name I haven't looked for
+
+// I figure there are probably better ways to do all of these things,
+// but for now I'll just write some utilities to isolate my ignorance
+
+template<typename Seq>
+struct as_map :
+ mpl::fold<Seq,
+ mpl::map<>,
+ mpl::insert<mpl::_1, mpl::_2> >
+{};
+template<typename Seq>
+struct as_set :
+ mpl::fold<Seq,
+ mpl::set<>,
+ mpl::insert<mpl::_1, mpl::_2> >
+{};
+
+template<typename AssocSeq, typename Key, typename Default>
+struct at_or_default :
+ mpl::if_<typename mpl::has_key<AssocSeq, Key>::type,
+ typename mpl::at<AssocSeq, Key>::type,
+ Default>
+{};
+
+template<typename Seq1, typename Seq2>
+struct set_equal :
+ mpl::fold<Seq2,
+ mpl::true_,
+ mpl::and_<mpl::_1,
+ mpl::has_key<typename as_set<Seq1>::type,
+ mpl::_2 > > >
+{};
+
+}
+}
+}
+}
+
+#endif // BOOST_METAGRAPH_MPL_GRAPH_MPL_UTILS_HPP_INCLUDED
Added: sandbox/metagraph/libs/metagraph/example/adjacency_list_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/adjacency_list_graph.cpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -0,0 +1,78 @@
+// mplgraph.cpp : Defines the entry point for the console application.
+//
+
+#include <boost/metagraph/mpl_graph/adjacency_list_graph.hpp>
+#include <boost/metagraph/mpl_graph/mpl_utils.hpp>
+#include <boost/mpl/equal.hpp>
+
+
+namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl_utils = mpl_graph::mpl_utils;
+namespace mpl = boost::mpl;
+
+/*
+ test graph and tests are almost identical to incidence_list_graph.cpp
+ A -> B -> C -\--> D
+ \ |--> E
+ \ \--> F
+ \-----/
+ G // except this
+*/
+
+// vertices
+struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{};
+
+// edges
+struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
+
+typedef mpl::vector<
+ mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >,
+ mpl::pair<B, mpl::vector<mpl::pair<B_C, C>,
+ mpl::pair<B_F, F> > >,
+ mpl::pair<C, mpl::vector<mpl::pair<C_D, D>,
+ mpl::pair<C_E, E>,
+ mpl::pair<C_F, F> > >,
+ mpl::pair<G, mpl::vector<> > >
+ some_adjacency_list;
+typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_graph;
+
+BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::source<B_C,some_graph>::type, B> ));
+BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::source<C_D,some_graph>::type, C> ));
+
+BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::target<C_D,some_graph>::type, D> ));
+BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::target<B_F,some_graph>::type, F> ));
+
+
+// shouldn't assume the order but this seems to work
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::out_edges<C,some_graph>::type, mpl::vector<C_D,C_E,C_F> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::out_edges<B,some_graph>::type, mpl::vector<B_C,B_F> > ));
+
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::out_degree<B,some_graph>::value), ==, 2 );
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::out_degree<C,some_graph>::value), ==, 3 );
+
+
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::in_edges<C,some_graph>::type, mpl::vector<B_C> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::in_edges<F,some_graph>::type, mpl::vector<B_F,C_F> > ));
+
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::in_degree<A,some_graph>::value), ==, 0 );
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::in_degree<F,some_graph>::value), ==, 2 );
+
+
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::degree<A,some_graph>::value), ==, 1 );
+BOOST_MPL_ASSERT_RELATION( (mpl_graph::degree<C,some_graph>::value), ==, 4 );
+
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::adjacent_vertices<A,some_graph>::type, mpl::vector<B> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::adjacent_vertices<C,some_graph>::type, mpl::vector<D,E,F> > ));
+
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::vertices<some_graph>::type, mpl::vector<A,B,C,D,E,F,G> > ));
+
+BOOST_MPL_ASSERT_RELATION( mpl_graph::num_vertices<some_graph>::value, ==, 7 );
+
+BOOST_MPL_ASSERT_RELATION( mpl_graph::num_edges<some_graph>::value, ==, 6 );
+
+
+int main(int argc, char* argv[])
+{
+ return 0;
+}
+
Modified: sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp (original)
+++ sandbox/metagraph/libs/metagraph/example/depth_first_search.cpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -1,33 +1,60 @@
#include <boost/metagraph/mpl_graph/depth_first_search.hpp>
-#include <boost/mpl/print.hpp>
+#include <boost/metagraph/mpl_graph/adjacency_list_graph.hpp>
+#include <boost/metagraph/mpl_graph/incidence_list_graph.hpp>
#include <iostream>
namespace mpl_graph = boost::metagraph::mpl_graph;
namespace mpl = boost::mpl;
+// vertices
+struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{}; struct G{};
+
+// edges
+struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
+
+
+
/*
- test graph:
+ incidence list test graph:
A -> B -> C -\--> D
\ |--> E
\ \--> F
\-----/
+ G
*/
-// vertices
-struct A{}; struct B{}; struct C{}; struct D{}; struct E{}; struct F{};
-
-// edges
-struct A_B{}; struct B_C{}; struct C_D{}; struct C_E{}; struct C_F{}; struct B_F{};
-
typedef mpl::vector<mpl::vector<A_B,A,B>,
mpl::vector<B_C,B,C>,
mpl::vector<C_D,C,D>,
mpl::vector<C_E,C,E>,
mpl::vector<C_F,C,F>,
mpl::vector<B_F,B,F> >
- some_edge_sequence;
-typedef mpl_graph::edgeseq_graph<some_edge_sequence> some_graph;
+ some_incidence_list;
+typedef mpl_graph::incidence_list_graph<some_incidence_list> some_incidence_list_graph;
+
+
+
+/*
+ adjacency list test graph:
+ A -> B -> C -\--> D
+ \ |--> E
+ \ \--> F
+ \-----/
+ G
+*/
+
+typedef mpl::vector<
+ mpl::pair<A, mpl::vector<mpl::pair<A_B, B> > >,
+ mpl::pair<B, mpl::vector<mpl::pair<B_C, C>,
+ mpl::pair<B_F, F> > >,
+ mpl::pair<C, mpl::vector<mpl::pair<C_D, D>,
+ mpl::pair<C_E, E>,
+ mpl::pair<C_F, F> > >,
+ mpl::pair<G, mpl::vector<> > >
+ some_adjacency_list;
+typedef mpl_graph::adjacency_list_graph<some_adjacency_list> some_adjacency_list_graph;
+
struct preordering_visitor : mpl_graph::dfs_default_visitor_operations {
template<typename Node, typename Graph, typename State>
@@ -42,22 +69,41 @@
mpl::push_back<State, Node>
{};
};
+
+// adjacency list tests
+
+// preordering, default start node (first)
+typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_adj;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj::type, mpl::vector<A,B,C,D,E,F,G> > ));
+
+// postordering, default start node
+typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_adj;
+BOOST_MPL_ASSERT(( mpl::equal<postorder_adj::type, mpl::vector<D,E,F,C,B,A,G> > ));
+
+// preordering starting at C
+typedef mpl::first<mpl_graph::depth_first_search<some_adjacency_list_graph,
+ mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
+ C>::type>::type preorder_adj_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_adj_from_c::type, mpl::vector<C,D,E,F,A,B,G> > ));
+
+
+// incidence list tests
+
+// preordering, default start node (first)
+typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder_inc;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc::type, mpl::vector<A,B,C,D,E,F> > ));
+
+// postordering, default start node
+typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder_inc;
+BOOST_MPL_ASSERT(( mpl::equal<postorder_inc::type, mpl::vector<D,E,F,C,B,A> > ));
+
+// preordering starting at C
+typedef mpl::first<mpl_graph::depth_first_search<some_incidence_list_graph,
+ mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
+ C>::type>::type preorder_inc_from_c;
+BOOST_MPL_ASSERT(( mpl::equal<preorder_inc_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
-template<typename T> struct incomplete;
int main() {
- // preordering, default start node (first)
- typedef mpl::first<mpl_graph::depth_first_search<some_graph,mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor > >::type>::type preorder;
- BOOST_MPL_ASSERT(( mpl::equal<preorder::type, mpl::vector<A,B,C,D,E,F> > ));
-
- // postordering, default start node
- typedef mpl::first<mpl_graph::depth_first_search<some_graph,mpl_graph::state_and_operations<mpl::vector<>, postordering_visitor > >::type>::type postorder;
- BOOST_MPL_ASSERT(( mpl::equal<postorder::type, mpl::vector<D,E,F,C,B,A> > ));
-
- // preordering starting at C
- typedef mpl::first<mpl_graph::depth_first_search<some_graph,
- mpl_graph::state_and_operations<mpl::vector<>, preordering_visitor >,
- C>::type>::type preorder_from_c;
- BOOST_MPL_ASSERT(( mpl::equal<preorder_from_c::type, mpl::vector<C,D,E,F,A,B> > ));
return 0;
}
\ No newline at end of file
Modified: sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp (original)
+++ sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -1,5 +1,5 @@
#include <boost/metagraph/fusion_graph/fusion_graph.hpp>
-#include <boost/mpl/print.hpp>
+#include <boost/metagraph/mpl_graph/incidence_list_graph.hpp>
namespace fusion_graph = boost::metagraph::fusion_graph;
namespace fusion = boost::fusion;
@@ -27,7 +27,7 @@
>
{};
struct graph_desc_graph :
- mpl_graph::edgeseq_graph<graph_desc>
+ mpl_graph::incidence_list_graph<graph_desc>
{};
typedef fusion_graph::make_fusion_graph<graph_desc_graph>::type graphy;
@@ -36,8 +36,6 @@
typedef graphy::vertex_impl<N>::type Node;
typedef graphy::vertex_impl<E>::type Edge;
-mpl::print<Graph>::type foo;
-
int main(int narg, char *args[]) {
Graph *g = new Graph;
Node *n1 = new Node, *n2 = new Node;
Modified: sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp
==============================================================================
--- sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp (original)
+++ sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp 2008-09-21 00:27:27 EDT (Sun, 21 Sep 2008)
@@ -1,10 +1,11 @@
// mplgraph.cpp : Defines the entry point for the console application.
//
-#include <boost/metagraph/mpl_graph/mpl_graph.hpp>
-#include <boost/mpl/print.hpp>
+#include <boost/metagraph/mpl_graph/incidence_list_graph.hpp>
+#include <boost/metagraph/mpl_graph/mpl_utils.hpp>
namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl_utils = mpl_graph::mpl_utils;
namespace mpl = boost::mpl;
/*
test graph:
@@ -26,8 +27,8 @@
mpl::vector<C_E,C,E>,
mpl::vector<C_F,C,F>,
mpl::vector<B_F,B,F> >
- some_edge_sequence;
-typedef mpl_graph::edgeseq_graph<some_edge_sequence> some_graph;
+ some_incidence_list;
+typedef mpl_graph::incidence_list_graph<some_incidence_list> some_graph;
BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::source<B_C,some_graph>::type, B> ));
BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::source<C_D,some_graph>::type, C> ));
@@ -35,27 +36,25 @@
BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::target<C_D,some_graph>::type, D> ));
BOOST_MPL_ASSERT(( boost::is_same<mpl_graph::target<B_F,some_graph>::type, F> ));
-// shouldn't assume the order but this seems to work
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::out_edges<C,some_graph>::type, mpl::vector<C_D,C_E,C_F> > ));
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::out_edges<B,some_graph>::type, mpl::vector<B_C,B_F> > ));
-
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::in_edges<C,some_graph>::type, mpl::vector<B_C> > ));
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::in_edges<F,some_graph>::type, mpl::vector<C_F,B_F> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::out_edges<C,some_graph>::type, mpl::vector<C_D,C_E,C_F> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::out_edges<B,some_graph>::type, mpl::vector<B_F,B_C> > ));
BOOST_MPL_ASSERT_RELATION( (mpl_graph::out_degree<B,some_graph>::value), ==, 2 );
BOOST_MPL_ASSERT_RELATION( (mpl_graph::out_degree<C,some_graph>::value), ==, 3 );
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::in_edges<C,some_graph>::type, mpl::vector<B_C> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::in_edges<F,some_graph>::type, mpl::vector<C_F,B_F> > ));
+
BOOST_MPL_ASSERT_RELATION( (mpl_graph::in_degree<A,some_graph>::value), ==, 0 );
BOOST_MPL_ASSERT_RELATION( (mpl_graph::in_degree<F,some_graph>::value), ==, 2 );
BOOST_MPL_ASSERT_RELATION( (mpl_graph::degree<A,some_graph>::value), ==, 1 );
BOOST_MPL_ASSERT_RELATION( (mpl_graph::degree<C,some_graph>::value), ==, 4 );
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::adjacent_vertices<A,some_graph>::type, mpl::vector<B> > ));
-BOOST_MPL_ASSERT(( mpl::equal<mpl_graph::adjacent_vertices<C,some_graph>::type, mpl::vector<D,E,F> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::adjacent_vertices<A,some_graph>::type, mpl::vector<B> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::adjacent_vertices<C,some_graph>::type, mpl::vector<D,E,F> > ));
-// this doesn't work because equal is ordered
-//BOOST_MPL_ASSERT(( equal<mpl_graph::vertices<some_graph>::type, set<A,B,C,D,E,F> > ));
+BOOST_MPL_ASSERT(( mpl_utils::set_equal<mpl_graph::vertices<some_graph>::type, mpl::vector<A,B,C,D,E,F> > ));
BOOST_MPL_ASSERT_RELATION( mpl_graph::num_vertices<some_graph>::value, ==, 6 );
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk