[Boost-commit] svn:boost r44788 - in sandbox/metagraph: . boost boost/metagraph libs libs/metagraph libs/metagraph/example

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;
+}
+