[Boost-commit] svn:boost r47111 - in sandbox/SOC/2008/graphs/trunk: boost boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-07-05 10:03:41

Author: asutton
Date: 2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
New Revision: 47111
URL: http://svn.boost.org/trac/boost/changeset/47111

Log:
Started rewriting vertex store implementations to use the new container and
descriptor libraries.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/containers.hpp              |    30 ++++-                                   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp |     2                                         
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp      |   196 ++++++++++++--------------------------- 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp    |   116 +++++++++--------------                 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile               |    26 +++-                                    
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp              |    69 +++++++++----                           
   6 files changed, 197 insertions(+), 242 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/containers.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/containers.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/containers.hpp	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -212,22 +212,34 @@
 
 namespace dispatch
 {
-    template <typename Container, typename Value>
+    // Insert implementations
+    template <typename Container, typename T>
     inline typename Container::iterator
-    insert(Container& c, Value const& x, sequence_tag)
+    insert(Container& c, T const& x, sequence_tag)
     { return c.insert(c.end(), x); }
 
-    template <typename Container, typename Value>
+    template <typename Container, typename T>
     inline typename Container::iterator
-    insert(Container& c, Value const& x, unique_associative_container_tag)
+    insert(Container& c, T const& x, unique_associative_container_tag)
     { return c.insert(x).first; }
 
-    template <typename Container, typename Value>
+    template <typename Container, typename T>
     inline typename Container::iterator
-    insert(Container& c, Value const& x, multiple_associative_container_tag)
+    insert(Container& c, T const& x, multiple_associative_container_tag)
     { return c.insert(x); }
 
+    // Find (non-const) implementations
+    template <typename Container, typename T>
+    inline typename Container::iterator
+    find(Container& c, T const& x, sequence_tag)
+    { return std::find(c.begin(), c.end(), x); }
+
+    template <typename Container, typename T>
+    inline typename Container::iterator
+    find(Container& c, T const& x, associative_container_tag)
+    { return c.find(x); }
 
+    // Erase implementations
     template <typename Container>
     inline typename Container::iterator
     erase(Container& c, typename Container::iterator i, sequence_tag)
@@ -250,7 +262,13 @@
 
 template <typename Container, typename T>
 inline typename Container::iterator
+find(Container& c, T const& x)
+{ return dispatch::find(c, x, container_category(c)); }
+
+template <typename Container>
+inline typename Container::iterator
 erase(Container& c, typename Container::iterator i)
 { return dispatch::erase(c, i, container_category(c)); }
 
+
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -2,7 +2,7 @@
 #ifndef UNDIRECTED_GRAPH_HPP
 #define UNDIRECTED_GRAPH_HPP
 
-#include "none.hpp"
+#include <boost/none.hpp>
 
 #include "undirected_vertex.hpp"
 #include "vertex_vector.hpp"

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -4,7 +4,8 @@
 
 #include <list>
 
-#include "vertex_descriptor.hpp"
+#include <boost/descriptors.hpp>
+
 #include "vertex_iterator.hpp"
 
 // Forward declarations
@@ -12,49 +13,24 @@
 template <typename V, typename A> class vertex_list_impl;
 
 /**
- * This metafunctiopn defines the basic elements of a vertex list.
- *
- * FIXME: We can probably rebuild the descriptor as an iterator into the
- * underlying store by defining it as a buffer the same size as a fake store
- * iterator and then re-casting the buffered data as an iterator whenever we
- * need it. That's a bit hacky, but it gets rid of redundant storage.
+ * This metafunction defines the basic elements of a vertex list.
  */
-template <template <typename> class Allocator = std::allocator>
+template <template <typename> class Alloc = std::allocator>
 struct vertex_list
 {
     typedef unused key_type;
-    typedef basic_vertex_descriptor<void*> descriptor_type;
+
+    typedef std::list<int, Alloc<int>> dummy;
+    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
 
     template <typename Vertex>
     struct store
     {
-        typedef vertex_list_elem<Vertex, Allocator> stored_vertex;
-        typedef Allocator<stored_vertex> allocator_type;
-        typedef vertex_list_impl<stored_vertex, allocator_type > type;
+        typedef vertex_list_impl<Vertex, Alloc<Vertex>> type;
     };
 };
 
 /**
- * Pad the vertex type with an iterator back into the list. See above for a
- * way around this.
- */
-template <typename Vertex, template <typename> class Alloc>
-class vertex_list_elem
-    : public Vertex
-{
-    typedef vertex_list_elem<Vertex, Alloc> this_type;
-public:
-    typedef typename std::list<this_type, Alloc<this_type> >::iterator iterator;
-
-    inline vertex_list_elem(typename Vertex::vertex_properties const& vp)
-        : Vertex(vp)
-        , iter()
-    { }
-
-    iterator iter;
-};
-
-/**
  * The implementation of the vertex list.
  *
  * @param Vertex The type of stored vertex.
@@ -63,31 +39,65 @@
 template <typename Vertex, typename Alloc>
 class vertex_list_impl
 {
-    typedef std::list<Vertex, Alloc> vertex_store;
 public:
-    typedef basic_vertex_descriptor<void*> vertex_descriptor;
+    typedef std::list<Vertex, Alloc> store_type;
+    typedef typename store_type::size_type size_type;
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
-    typedef typename vertex_store::size_type size_type;
-    typedef typename vertex_store::iterator iterator;
-    typedef typename vertex_store::const_iterator const_iterator;
 
-    typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
+
+    typedef simple_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors
-    vertex_list_impl();
+    inline vertex_list_impl()
+        : _verts(), _size(0)
+    { }
 
-    // Add/remove vertices.
-    vertex_descriptor add();
-    vertex_descriptor add(vertex_properties const& vp);
-    vertex_descriptor find(vertex_properties const& vp);
-    void remove(vertex_descriptor v);
-    void remove(vertex_properties const& vp);
+    /** @name Add Vertex
+     * Add a vertex to the store with the given properties (or none). Return
+     * a descriptor to the vertex that was added to the vector.
+     */
+    //@{
+    inline vertex_descriptor add()
+    { return add(vertex_properties()); }
+
+    inline vertex_descriptor add(vertex_properties const& vp)
+    {
+        ++_size;
+        iterator i = insert(_verts, vertex_type(vp));
+        return make_descriptor(_verts, i);
+    }
+    //@}
+
+    /** Find the vertex with the given properties. */
+    inline vertex_descriptor find(vertex_properties const& vp)
+    {
+        iterator i = std::find_if(_verts.begin(), _verts.end(), find_properties(vp));
+        return make_descriptor(_verts, i);
+    }
+
+    /** @name Remove Vertex
+     * Remove the given vertex from the vertex store. This will probably break
+     * if the descriptor is invalid.
+     */
+    //@{
+    inline void remove(vertex_descriptor v)
+    {
+        _verts.erase(make_iterator(_verts, v));
+        --_size;
+    }
+
+    inline void remove(vertex_properties const& vp)
+    { remove(find(vp)); }
+    //@}
 
     /** Return the number of vertices in the set. */
-    size_type size() const
+    inline size_type size() const
     { return _size; }
 
     /** @name Vertex Iterators */
@@ -105,10 +115,10 @@
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return *static_cast<vertex_type*>(v.get()); }
+    { return *make_iterator(_verts, v); }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return *static_cast<vertex_type*>(v.get()); }
+    { return *make_iterator(_verts, v); }
     //@}
 
     /** @name Vertex Properties */
