|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-07 10:49:50
Author: asutton
Date: 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
New Revision: 47191
URL: http://svn.boost.org/trac/boost/changeset/47191
Log:
Rewriting the incidence stores to use new descriptor lib.
Fixed a couple of descriptor bugs (i.e., non-const relational operators and
incorrect boolean casts).
Rebuilding test hierarchy. Eventually most of the tests will be moved to hdr
files to enable better componentization. Started adding traits for specific
types of containers.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp
- copied, changed from r47177, /sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp | 8 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 29 ++++++++-------
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp | 56 ++++++++++++-----------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp | 75 ++++++++++++++++++---------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 30 ++++++++--------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp | 33 +++++++++--------
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 2 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp | 13 +++---
11 files changed, 121 insertions(+), 133 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -46,16 +46,16 @@
/** @name Less Than Comparable */
//@{
- inline bool operator<(index_descriptor const& x)
+ inline bool operator<(index_descriptor const& x) const
{ return value < x.value; }
- inline bool operator>(index_descriptor const& x)
+ inline bool operator>(index_descriptor const& x) const
{ return value > x.value; }
- inline bool operator<=(index_descriptor const& x)
+ inline bool operator<=(index_descriptor const& x) const
{ return value <= x.value; }
- inline bool operator>=(index_descriptor const& x)
+ inline bool operator>=(index_descriptor const& x) const
{ return value >= x.value; }
//@}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -2,9 +2,6 @@
#ifndef EDGE_VECTOR_HPP
#define EDGE_VECTOR_HPP
-#include "triple.hpp"
-#include "placeholder.hpp"
-
#include "property_vector.hpp"
#include "incidence_vector.hpp"
#include "out_vector.hpp"
@@ -40,26 +37,22 @@
template <typename> class SecondAlloc = std::allocator>
struct edge_vector
{
+ // A couple of dummy vectors used to build descriptors.
typedef std::vector<int, FirstAlloc<int>> first_dummy;
- typedef stdd::vector<int, SecondAlloc<int>> second_dummy;
+ typedef std::vector<int, SecondAlloc<int>> second_dummy;
+ // Descriptor types for undirected graphs.
typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
// The property store metafunction generates the type of vector used to
// store global properties for undirected graphs.
- template <typename EdgeProps, VertexDesc>
+ template <typename EdgeProps, typename IncDesc>
struct property_store
{
- // Define a dummy type that will eventually container iterators into
- // an incidence container. Use this as part of the triple for each
- // edge store - the properties and "out-facing" iterators.
- typedef triple<EdgeProps, VertexDesc, VertexDesc> property;
- typedef SecondAlloc<property> allocator;
- typedef property_vector<property, allocator> type;
+ typedef std::pair<EdgeProps, std::pair<IncDesc, IncDesc>> edge;
+ typedef SecondAlloc<edge> allocator;
+ typedef property_vector<edge, allocator> type;
};
// The incidence store metafunction generates the type of vector used to
@@ -72,8 +65,15 @@
typedef incidence_vector<incidence_pair, incidence_allocator> type;
};
+
+ // Descritor types for directed graphs
+ typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
+ typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
+
+
// The out store metafunction generates the type of vector used to store
// out edges of a vertex in a directed graph.
+ /*
template <typename VertexDesc, typename Props>
struct out_store
{
@@ -101,6 +101,7 @@
typedef SecondAlloc<edge> allocator;
typedef in_vector<edge, allocator> type;
};
+ */
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -5,6 +5,8 @@
#include <list>
#include <algorithm>
+#include <boost/graphs/utility.hpp>
+
/**
* The incidence vector stores incident "edges" of a vertex. In actuality,
* this stores pairs containing an adjacent vertex descriptor and a property
@@ -13,22 +15,23 @@
*
* This type allows constant time insertions, and linear search and remove.
*/
-template <typename IncEdge, typename Alloc>
+template <typename Edge, typename Alloc>
class incidence_list
{
- typedef std::list<IncEdge, Alloc> store_type;
public:
- typedef IncEdge incidence_pair;
- typedef typename IncEdge::first_type vertex_descriptor;
- typedef typename IncEdge::second_type property_descriptor;
+ typedef std::list<Edge, Alloc> store_type;
+
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type property_descriptor;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
+ typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
+
// Constructors
incidence_list()
- : _edges()
- , _size(0)
+ : _edges(), _size(0)
{ }
/**
@@ -36,53 +39,38 @@
* conflicts exist. The first element of the return is the end() of the list.
* @complexity O(1)
*/
- inline std::pair<iterator, bool> allow(vertex_descriptor) const
- { return make_pair(_edges.end(), true); }
+ inline std::pair<incidence_descriptor, bool> allow(vertex_descriptor) const
+ { return make_pair(make_descriptor(_edges, _edges.end()), true); }
/**
* Add a vertex to the list.
* @complexity O(1)
*/
- inline iterator add(incidence_pair p)
+ inline incidence_descriptor add(vertex_descriptor v, property_descriptor p)
{
++_size;
- return _edges.insert(_edges.end(), p);
+ iterator i = _edges.insert(_edges.end(), make_pair(v, p));
+ return make_descriptor(_edges, i);
}
/**
* Find the given incidence pair in the vertex.
- * @todo Do we need this function?
* @complexity O(1)
*/
- inline iterator find(incidence_pair p) const
- { return std::find(_edges.begin(), _edges.end(), p); }
-
- /** Find the edge with the given vertex. */
- inline iterator find(vertex_descriptor v) const
+ inline incidence_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);
}
/**
* Remove the given incidence pair in this vertex.
* @complexity O(deg(v))
*/
- inline void remove(incidence_pair p)
- { remove(find(p)); }
-
- /**
- * Remove the iterator.
- * @complexity O(1)
- */
- inline iterator remove(iterator i)
+ inline void remove(incidence_descriptor d)
{
+ _edges.erase(make_iterator(_edges, d));
--_size;
- return _edges.erase(i);
}
/** Remove all edges from the vertex. */
@@ -92,14 +80,18 @@
_edges.clear();
}
+ /** Return the number of edges in this store. */
inline size_type size() const
{ return _size; }
+ /** @name Iterators */
+ //@{
inline iterator begin() const
{ return _edges.begin(); }
inline iterator end() const
{ return _edges.end(); }
+ //@}
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -4,7 +4,7 @@
#include <map>
-#include <boost/next_prior.hpp>
+#include <boost/descriptors.hpp>
/**
* The incidence vector stores incident "edges" of a vertex. In actuality,
@@ -14,23 +14,28 @@
*
* This type allows logarithmic time insertions, searches, and removals.
*/
-template <typename IncEdge, typename Compare, typename Alloc>
+template <typename Edge, typename Compare, typename Alloc>
class incidence_set
{
public:
- typedef IncEdge incidence_pair;
- typedef typename IncEdge::first_type vertex_descriptor;
- typedef typename IncEdge::second_type property_descriptor;
-private:
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type property_descriptor;
+
// Actually, the incident set, as it fundamentally implements a simple
// graph is based on a map keyed on the adjacenct vertex and mapped to the
// edge properties that describe it. We're basically undwinding and
// rebuilding the edge pair for this map.
+ // NOTE: This can impose some difficulties since the vertex (key type) will
+ // be made const in this map. That means we may have to cast out the const
+ // aspect of the key at times, but changing that value would be absolutely
+ // catastrophic.
typedef std::map<vertex_descriptor, property_descriptor, Compare, Alloc> store_type;
-public:
+
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
+ typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
+
// Constructors
inline incidence_set()
: _edges()
@@ -41,63 +46,51 @@
* This returns a pair containing an iterator indicating the position of the
* edge if it already exists and a bool value indicating whether or not the
* addition would even be allowed by policy.
- * @complexity O(lg(deg(v)))
+ * @complexity O(lg(dd))
*/
- inline std::pair<iterator, bool> allow(vertex_descriptor v) const
- { return make_pair(_edges.find(v), true); }
+ inline std::pair<incidence_descriptor, bool> allow(vertex_descriptor v) const
+ { return make_pair(make_descriptor(_edges, _edges.find(v)), true); }
/**
* Add the incidence pair to the vertex.
- * @complexity O(lg(deg(v)))
- */
- inline iterator add(incidence_pair p)
- { return _edges.insert(p).first; }
-
- /**
- * Find the incidence pair.
- * @complexity O(lg(deg(v)))
+ * @complexity O(lg(d))
*/
- inline iterator find(incidence_pair p) const
- { return find(p.first); }
-
- /**
- * Find the incidence pair.
- * @complexity O(lg(deg(v)))
- */
- inline iterator find(vertex_descriptor v) const
- { return _edges.find(v); }
+ inline incidence_descriptor add(vertex_descriptor v, property_descriptor p)
+ {
+ std::pair<iterator, bool> i = _edges.insert(make_pair(v, p));
+ return make_descriptor(_edges, i.first);
+ }
/**
- * Remove the incidence pair from the set.
- * @complexity O(lg(deg(v)))
+ * Find the incident edge whose opposite end is v.
+ * @complexity O(lg(d))
*/
- inline void remove(incidence_pair p)
- { _edges.erase(find(p)); }
+ inline incidence_descriptor find(vertex_descriptor v) const
+ { return make_descriptor(_edges, _edges.find(v)); }
/**
- * Remove the iterator to the given incidence pair, returning an iterator
- * to the next object in the sequence.
- * @complexity O(lg(deg(v)))
+ * Remove the edge whose opposite end is v.
+ * @complexity O(lg(d))
*/
- inline iterator remove(iterator x)
- {
- iterator ret = boost::next(x);
- _edges.erase(x);
- return ret;
- }
+ inline void remove(incidence_descriptor d)
+ { _edges.erase(make_iterator(_edges, d)); }
- // Remove edges.
+ /** Remove all edges incident to this vertex. */
inline void clear()
{ _edges.clear(); }
+ /** Return the number of edges incident to this vertex. */
inline size_type size() const
{ return _edges.size(); }
+ /** @name Iterators */
+ //@{
inline iterator begin() const
{ return _edges.begin(); }
inline iterator end() const
{ return _edges.end(); }
+ //@}
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -3,8 +3,9 @@
#define INCIDENCE_VECTOR
#include <vector>
+#include <algorithm>
-#include <boost/next_prior.hpp>
+#include <boost/descriptors.hpp>
/**
* The incidence vector stores incident "edges" of a vertex. In actuality,
@@ -18,15 +19,17 @@
template <typename Edge, typename Alloc>
class incidence_vector
{
- typedef std::vector<Edge, Alloc> store_type;
public:
- typedef Edge incidence_pair;
+ typedef std::vector<Edge, Alloc> store_type;
+
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type property_descriptor;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
+ typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
+
// Constructors
inline incidence_vector()
: _edges()
@@ -38,27 +41,24 @@
* the vector.
* @complexity O(1)
*/
- std::pair<iterator, bool> allow(vertex_descriptor) const
- { return make_pair(_edges.end(), true); }
+ std::pair<incidence_descriptor, bool> allow(vertex_descriptor) const
+ { return make_pair(incidence_descriptor(), true); }
/** Add the incidence pair to the vector. */
- iterator add(incidence_pair p)
+ incidence_descriptor add(vertex_descriptor v, property_descriptor p)
{
- _edges.push_back(p);
- return boost::prior(_edges.end());
+ iterator i = _edges.insert(_edges.end(), std::make_pair(v, p));
+ return make_descriptor(_edges, i);
}
/** Find the edge with the given vertex. */
- inline iterator find(vertex_descriptor v) const
+ inline incidence_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);
}
+ /** Return the number of edges in this store. */
inline size_type size() const
{ return _edges.size(); }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -60,7 +60,7 @@
*/
inline property_descriptor find(edge_properties const& ep) const
{
- iterator i = std::find_if(_props.begin(), _props.end(), find_stored_edge(ep));
+ iterator i = std::find_if(_props.begin(), _props.end(), find_first(ep));
return make_descriptor(_props, i);
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -54,7 +54,7 @@
*/
property_descriptor find(edge_properties const& ep) const
{
- iterator i = std::find_if(_props.begin(), _props.end(), find_stored_edge(ep));
+ iterator i = std::find_if(_props.begin(), _props.end(), find_first(ep));
return make_descriptor(_props, i);
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -54,29 +54,30 @@
/**
* @internal
- * A functor that returns true when we can find a an edge with the given
- * properties.
- * @param Properties The type of properties being compared.
- * @todo This goes away with lambda expression (in property_*::find).
+ * A functor that returns true when the first value of a pair (or other tuple
+ * with a named first element) matches that of the constructed value.
+ * @param First The type of the first element.
+ * @todo This goes away with lambda expression (in property_*::find and
+ * incidence_*::find).
*/
-template <typename Properties>
-struct stored_edge_finder
+template <typename First>
+struct first_finder
{
- inline stored_edge_finder(Properties const& p)
- : props(p)
+ inline first_finder(First const& x)
+ : value(x)
{ }
- template <typename Edge>
- inline bool operator()(Edge const& e) const
- { return e.first == props; }
+ template <typename Object>
+ inline bool operator()(Object const& o) const
+ { return o.first == value; }
- Properties const& props;
+ First const& value;
};
-template <typename Properties>
-inline stored_edge_finder<Properties>
-find_stored_edge(Properties const& props)
-{ return stored_edge_finder<Properties>(props); }
+template <typename First>
+inline first_finder<First>
+find_first(First const& props)
+{ return first_finder<First>(props); }
#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-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -18,3 +18,5 @@
exe test_verts : test_verts.cpp : <include>../../ ;
exe test_props : test_props.cpp : <include>../../ ;
+exe test_incs : test_incs.cpp : <include>../../ ;
+exe test_es : test_es.cpp : <include>../../ ;
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
+++ (empty file)
@@ -1,25 +0,0 @@
-
-#ifndef DEMANGLE_HPP
-#define DEMANGLE_HPP
-
-#include <string>
-#include <typeinfo>
-#include <cxxabi.h>
-
-inline std::string
-demangle(std::string const& name)
-{
- std::size_t n = 2048;
- char buf[2048];
- abi::__cxa_demangle(name.c_str(), buf, &n, 0);
- return std::string(buf, ::strnlen(buf, n));
-}
-
-template <typename T>
-inline std::string
-demangle()
-{
- return demangle(typeid(T).name());
-}
-
-#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,38 @@
+
+#include <iostream>
+
+#include <boost/next_prior.hpp>
+#include <boost/graphs/edge_vector.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+// These are things that we can't do much about...
+typedef int VertexProps;
+typedef int EdgeProps;
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> IncDesc;
+
+template <typename EdgeStore>
+void
+undirected()
+{
+ cout << "--- " << typestr<EdgeStore>() << " ---" << endl;
+
+ // Instantiate data structures related to the storage of edges and their
+ // properties.
+ typedef typename EdgeStore::template property_store<EdgeProps, IncDesc>::type PropStore;
+ typedef typename EdgeStore::template incidence_store<EdgeProps, IncDesc>::type IncStore;
+
+ cout << " * " << typestr<PropStore>() << endl;
+ cout << " * " << typestr<IncStore>() << endl;
+}
+
+int main()
+{
+ undirected<edge_vector<>>();
+
+ return 0;
+}
\ No newline at end of file
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,83 @@
+
+#include <iostream>
+
+#include <boost/graphs/incidence_vector.hpp>
+#include <boost/graphs/incidence_list.hpp>
+#include <boost/graphs/incidence_set.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+struct incidence_vector_tag : unstable_remove_tag { };
+struct incidence_list_tag : stable_descriptor_tag { };
+struct incidence_set_tag : stable_descriptor_tag { };
+
+template <typename IncStore>
+struct incidence_traits
+{ typedef typename IncStore::category category; };
+
+template <typename IncStore>
+typename incidence_traits<IncStore>::category
+incidence_category(IncStore const&)
+{ return typename incidence_traits<IncStore>::category(); }
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_vector<Edge, Alloc>>
+{ typedef incidence_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_list<Edge, Alloc>>
+{ typedef incidence_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct incidence_traits<incidence_set<Edge, Comp, Alloc>>
+{ typedef incidence_set_tag category; };
+
+
+
+typedef index_descriptor<size_t> VertexDesc;
+typedef index_descriptor<size_t> PropDesc;
+typedef std::pair<VertexDesc, PropDesc> Edge;
+typedef allocator<Edge> Alloc;
+typedef std::less<VertexDesc> Compare;
+
+
+
+template <typename IncStore>
+void test_remove(IncStore& incs, stable_descriptor_tag)
+{
+ // Kind of strange, but we can actually construct some types of descriptors
+ // withou an iterator.
+ incs.remove(incs.find(VertexDesc(0)));
+ cout << " * num incs after removing " << incs.size() << endl;
+}
+
+template <typename IncStore>
+void test_remove(IncStore& incs, unstable_remove_tag)
+{ /* Can't remove elements. */ }
+
+template <typename IncStore>
+void test()
+{
+ IncStore incs;
+ cout << "--- " << typestr(incidence_category(incs)) << " ---" << endl;
+
+ // Add some edges
+ incs.add(VertexDesc(0), PropDesc(0));
+ incs.add(VertexDesc(1), PropDesc(1));
+ cout << " * num incs after building: " << incs.size() << endl;
+
+ // Try to remove something
+ test_remove(incs, incidence_category(incs));
+}
+
+int main()
+{
+ test<incidence_vector<Edge, Alloc>>();
+ test<incidence_list<Edge, Alloc>>();
+ test<incidence_set<Edge, Compare, Alloc>>();
+
+ return 0;
+}
\ No newline at end of file
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,54 @@
+
+#include <iostream>
+
+#include <boost/graphs/property_vector.hpp>
+#include <boost/graphs/property_list.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+typedef int EdgeProperties;
+typedef descriptor_traits<std::list<int>>::descriptor_type IncDesc;
+
+template <typename PropSet>
+void test_remove(PropSet& props, stable_descriptor_tag)
+{
+ props.remove(props.find(5));
+ std::cout << "num props after remove: " << props.size() << endl;
+}
+
+template <typename PropSet>
+void test_remove(PropSet& props, unstable_remove_tag)
+{ /* Can't remove! */ }
+
+template <typename PropSet>
+void test()
+{
+ typedef typename PropSet::property_descriptor PropDesc;
+ typedef typename descriptor_traits<typename PropSet::store_type>::descriptor_stability Stability;
+
+ cout << "--- " << typestr<PropSet>() << " ---" << endl;
+
+ // Add some properties
+ PropSet props;
+ for(int i = 0; i < 10; ++i) {
+ props.add(i);
+ }
+ cout << "num props after build: " << props.size() << endl;
+
+ test_remove(props, Stability());
+}
+
+int main()
+{
+ typedef pair<IncDesc, IncDesc> EdgePair;
+ typedef pair<EdgeProperties, EdgePair> StoredEdge;
+ typedef allocator<StoredEdge> Allocator;
+
+ test<property_vector<StoredEdge, Allocator>>();
+ test<property_list<StoredEdge, Allocator>>();
+
+ return 0;
+}
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -6,7 +6,7 @@
#include <boost/graphs/vertex_set.hpp>
#include <boost/graphs/vertex_map.hpp>
-#include "demangle.hpp"
+#include "typestr.hpp"
using namespace std;
using namespace boost;
@@ -74,7 +74,7 @@
typedef typename VertexSet::descriptor_type Descriptor;
typedef typename Store::store_type StoreImpl;
- cout << "--- " << demangle<VertexSet>() << " ---" << endl;
+ cout << "--- " << typestr<VertexSet>() << " ---" << endl;
Store verts;
Copied: sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp (from r47177, /sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp 2008-07-07 10:49:49 EDT (Mon, 07 Jul 2008)
@@ -6,20 +6,19 @@
#include <typeinfo>
#include <cxxabi.h>
-inline std::string
-demangle(std::string const& name)
+template <typename T>
+std::string
+typestr()
{
std::size_t n = 2048;
char buf[2048];
- abi::__cxa_demangle(name.c_str(), buf, &n, 0);
+ abi::__cxa_demangle(typeid(T).name(), buf, &n, 0);
return std::string(buf, ::strnlen(buf, n));
}
template <typename T>
inline std::string
-demangle()
-{
- return demangle(typeid(T).name());
-}
+typestr(T const&)
+{ return typestr<T>(); }
#endif
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk