[Boost-commit] svn:boost r46772 - in sandbox/SOC/2008/graphs/branches: decoup iu/libs/graphs placeholder placeholder/boost/graphs placeholder/libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-27 10:28:31

Author: asutton
Date: 2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
New Revision: 46772
URL: http://svn.boost.org/trac/boost/changeset/46772

Log:
Experimenting with placeholders.

Added:
   sandbox/SOC/2008/graphs/branches/decoup/
   sandbox/SOC/2008/graphs/branches/decoup/Jamfile   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/decoup/Jamroot   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/decoup/README   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/decoup/decoup.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/decoup/demangle.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/placeholder/
      - copied from r46767, /sandbox/SOC/2008/graphs/trunk/
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/descriptor.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/directed_graph.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/directed_vertex.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/incidence_iterator.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/property_vector.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/undirected_graph.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/vertex_descriptor.hpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
   sandbox/SOC/2008/graphs/branches/placeholder/libs/graphs/un.cpp
      - copied unchanged from r46769, /sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
Text files modified: 
   sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp                    |   169 ++++++++++++++++++++++++++++++++++++++- 
   sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/placeholder.hpp |     2                                         
   2 files changed, 164 insertions(+), 7 deletions(-)

Added: sandbox/SOC/2008/graphs/branches/decoup/Jamfile
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/decoup/Jamfile	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -0,0 +1,2 @@
+
+exe decoup : decoup.cpp : <include>../../trunk ;

Added: sandbox/SOC/2008/graphs/branches/decoup/Jamroot
==============================================================================

Added: sandbox/SOC/2008/graphs/branches/decoup/README
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/decoup/README	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -0,0 +1,38 @@
+
+The decoup "library" is simply an attempt to see if it's possible
+to completely decouple the layout of objects from their types and
+then "re-imbue" them with their interfaces at a later stage. The
+reason for doing so is to basically lay out the structure of a
+number of interdependent types (like those in the graph library).
+
+There are two parts of this problem to think about. The first, sometimes
+referred to as "mutually dependent types" is actually fairly trivial to resolve.
+Basically, we have two types that depend on eachother, with one generally being
+a pointer or a reference. If these types are not templates, you have to be
+careful about the ordering of functions that actually "realize" the depenency
+so that the types are completed before the realization. An interesting solution
+is to move the types into templates, which defers the realization until the
+templates are instantiated - pretty cool.
+
+The second, and much harder part of this problems is the definition of mutually
+dependend incomplete types (which usually involves a trio of types). Consider
+
+template <typename VertexDescriptor>
+struct vertex
+{
+    IncidenceStore<vertex_descriptor> edges;
+}
+
+typedef VertexStore<vertex<...> > vertex_store;
+typedef Descriptor<vertex_store> vertex_descriptor;
+
+Seems inocuous enough... The problem here is that the vertex store needs a
+complete vertex type in order to generate the store, and that generates the
+vertex decriptor. Unfortunately, we're too late because the vertex needs the
+descriptor type.
+
+Normally, if any of the types involved here are concrete (i.e., known), then
+the problem can generally be unwrapped. However, if all types are paramterized,
+then the solution isn't quite as easy. Basically, we have to rely on the fact
+that these containers are all fixed sizes regardless of the whatever they might
+store.
\ No newline at end of file

Added: sandbox/SOC/2008/graphs/branches/decoup/decoup.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/decoup/decoup.cpp	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -0,0 +1,60 @@
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <list>
+#include <set>
+#include <map>
+#include <tr1/unordered_set>
+#include <tr1/unordered_map>
+
+#include <boost/graphs/placeholder.hpp>
+#include <boost/graphs/descriptor.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+using namespace std::tr1;
+
+template <typename Properties, typename IncidenceStore>
+struct vertex
+{
+    vertex(Properties const& p)
+        : props(p), edges()
+    { }
+
+    Properties      props;
+    IncidenceStore  edges;
+};
+
+typedef double T;
+
+// Generate the underlying storage types for a vertex (its slot). This will
+// be used as the basic block of memory passed to the vertex store.
+typedef vector<int> dummy_store;
+typedef vertex<T, dummy_store> dummy_vertex;
+typedef placeholder<sizeof(dummy_vertex)> vertex_slot;
+
+// Create the vertex store and use that to generate descriptors.
+typedef vector<vertex_slot> vertex_store;
+typedef descriptor<vertex_store> vertex_descriptor;
+
+// We can now use the vertex descriptor to generate the incidence store
+typedef vector<vertex_descriptor> incidence_store;
+
+// Now, we can generate the full vertex type.
+typedef vertex<T, incidence_store> vertex_type;
+
+int main()
+{
+    // Make sure that these are the correct sizes.
+    BOOST_ASSERT(sizeof(vertex_type) == sizeof(vertex_slot));
+
+    vertex_store verts;
+    verts.push_back(vertex_type(3.14));
+
+    vertex_type& v = verts.back().get<vertex_type>();
+    cout << v.props << endl;
+
+    return 0;
+}