@@ -121,96 +131,10 @@
     //@}
 
 private:
-    vertex_store _verts;
-    size_type _size;
+    store_type  _verts;
+    size_type   _size;
 };
 
-#define BOOST_GRAPH_VL_PARAMS \
-    typename V, typename A
-
-/**
- * Construct an empty vertex list.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-vertex_list_impl<V,A>::vertex_list_impl()
-    : _verts()
-    , _size(0)
-{ }
-
-/**
- * Add a vertex to the list with no or default properties.
- *
- * @complexity O(1)
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_descriptor
-vertex_list_impl<V,A>::add()
-{
-    return add(vertex_properties());
-}
-
-/**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties. Note that vertices are not mapped
- * or ordered so multiple, equivalent vertices can be added to the graph.
- * This adds the vertex to the end of the list.
- *
- * @complexity O(1)
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_descriptor
-vertex_list_impl<V,A>::add(vertex_properties const& vp)
-{
-    ++_size;
-    iterator i = _verts.insert(_verts.end(), vertex_type(vp));
-    i->iter = i;
-    return &(*i);
-}
-
-/**
- * Find the vertex with the given properties. If there are multiple vertices
- * with the given properties, only the first is returned.
- *
- * @complexity O(V)
- * @requires EqualityComparable<VertexProps>
- */
-template <typename V, typename A>
-typename vertex_list_impl<V,A>::vertex_descriptor
-vertex_list_impl<V,A>::find(vertex_properties const& vp)
-{
-    return &const_cast<vertex_type&>(*std::find(_verts.begin(), _verts.end(), vp));
-}
-
-/**
- * Remove a vertex from the set. Removing a vertex will invalidate all vertex
- * descriptors and iterators to the removed vertex.
- *
- * @complexity O(1)
- */
-template <BOOST_GRAPH_VL_PARAMS>
-void
-vertex_list_impl<V,A>::remove(vertex_descriptor v)
-{
-    --_size;
-    vertex_type* vp = static_cast<vertex_type*>(v.get());
-    _verts.erase(vp->iter);
-}
-
-/**
- * Remove the vertex with the given properties from the list. This searches
- * the list for the first element with the given vertex and erases it. If there
- * are multiple elements with these properties, only the first is removed.
- *
- * @complexity O(V)
- */
-template <typename V, typename A>
-void
-vertex_list_impl<V,A>::remove(vertex_properties const& vp)
-{
-    remove(find(vp));
-}
-
-#undef BOOST_GRAPH_VL_PARAMS
 
 #endif
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -5,7 +5,9 @@
 #include <vector>
 #include <algorithm>
 
