From: gordon_at_[hidden]
Date: 2008-04-26 17:46:50
Author: gordon.woodhull
Date: 2008-04-26 17:46:49 EDT (Sat, 26 Apr 2008)
New Revision: 44788
URL: http://svn.boost.org/trac/boost/changeset/44788
Log:
initial checkin of metagraph libraries
Added:
sandbox/metagraph/
sandbox/metagraph/boost/
sandbox/metagraph/boost/metagraph/
sandbox/metagraph/boost/metagraph/fusion_graph.h (contents, props changed)
sandbox/metagraph/boost/metagraph/mpl_graph.h (contents, props changed)
sandbox/metagraph/libs/
sandbox/metagraph/libs/metagraph/
sandbox/metagraph/libs/metagraph/example/
sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp (contents, props changed)
sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp (contents, props changed)
Added: sandbox/metagraph/boost/metagraph/fusion_graph.h
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/fusion_graph.h 2008-04-26 17:46:49 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,106 @@
+// fusion_graph - a heterogeneous typed graph data structure
+
+// (c) 2008 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSEmpl::_1_0.txt or copy at
+// http://www.boost.org/LICENSEmpl::_1_0.txt)
+
+#include "mpl_graph.h"
+
+#include <boost/fusion/include/map.hpp>
+#include <boost/fusion/include/pair.hpp>
+#include <boost/fusion/include/insert.hpp>
+#include <boost/fusion/include/as_map.hpp>
+#include <boost/fusion/include/mpl.hpp>
+#include <boost/fusion/include/at_key.hpp>
+
+#include <list>
+
+
+namespace boost {
+namespace metagraph {
+namespace fusion_graph {
+
+// input: an mpl_graph of vertex-types and edge-relations annotated with
+// instructions on the web of types-that-refer-to-each-other to generate
+
+// note a fusion_graph's nodes and edges are all different types, although
+// there may be many instances of a particular type. as a particular example,
+// one might specify a minimal graph adt as a fusion_graph of three types G, N, and E
+// G -> N <-> E "A graph contains containers of pointers to nodes, which contain
+// containers of pointers to edges, which contain pointers to nodes."
+
+// output: a type generator for the requested interlinked types - look up
+// the implementation using tags of input graph with fig::vertex_impl<vertex_tag>::type
+// or fig::edge_impl<edge_tag>::type. note edge data is all stored in source nodes
+// and accessed using fig::access_edge<edge_tag>(vertex)
+
+// this should all be abstracted better (another level is planned), but here's a start
+template<typename InputGraph>
+struct make_fusion_graph {
+ struct type { //?
+ template<typename VertexTag> struct vertex_impl;
+ template<typename EdgeTag>
+ struct edge_impl {
+ struct type {
+ typedef typename vertex_impl<typename mpl_graph::target<EdgeTag,InputGraph>::type>::type target_type;
+ typedef typename EdgeTag::template link_container<target_type>::type link_type;
+
+ link_type link;
+ typename EdgeTag::data_type data;
+ };
+ };
+
+ template<typename VertexTag>
+ struct vertex_impl {
+ struct type {
+ typedef typename mpl::transform<typename mpl_graph::out_edges<VertexTag,InputGraph>::type,
+ fusion::pair<mpl::_1,
+ edge_impl<mpl::_1> >
+ >::type tag_n_impl_sequence;
+ typedef typename VertexTag::template edges_container<tag_n_impl_sequence>::type
+ edges_type;
+ edges_type edges;
+ typename VertexTag::data_type data;
+ };
+ };
+ };
+};
+
+// some vertex and edge data specification classes
+
+// tells fusion_graph to use a fusion::map to keep track of edges in a vertex
+template<typename Data>
+struct mapper_vertex {
+ typedef Data data_type;
+ template<typename EdgeTagImplVec>
+ struct edges_container :
+ boost::fusion::result_of::as_map<EdgeTagImplVec>
+ {};
+};
+
+// tells fusion_graph to use a pointer to store zero/one link in edge
+template<typename Data>
+struct ptr_edge {
+ typedef Data data_type;
+ template<typename VertexImpl>
+ struct link_container {
+ typedef VertexImpl* type;
+ };
+};
+// tells fusion_graph to use a list to store zero or more links in edge
+template<typename Data>
+struct ptr_list_edge {
+ typedef Data data_type;
+ template<typename VertexImpl>
+ struct link_container {
+ typedef std::list<VertexImpl*> type;
+ };
+};
+// etc. special provision will be made for intrusive containers and their
+// magical polymorphic qualities in the next level...
+
+
+} // fusion_graph
+} // metagraoh
+} // boost
Added: sandbox/metagraph/boost/metagraph/mpl_graph.h
==============================================================================
--- (empty file)
+++ sandbox/metagraph/boost/metagraph/mpl_graph.h 2008-04-26 17:46:49 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,205 @@
+// mpl_graph - defines a metadata implementation of the BGL immutable graph concepts
+
+// (c) 2008 Gordon Woodhull
+// Distributed under the Boost Software License, Version 1.0.
+// (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
+
+#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 {
+
+// 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
+
+// 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> {};
+
+ // S->E->T map for out_*, adjacent_vertices
+ /*
+ // 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.
+ template<typename EdgeSeqGraph>
+ struct produce_outs_map :
+
+ fold<typename EdgeSeqGraph::est_sequence,
+ map<>,
+ if_<has_key<mpl::_1,fetch_source<mpl::_2> >,
+ insert<erase_key<mpl::_1,fetch_source<mpl::_2> >,
+ pair<fetch_source<mpl::_2>,
+ insert<at<mpl::_1,fetch_source<mpl::_2> >,
+ pair<fetch_edge<mpl::_2>, fetch_target<mpl::_2> > > > >,
+ insert<mpl::_1,pair<fetch_source<mpl::_2>,
+ map<pair<fetch_edge<mpl::_2>,fetch_target<mpl::_2> > > > >
+ > >
+ {};
+ */
+ // 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> > > >
+ {};
+ // 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> > >
+ {};
+}
+
+// Boost Graph concepts, MPL style
+
+// IncidenceGraph
+template<typename E, typename G>
+struct source :
+ mpl::first<typename mpl::at<typename detail::produce_edge_st_map<G>::type,E>::type>
+{};
+template<typename E, typename G>
+struct target :
+ mpl::second<typename mpl::at<typename detail::produce_edge_st_map<G>::type,E>::type>
+{};
+template<typename U, typename G>
+struct out_edges :
+ mpl::fold<typename detail::produce_out_map<U,G>::type,
+ mpl::vector<>,
+ mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
+{};
+template<typename U, typename G>
+struct out_degree :
+ mpl::size<typename out_edges<U,G>::type>
+{};
+
+// BidirectionalGraph
+template<typename V, typename G>
+struct in_edges :
+ mpl::fold<typename detail::produce_in_map<V,G>::type,
+ mpl::vector<>,
+ mpl::push_back<mpl::_1, mpl::first<mpl::_2> > >
+{};
+template<typename V, typename G>
+struct in_degree :
+ mpl::size<typename in_edges<V,G>::type>
+{};
+template<typename V, typename G>
+struct degree :
+ mpl::plus<typename out_degree<V,G>::type,typename in_degree<V,G>::type>
+{};
+
+// AdjacencyGraph
+template<typename V, typename G>
+struct adjacent_vertices :
+ mpl::transform<typename detail::produce_out_map<V,G>::type,
+ mpl::second<mpl::_1>,
+ mpl::back_inserter<mpl::vector<> > >
+{};
+
+// VertexListGraph
+template<typename G>
+struct vertices :
+ detail::produce_vertex_set<G>
+{};
+template<typename G>
+struct num_vertices :
+ mpl::size<typename vertices<G>::type>
+{};
+
+// EdgeListGraph
+template<typename G>
+struct edges :
+ detail::produce_edge_set<G>
+{};
+template<typename G>
+struct num_edges :
+ mpl::size<typename edges<G>::type>
+{};
+// source and target are defined in IncidenceGraph
+
+} // mplgraph
+} // metagraph
+} // boost
+
+#endif // BOOST_MPLGRAPH_H
Added: sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/fusion_graph.cpp 2008-04-26 17:46:49 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,53 @@
+#include <boost/metagraph/fusion_graph.h>
+#include <boost/mpl/print.hpp>
+
+namespace fusion_graph = boost::metagraph::fusion_graph;
+namespace fusion = boost::fusion;
+namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl = boost::mpl;
+
+struct G : fusion_graph::mapper_vertex<int> {};
+struct N : fusion_graph::mapper_vertex<int> {};
+struct E : fusion_graph::mapper_vertex<int> {};
+
+struct G_N : fusion_graph::ptr_list_edge<int> {};
+struct N_E : fusion_graph::ptr_list_edge<int> {};
+struct E_N : fusion_graph::ptr_edge<int> {};
+struct E_T : E_N {};
+struct E_S : E_N {};
+
+struct graph_desc :
+ mpl::vector<
+ mpl::vector<G_N,G,N>,
+ mpl::vector<N_E,N,E>,
+ mpl::vector<E_T,E,N>,
+ mpl::vector<E_S,E,N>
+ >
+{};
+struct graph_desc_graph :
+ mpl_graph::edgeseq_graph<graph_desc>
+{};
+
+typedef fusion_graph::make_fusion_graph<graph_desc_graph>::type graphy;
+
+typedef graphy::vertex_impl<G>::type Graph;
+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;
+ Edge *e1 = new Edge;
+
+ fusion::at_key<G_N>(g->edges).link.push_back(n1);
+ fusion::at_key<G_N>(g->edges).link.push_back(n2);
+ fusion::at_key<N_E>(n1->edges).link.push_back(e1);
+ fusion::at_key<E_S>(e1->edges).link = n1;
+ fusion::at_key<E_T>(e1->edges).link = n2;
+
+ // NO (generates horribly incomprehensible messages
+ //fusion::at_key<N_E>(g->edges).link.push_back(n1);
+
+}
\ No newline at end of file
Added: sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp
==============================================================================
--- (empty file)
+++ sandbox/metagraph/libs/metagraph/example/mpl_graph.cpp 2008-04-26 17:46:49 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,69 @@
+// mplgraph.cpp : Defines the entry point for the console application.
+//
+
+#include <boost/metagraph/mpl_graph.h>
+#include <boost/mpl/print.hpp>
+
+namespace mpl_graph = boost::metagraph::mpl_graph;
+namespace mpl = boost::mpl;
+/* can't at the moment think of a cute graph example so the following abstract
+ and poorly drawn
+ A -> B -> C -\--> D
+ \ |--> E
+ \ \--> F
+ \-----/
+*/
+
+// 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;
+
+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::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_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_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> > ));
+
+// 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_RELATION( mpl_graph::num_vertices<some_graph>::value, ==, 6 );
+
+BOOST_MPL_ASSERT_RELATION( mpl_graph::num_edges<some_graph>::value, ==, 6 );
+
+
+int main(int argc, char* argv[])
+{
+ return 0;
+}
+