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

From: asutton_at_[hidden]
Date: 2008-07-07 21:23:13

Author: asutton
Date: 2008-07-07 21:23:12 EDT (Mon, 07 Jul 2008)
New Revision: 47201
URL: http://svn.boost.org/trac/boost/changeset/47201

Log:
Fixed the out vector implementation, started writing tests for all out edge
stores.

Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp |    36 ++++++++++++++++++++----------------    
   sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile         |     1 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp     |     2 +-                                      
   3 files changed, 22 insertions(+), 17 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp	2008-07-07 21:23:12 EDT (Mon, 07 Jul 2008)
@@ -3,6 +3,10 @@
 #define OUT_VECTOR_HPP
 
 #include <vector>
+#include <algorithm>
+
+#include <boost/triple.hpp>
+#include <boost/descriptors.hpp>
 
 /**
  * The in/out vector implements vector-based, edge storage for directed graphs.
@@ -15,18 +19,18 @@
 template <typename Edge, typename Alloc>
 class out_vector
 {
-    typedef std::vector<Edge, Alloc> store_type;
 public:
-    typedef Edge out_tuple;
     typedef typename Edge::first_type vertex_descriptor;
     typedef typename Edge::second_type edge_properties;
-private:
-    typedef typename Edge::third_type in_edge_place;
-public:
-    typedef std::pair<vertex_descriptor, edge_properties> out_pair;
+    typedef typename Edge::third_type in_descriptor;
+    
+    typedef std::vector<Edge, Alloc> store_type;
     typedef typename store_type::iterator iterator;
     typedef typename store_type::size_type size_type;
 
+    typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
+
+    // Constructor
     inline out_vector()
         : _edges()
     { }
@@ -42,27 +46,27 @@
      * Add the edge to the vector.
      * @complexity O(1)
      */
-    iterator add(vertex_descriptor v, edge_properties const& ep)
+    out_descriptor add(vertex_descriptor v, edge_properties const& ep)
     {
-        _edges.push_back(out_tuple(v, ep, in_edge_place()));
-        return boost::prior(_edges.end());
+        iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
+        return make_descriptor(_edges, i);
     }
 
     /** Find the edge with the given vertex. */
-    iterator find(vertex_descriptor v) const
+    out_descriptor find(vertex_descriptor v) const
     {
-        // TODO How do I write this with std::find?
-        iterator i = _edges.begin(), end = _edges.end();
-        for( ; i != end; ++i) {
-            if(i->first == v) return i;
-        }
-        return end;
+        iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
+        return make_descriptor(_edges, i);
     }
 
     /** Get the number of outgoing edges. */
     inline size_type size() const
     { return _edges.size(); }
 
+    /** Return true if there are no out edges. */
+    inline bool empty() const
+    { return _edges.empty(); }
+
     /** @name Iterators */
     //@{
     inline iterator begin() const

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-07 21:23:12 EDT (Mon, 07 Jul 2008)
@@ -20,3 +20,4 @@
 exe test_props : test_props.cpp : <include>../../ ;
 exe test_incs : test_incs.cpp : <include>../../ ;
 exe test_es : test_es.cpp : <include>../../ ;
+exe test_outs : test_outs.cpp : <include>../../ ;

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp	2008-07-07 21:23:12 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,52 @@
+
+#include <iostream>
+
+#include <boost/graphs/out_vector.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+struct out_vector_tag : sequence_tag, unstable_remove_tag { };
+struct out_list_tag : sequence_tag, stable_mutators_tag { };
+struct out_set_tag : associative_container_tag, stable_mutators_tag { };
+
+template <typename Outs>
+struct out_edge_traits
+{ typedef typename Outs::category cateogry; };
+
+template <typename Outs>
+typename out_edge_traits<Outs>::category
+out_edge_category(Outs const&)
+{ return typename out_edge_traits<Outs>::category(); }
+
+template <typename Edge, typename Alloc>
+struct out_edge_traits<out_vector<Edge, Alloc>>
+{ typedef out_vector_tag category; };
+
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> InDesc;
+typedef int EdgeProps;
+typedef triple<VertexDesc, EdgeProps, InDesc> OutEdge;
+typedef allocator<OutEdge> Alloc;
+
+template <typename Outs>
+void test()
+{
+    Outs outs;
+    cout << "--- " << typestr(out_edge_category(outs)) << " ---" <<  endl;
+
+    BOOST_ASSERT(outs.empty());
+    for(int i = 0; i < 5; ++i) {
+        outs.add(VertexDesc(i), i * i);
+    }
+    BOOST_ASSERT(outs.size() == 5);
+}
+
+int main()
+{
+    test<out_vector<OutEdge, Alloc>>();
+    return 0;
+}

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp	2008-07-07 21:23:12 EDT (Mon, 07 Jul 2008)
@@ -13,7 +13,7 @@
     std::size_t n = 2048;
     char buf[2048];
     abi::__cxa_demangle(typeid(T).name(), buf, &n, 0);
-    return std::string(buf, ::strnlen(buf, n));
+    return std::string(buf, ::strlen(buf));
 }
 
 template <typename T>