-#include "vertex_descriptor.hpp"
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
+
 #include "vertex_iterator.hpp"
 
 // Forward declarations
@@ -25,7 +27,9 @@
 struct vertex_vector
 {
     typedef unused key_type;
-    typedef basic_vertex_descriptor<std::size_t> descriptor_type;
+
+    typedef std::vector<int, Alloc<int>> dummy;
+    typedef typename descriptor_traits<dummy>::descriptor_type descriptor_type;
 
     // The store metafunction generates the type used to store vertices in
     // either a directed or undirected graph. This metafunction takes the
@@ -33,9 +37,7 @@
     template <typename Vertex>
     struct store
     {
-        typedef Vertex stored_vertex;
-        typedef Alloc<stored_vertex> allocator;
-        typedef vertex_vector_impl<stored_vertex, allocator> type;
+        typedef vertex_vector_impl<Vertex, Alloc<Vertex>> type;
     };
 };
 
@@ -53,35 +55,55 @@
 template <typename Vertex, typename Allocator>
 class vertex_vector_impl
 {
-    typedef std::vector<Vertex, Allocator> vertex_store;
 public:
-    typedef basic_vertex_descriptor<std::size_t> vertex_descriptor;
+    typedef std::vector<Vertex, Allocator> store_type;
+    typedef typename store_type::size_type size_type;
+    typedef typename store_type::iterator iterator;
+    typedef typename store_type::const_iterator const_iterator;
 
     typedef Vertex vertex_type;
     typedef typename Vertex::vertex_properties vertex_properties;
-    typedef typename vertex_store::size_type size_type;
-    typedef typename vertex_store::iterator iterator;
-    typedef typename vertex_store::const_iterator const_iterator;
 
-    typedef indexed_vertex_iterator<vertex_store> vertex_iterator;
+    typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
+
+    typedef indexed_vertex_iterator<store_type> vertex_iterator;
     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
 
     // Constructors
-    vertex_vector_impl();
-
-    /** @name Add Vertex */
+    inline vertex_vector_impl()
+        : _verts()
+    { }
+
+    /** @name Add Vertex
+     * Add a vertex to the store with the given properties (or none). Return
+     * a descriptor to the vertex that was added to the vector.
+     */
     //@{
-    vertex_descriptor add();
-    vertex_descriptor add(vertex_properties const&);
+    inline vertex_descriptor add()
+    { return add(vertex_properties()); }
+
+    inline vertex_descriptor add(vertex_properties const& vp)
+    {
+        return make_descriptor(_verts, insert(_verts, vertex_type(vp)));
+    }
     //@}
 
-    /** Return the vertex with the given properties */
-    vertex_descriptor find(vertex_properties const&) const;
+    /**
+     * Return a descriptor to the vertex with the given properties. If you
+     * end up calling this function, you're probably using the wrong graph
+     * type.
+     */
+    vertex_descriptor find(vertex_properties const& vp) const
+    {
+        iterator i = std::find_if(_verts.begin(), _verts.end(), find_properties(vp));
+        return make_descriptor(_verts, i);
+    }
 
     /** Rerturn the number of vertices in the vector. */
     size_type size() const
     { return _verts.size(); }
 
+
     /** @name Vertex Iterators */
     //@{
     vertex_iterator begin_vertices() const
@@ -94,14 +116,15 @@
     { return std::make_pair(begin_vertices(), end_vertices()); }
     //@}
 
+
     /** @name Vertex Accessors */
     //@{
     vertex_type& vertex(vertex_descriptor v)
-    { return _verts[v.get()]; }
+    { return *make_iterator(_verts, v); }
 
     vertex_type const& vertex(vertex_descriptor v) const
-    { return _verts[v.get()]; }
-    //@{
+    { return *make_iterator(_verts, v); }
+    //@}
 
     /** @name Property Accessors */
     //@{
@@ -110,57 +133,10 @@
 
     vertex_properties const& properties(vertex_descriptor v) const
     { return vertex(v).properties(); }
-    //@{
+    //@}
 
 private:
-    vertex_store _verts;
+    mutable store_type _verts;
 };
 
