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>