Added: sandbox/SOC/2008/graphs/branches/decoup/demangle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/decoup/demangle.hpp	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -0,0 +1,22 @@
+
+#ifndef DEMANGLE_HPP
+#define DEMANGLE_HPP
+
+#include <string>
+#include <typeinfo>
+#include <cxxabi.h>
+
+inline std::string
+demangle(std::string const& name)
+{
+    return std::string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+}
+
+template <typename T>
+inline std::string
+demangle()
+{
+    return demangle(typeid(T).name());
+}
+
+#endif

Modified: sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -56,7 +56,7 @@
 }
 
 template <typename Graph>
-void test_make_simple_triangle()
+void test_add_edges()
 {
     Graph g;
     vector<typename Graph::vertex_descriptor> V;
@@ -70,6 +70,143 @@
     BOOST_ASSERT(g.num_edges() == 3);
 }
 
+template <typename Graph>
+void test_add_remove_edges()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    E.push_back(g.add_edge(V[0], V[1]));
+    E.push_back(g.add_edge(V[1], V[2]));
+    E.push_back(g.add_edge(V[2], V[0]));
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 1);
+    E.pop_front();
+
+    g.remove_edge(E.front());
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    E.pop_front();
+}
+
+template <typename Graph>
+void test_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.disconnect_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.degree(V[1]) == 0);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+// This is a little different than above. We remove a vertex from the triangle,
+// which implicitly disconnects it.
+template <typename Graph>
+void test_implicit_disconnect_vertex()
+{
+    Graph g;
+    vector<typename Graph::vertex_descriptor> V;
+    list<typename Graph::edge_descriptor> E;
+    for(int i = 0; i < 3; ++i) {
+        V.push_back(g.add_vertex(i));
+    }
+    g.add_edge(V[0], V[1]);
+    g.add_edge(V[1], V[2]);
+    g.add_edge(V[2], V[0]);
+    BOOST_ASSERT(g.num_vertices() == 3);
+    BOOST_ASSERT(g.num_edges() == 3);
+
+    g.remove_vertex(V[1]);
+    BOOST_ASSERT(g.num_vertices() == 2);
+    BOOST_ASSERT(g.degree(V[0]) == 1);
+    BOOST_ASSERT(g.degree(V[2]) == 1);
+}
+
+template <typename Graph>
+void test_add_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    BOOST_ASSERT(g.num_vertices() == 2);
+    if(is_simple_graph(g)) {
+        BOOST_ASSERT(g.num_edges() == 1);
+    }
+    else {
+        BOOST_ASSERT(g.num_edges() == 4);
+    }
+}
+
+template <typename Graph>
+void test_remove_multi_edges()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+    g.add_edge(u, v);
+    g.add_edge(v, u);
+
+    g.remove_edges(u, v);
+    BOOST_ASSERT(g.num_edges() == 0);
+}
+
+template <typename Graph>
+void test_incidence_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::incident_edge_range x = g.incident_edges(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
+
+template <typename Graph>
+void test_adjacency_iterator()
+{
+    Graph g;
+    typename Graph::vertex_descriptor u = g.add_vertex(1);
+    typename Graph::vertex_descriptor v = g.add_vertex(2);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, u, 2);
+    g.add_edge(u, v, 3);
+    g.add_edge(v, u, 4);
+
+    typename Graph::adjacent_vertex_range x = g.adjacent_vertices(v);
+    for( ; x.first != x.second; ++x.first) {
+        // cout << "test: " << g[*x.first] << endl;
+    }
+}
 
 int main()
 {
@@ -82,25 +219,45 @@
 
 void vec_vec()
 {
+    cout << "---- vec/vec ----" << endl;
     typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
     test_add_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_edges<Graph>();
+    test_add_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
+
+    Graph g;
+    g.add_vertex();
+    Graph::edge_iterator i(&g);
 }
 
 void list_list()
 {
+    cout << "---- list/list ----" << endl;
     typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
-
-    Graph g;
     test_add_remove_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
 }
 
 
 void set_set()
 {
+    cout << "---- set/set ----" << endl;
     typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
     test_add_remove_vertices<Graph>();
-    test_make_simple_triangle<Graph>();
+    test_add_remove_edges<Graph>();
+    test_disconnect_vertex<Graph>();
+    test_implicit_disconnect_vertex<Graph>();
+    test_add_multi_edges<Graph>();
+    test_remove_multi_edges<Graph>();
+    test_incidence_iterator<Graph>();
+    test_adjacency_iterator<Graph>();
 }
 

Modified: sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/placeholder.hpp
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/placeholder/boost/graphs/placeholder.hpp	2008-06-27 10:28:31 EDT (Fri, 27 Jun 2008)
@@ -42,7 +42,7 @@
 
     /** Get the value of the placeholder and return it as an object of type T. */
     template <typename T>
-    inline T get() const
+    inline T& get() const
     {
         BOOST_STATIC_ASSERT(sizeof(T) == N);
         return *reinterpret_cast<T*>(mem);