-template <typename V, typename A>
-vertex_vector_impl<V,A>::vertex_vector_impl()
-    : _verts()
-{ }
-
-/**
- * Add a vertex to the store with no or default properties, returning the
- * the descriptor to the added vertex. Adding a vertex does not invalidate
- * any vertices or edges.
- *
- * @complexity O(~1)
- */
-template <typename V, typename A>
-typename vertex_vector_impl<V,A>::vertex_descriptor
-vertex_vector_impl<V,A>::add()
-{
-    return add(vertex_properties());
-}
-
-/**
- * Add a vertex to the store with the given properties. Adding a vertex does
- * not invalidate any other descriptors.
- *
- * @complexity O(1)
- */
-template <typename V, typename A>
-typename vertex_vector_impl<V,A>::vertex_descriptor
-vertex_vector_impl<V,A>::add(vertex_properties const& vp)
-{
-    // Just push the vertex to the back and return its index.
-    _verts.push_back(vertex_type(vp));
-    return _verts.size() - 1;
-}
-
-/**
- * Find the vertex with the given properties.
- *
- * @complexity O(V)
- */
-template <typename V, typename A>
-typename vertex_vector_impl<V,A>::vertex_descriptor
-vertex_vector_impl<V,A>::find(vertex_properties const& vp) const
-{
-    return std::distance(_verts.begin(),
-                         std::find(_verts.begin(), _verts.end(), vp));
-}
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -1,9 +1,19 @@
 
-exe un : un.cpp : <include>../../ <include>/usr/local/include ;
-exe di : di.cpp : <include>../../ <include>/usr/local/include ;
-exe set : set.cpp : <include>../../ <include>/usr/local/include ;
-exe map : map.cpp : <include>../../ <include>/usr/local/include ;
-exe test : test.cpp : <include>../../ <include>/usr/local/include ;
-exe props : props.cpp : <include>../../ <include>/usr/local/include ;
-exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
-exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
+
+# Import a newer version of g++ and configure it for C++0x support.
+using gcc : 4.4 : g++-4.4 : <cxxflags>-std=c++0x ;
+
+# Build all subrojects using g++-4.4
+project graphs
+    : requirements <toolset>gcc-4.4
+    ;
+
+# exe un : un.cpp : <include>../../ <include>/usr/local/include ;
+# exe di : di.cpp : <include>../../ <include>/usr/local/include ;
+# exe set : set.cpp : <include>../../ <include>/usr/local/include ;
+# exe map : map.cpp : <include>../../ <include>/usr/local/include ;
+# exe props : props.cpp : <include>../../ <include>/usr/local/include ;
+# exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
+# exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
+
+exe test : test.cpp : <include>../../ ;

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp	2008-07-05 10:03:40 EDT (Sat, 05 Jul 2008)
@@ -3,42 +3,69 @@
 #include <string>
 #include <list>
 
-#include <boost/next_prior.hpp>
-#include <boost/graphs/placeholder.hpp>
+#include <boost/none.hpp>
+#include <boost/graphs/vertex_vector.hpp>
+#include <boost/graphs/vertex_list.hpp>
+
+#include "demangle.hpp"
 
 using namespace std;
 using namespace boost;
 
+struct no_remove_tag { };
+struct has_remove_tag { };
+
+// A fake vertex type.
 struct Vertex
 {
-    Vertex(string n, int w)
-        : name(n), weight(w)
+    typedef int vertex_properties;
+
+    Vertex(int x)
+        : value(x)
     { }
 
-    string name;
-    int weight;
+    int& properties()
+    { return value; }
+
+    int const& properties() const
+    { return value; }
+
+    int value;
 };
 
-inline ostream& operator<<(ostream& os, Vertex const& v)
-{ return os << v.name << " " << v.weight; }
 
-int main()
+template <typename Store>
+void test_remove(Store& verts, stable_descriptor_tag)
 {
-    typedef list<Vertex> List;
-    typedef List::iterator Iterator;
+    verts.remove(3);
+    cout << "size after remove: " << verts.size() << endl;
+}
 
-    typedef list<int>::iterator Dummy;
-    typedef placeholder<sizeof(Dummy)> Reference;
+template <typename VertexSet>
+void test_remove(VertexSet& vs, unstable_remove_tag)
+{ /* Noop for unstable removes */ }
 
-    List verts;
-    verts.push_back(Vertex("a", 1));
-    verts.push_back(Vertex("b", 2));
+template <typename VertexSet>
+void test()
+{
+    typedef typename VertexSet::template store<Vertex>::type Store;
+    typedef typename VertexSet::descriptor_type Descriptor;
 
-    Reference x(verts.begin());
-    Reference y(prior(verts.end()));
+    cout << "--- " << demangle<VertexSet>() << " ---" << endl;
 
-    cout << *x.get<Iterator>() << endl;
-    cout << *y.get<Iterator>() << endl;
+    Store verts;
+    Descriptor d1 = verts.add(3);
 
-    return 0;
+    cout << "value of added props: " << verts.vertex(d1).value << endl;
+    cout << "value of found props: " << verts.vertex(verts.find(3)).value << endl;
+
+    test_remove(verts, typename descriptor_traits<typename Store::store_type>::descriptor_stability());
 }
+
+int main()
+{
+    test<vertex_vector<>>();
+    test<vertex_list<>>();
+
+    return 0;
+}
\ No newline at end of file