From: asutton_at_[hidden]
Date: 2008-07-07 09:02:11
Author: asutton
Date: 2008-07-07 09:02:09 EDT (Mon, 07 Jul 2008)
New Revision: 47184
URL: http://svn.boost.org/trac/boost/changeset/47184
Log:
Rewriting the property store implementations. Removed the dependency on the
triple class, so that these types now store a pair of edge props and an
edge pair, which will consist of descriptors into the incidence stores.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/blob.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp | 16 ++
sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp | 6 +
sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp | 7 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 14 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 162 ++++++++++++---------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 87 +++++++++------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 6 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp | 28 ++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 3
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 3
14 files changed, 162 insertions(+), 175 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/blob.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/blob.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/blob.hpp 2008-07-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -85,7 +85,7 @@
{ return std::memcmp(mem, x.mem, N) >= 0; }
//@}
- mutable char mem[N];
+ mutable unsigned char mem[N];
};
template <unsigned int N>
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp 2008-07-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -84,22 +84,30 @@
/**
* Given a container and a valid iterator into the container, return a
* descriptor to the object being pointed at. The descriptor is guaranteed to
- * be at least as long as the iterator, generally longer.
+ * be at least as long as the iterator, generally longer. If the given iterator
+ * is past the end of the container, then the returned descriptor is null.
*/
template <typename Container>
inline typename descriptor_traits<Container>::descriptor_type
make_descriptor(Container& c, typename Container::iterator i)
-{ return typename descriptor_traits<Container>::descriptor_type(c, i); }
+{
+ typedef typename descriptor_traits<Container>::descriptor_type result_type;
+ return i != c.end() ? result_type(c, i) : result_type();
+}
/**
* Given a container and a valid descriptor, return an iterator pointing to the
* described object. The iterator will be valid as long as the descriptor has
- * not been invalidated (e.g., removing an item from a vector).
+ * not been invalidated (e.g., removing an item from a vector). If the given
+ * descriptor is null, then the returned iterator is past the end of the
+ * container.
*/
template <typename Container>
inline typename Container::iterator
make_iterator(Container& c, typename descriptor_traits<Container>::descriptor_type d)
-{ return d.get(c); }
+{
+ return d ? d.get(c) : c.end();
+}
/** Return the descriptor stability tag for the given container. */
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -26,9 +26,15 @@
: value(std::distance(c.begin(), i))
{ }
+ /** Return true if the descriptor is null. */
inline bool is_null() const
{ return value == descriptor_type(-1); }
+ /** Cast to bool tests to see if the descritpor is null. */
+ inline operator bool() const
+ { return !is_null(); }
+
+
/** @name Equality Comparable */
//@{
inline bool operator==(index_descriptor const& x)
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp 2008-07-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -25,9 +25,14 @@
: value(i)
{ }
- inline bool is_null()
+ /** Return true if the descriptor is null. */
+ inline bool is_null() const
{ return value == descriptor_type(); }
+ /** Cast to bool tests to see if the descritpor is null. */
+ inline operator bool() const
+ { return !is_null(); }
+
/** @name Equality Comparable */
//@{
inline bool operator==(node_descriptor const& x)
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -40,16 +40,24 @@
template <typename> class SecondAlloc = std::allocator>
struct edge_vector
{
+ typedef std::vector<int, FirstAlloc<int>> first_dummy;
+ typedef stdd::vector<int, SecondAlloc<int>> second_dummy;
+
+ 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>
+ template <typename EdgeProps, VertexDesc>
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 typename hold<typename std::vector<int>::iterator>::type dummy_type;
- typedef triple<EdgeProps, dummy_type, dummy_type> property;
+ typedef triple<EdgeProps, VertexDesc, VertexDesc> property;
typedef SecondAlloc<property> allocator;
typedef property_vector<property, allocator> type;
};
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -3,9 +3,10 @@
#define PROPERTY_LIST_HPP
#include <list>
+#include <algorithm>
-#include "triple.hpp"
-#include "descriptor.hpp"
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
/**
* The property list implements global list of properties for node-based edge
@@ -17,35 +18,62 @@
* removal of one element at a time, we do this to optimize calls to the size()
* function (which is used for the number of edges).
*/
-template <typename Props, typename Alloc>
+template <typename Edge, typename Alloc>
class property_list
{
- typedef std::list<Props, Alloc> store_type;
public:
- typedef Props properties_triple;
- typedef typename Props::first_type edge_properties;
-private:
- typedef typename Props::second_type first_iterator;
- typedef typename Props::third_type second_iterator;
-public:
- typedef typename store_type::const_iterator iterator;
+ typedef std::list<Edge, Alloc> store_type;
+
+ typedef Edge edge_type;
+ typedef typename Edge::first_type edge_properties;
+ typedef typename Edge::second_type edge_pair;
+
+ typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
- typedef descriptor<store_type> property_descriptor;
+ typedef typename descriptor_traits<store_type>::descriptor_type property_descriptor;
+
+ // Constructors.
inline property_list()
: _props(), _size(0)
{ }
- // Add properties
- inline property_descriptor add();
- inline property_descriptor add(edge_properties const&);
+ /** @name Add Property
+ * Add a property tot the global set, leaving the incidence descriptors
+ * empty for the time being.
+ */
+ //@{
+ inline property_descriptor add()
+ { return add(edge_properties()); }
- // Remove properties
- inline void remove(property_descriptor);
+ inline property_descriptor add(edge_properties const& ep)
+ {
+ ++_size;
+ iterator i = _props.insert(_props.end(), make_pair(ep, edge_pair()));
+ return make_descriptor(_props, i);
+ }
+ //@}
+
+ /**
+ * Find the edge with the given properties. Finding an edge by its
+ * properties is guaranteed to be O(E).
+ */
+ inline property_descriptor find(edge_properties const& ep) const
+ {
+ iterator i = std::find_if(_props.begin(), _props.end(), find_stored_edge(ep));
+ return make_descriptor(_props, i);
+ }
+
+ /** Remove the described property from the property set. */
+ inline void remove(property_descriptor d)
+ {
+ _props.erase(make_iterator(_props, d));
+ --_size;
+ }
// Property access.
inline edge_properties& properties(property_descriptor d)
- { return d.iter->first; }
+ { return make_iterator(_props, d)->first; }
/** Bind iterators into the incidence lists into the global property. */
template <typename Iter>
@@ -59,107 +87,19 @@
inline size_type size() const
{ return _size; }
+ /** @name Iterators */
+ //@{
inline iterator begin() const
{ return _props.begin(); }
inline iterator end() const
{ return _props.end(); }
+ //@}
private:
- store_type _props;
- size_type _size;
-};
-
-/**
- * Add an empty or default property to the list.
- */
-template <typename P, typename A>
-typename property_list<P,A>::property_descriptor
-property_list<P,A>::add()
-{
- return add(edge_properties());
-}
-
-/**
- * Add the specified properties to the list.
- */
-template <typename P, typename A>
-typename property_list<P,A>::property_descriptor
-property_list<P,A>::add(edge_properties const& p)
-{
- ++_size;
- _props.push_back(make_triple(p, first_iterator(), second_iterator()));
- return property_descriptor(_props, boost::prior(_props.end()));
-}
-
-/**
- * Remove the indicated property from the list. This invalidates any
- * descriptors and iterators to the given property, but no others.
- *
- * @complexity O(1)
- */
-template <typename P, typename A>
-void
-property_list<P,A>::remove(property_descriptor p)
-{
- --_size;
- _props.erase(p.iter);
-}
-
-/**
- * The proplist descriptor provides a wrapper around a list iterator that
- * provides comparability for the underlying iterator. Note that the comparison
- * has little to do with actual ordering of elements. This is to say that
- * i \< j !=> *i \< *j. This just provides a mechanism for ordering the
- * descriptors.
- */
-template <typename Iter>
-struct proplist_descriptor
-{
- inline proplist_descriptor()
- : iter()
- { }
-
- inline proplist_descriptor(Iter const& iter)
- : iter(iter)
- { }
-
- inline bool operator==(proplist_descriptor const& x) const
- { return iter == x.iter; }
-
- inline bool operator<(proplist_descriptor const& x) const
- { return &*iter < &*x.iter; }
-
- Iter iter;
+ mutable store_type _props;
+ size_type _size;
};
-
-// This helper type is used to erase global edge properties during edge removal
-// of undirected graphs.
-template <typename PropList>
-struct property_eraser
-{
- property_eraser(PropList& props)
- : props(props)
- { }
-
- template <typename PropDesc>
- void operator()(PropDesc p)
- { props.remove(p); }
-
- PropList& props;
-};
-
-// The noop eraser does nothing.
-struct noop_eraser
-{
- noop_eraser() { }
-
- template <typename PropDesc>
- void operator()(PropDesc)
- { }
-};
-
-
#endif
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -3,61 +3,64 @@
#define PROPERTY_VECTOR_HPP
#include <vector>
+#include <algorithm>
-#include "triple.hpp"
-#include "descriptor.hpp"
-
-// NOTE: Property stores hold two additional values. Right now, they contain
-// vertex descriptors, but would ideally by "iterators" into the incidence store
-// to make remove operations involing recipricol edge stubs more efficient.
-//
-// This really highlights the need for something like a "stable" iterator that
-// isn't invalidated by little things like complete reallocations and copies.
-// The problem can be stated as: how do you describe a never-invalidating
-// iterator into arbitrary containers and, can we map this onto iterators.
+#include <boost/descriptors.hpp>
+#include <boost/graphs/utility.hpp>
/**
* The property vector implements a vector-based global property store for
* vector-based edge storage. Assuming, of course, that there are actually edge
- * properties...
+ * properties.
*/
-template <typename Props, typename Alloc>
+template <typename Edge, typename Alloc>
class property_vector
{
- typedef std::vector<Props, Alloc> store_type;
-public:
- typedef Props properties_triple;
- typedef typename Props::first_type edge_properties;
-private:
- typedef typename Props::second_type first_iterator;
- typedef typename Props::third_type second_iterator;
public:
+ typedef std::vector<Edge, Alloc> store_type;
+
+ typedef Edge edge_type;
+ typedef typename Edge::first_type edge_properties;
+ typedef typename Edge::second_type edge_pair;
+
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
- typedef descriptor<store_type> property_descriptor;
+ typedef typename descriptor_traits<store_type>::descriptor_type property_descriptor;
+
+ // Constructor
inline property_vector()
: _props()
{ }
- property_descriptor add();
- property_descriptor add(edge_properties const&);
+ /** @name Add Property
+ * Add a property tot the global set, leaving the incidence descriptors
+ * empty for the time being.
+ */
+ //@{
+ property_descriptor add()
+ { return add(edge_properties()); }
- /** Return the properties referenced by the given descriptor. */
- inline edge_properties& properties(property_descriptor d)
- { return d.value().first; }
+ property_descriptor add(edge_properties const& ep)
+ {
+ iterator i = _props.insert(_props.end(), make_pair(ep, edge_pair()));
+ return make_descriptor(_props, i);
+ }
+ //@}
- /** Bind descriptors into the incidence lists into the global property. */
- template <typename VertexDesc>
- void bind(property_descriptor d, VertexDesc src, VertexDesc tgt)
+ /**
+ * Find the edge with the given properties. This function is guaranteed to
+ * run in O(E) time.
+ */
+ property_descriptor find(edge_properties const& ep) const
{
- d.value().second.put(src);
- d.value().third.put(tgt);
+ iterator i = std::find_if(_props.begin(), _props.end(), find_stored_edge(ep));
+ return make_descriptor(_props, i);
}
- /** Convert an iterator to a descriptor. */
- inline property_descriptor describe(iterator i) const
- { return property_descriptor(_props, i); }
+ /** Return the properties referenced by the given descriptor. */
+ inline edge_properties& properties(property_descriptor d)
+ { return d.value().first; }
/** Return the number of properties in the store. */
inline size_type size() const
@@ -76,21 +79,5 @@
mutable store_type _props;
};
-
-template <typename P, typename A>
-typename property_vector<P,A>::property_descriptor
-property_vector<P,A>::add()
-{
- return add(edge_properties());
-}
-
-template <typename P, typename A>
-typename property_vector<P,A>::property_descriptor
-property_vector<P,A>::add(edge_properties const& p)
-{
- _props.push_back(make_triple(p, first_iterator(), second_iterator()));
- return property_descriptor(_props, boost::prior(_props.end()));
-}
-
#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-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -31,6 +31,10 @@
typedef VertexStore vertex_store_selector;
typedef EdgeStore edge_store_selector;
+ typedef VertexStore::descriptor_type vertex_descriptor;
+
+ typedef typename EdgeStore::EdgeStore::template property_store<edge_properties, vertex_descriptor>::type property_store;
+
// Generate the property store type first. We can do this first because
// it's basically independant of everything else, but contributes to almost
// everything in the class by virtue of the property descriptor. Use this
@@ -43,7 +47,7 @@
// straightforward since, like the property store, its independant of almost
// everything. The property descriptor depends entirely upon the property
// store and the edge descriptor is actually fairly complicated.
- typedef typename VertexStore::descriptor_type vertex_descriptor;
+ // typedef typename VertexStore::descriptor_type vertex_descriptor;
typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
// Generate the incidence list. The incidence list for a single vertex
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -30,6 +30,7 @@
* same value as those given in the cosntructor. This works for both vertices
* and edges.
* @param Properties The type of properties being compared.
+ * @todo This goes away with lambda expressions. Used in vertex_[v|l]::find().
*/
template <typename Properties>
struct property_finder
@@ -51,4 +52,31 @@
{ return property_finder<Properties>(props); }
+/**
+ * @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).
+ */
+template <typename Properties>
+struct stored_edge_finder
+{
+ inline stored_edge_finder(Properties const& p)
+ : props(p)
+ { }
+
+ template <typename Edge>
+ inline bool operator()(Edge const& e) const
+ { return e.first == props; }
+
+ Properties const& props;
+};
+
+template <typename Properties>
+inline stored_edge_finder<Properties>
+find_stored_edge(Properties const& props)
+{ return stored_edge_finder<Properties>(props); }
+
+
#endif
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-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -4,6 +4,7 @@
#include <list>
+#include <boost/none.hpp>
#include <boost/descriptors.hpp>
#include "vertex_iterator.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp 2008-07-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -4,6 +4,7 @@
#include <set>
+#include <boost/none.hpp>
#include <boost/descriptors.hpp>
#include <boost/graphs/utility.hpp>
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-07 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -5,6 +5,7 @@
#include <vector>
#include <algorithm>
+#include <boost/none.hpp>
#include <boost/descriptors.hpp>
#include <boost/graphs/utility.hpp>
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -16,4 +16,5 @@
# exe edge : edge.cpp : <include>../../ <include>/usr/local/include ;
# exe desc : desc.cpp : <include>../../ <include>/usr/local/include ;
-exe test : test.cpp : <include>../../ ;
+exe test_verts : test_verts.cpp : <include>../../ ;
+exe test_props : test_props.cpp : <include>../../ ;
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 09:02:09 EDT (Mon, 07 Jul 2008)
@@ -1,9 +1,6 @@
#include <iostream>
-#include <string>
-#include <list>
-#include <boost/none.hpp>
#include <boost/graphs/vertex_vector.hpp>
#include <boost/graphs/vertex_list.hpp>
#include <boost/graphs/vertex_set.hpp>