From: asutton_at_[hidden]
Date: 2008-06-19 08:06:50
Author: asutton
Date: 2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
New Revision: 46504
URL: http://svn.boost.org/trac/boost/changeset/46504
Log:
Cleaned up the vertex_vector implementation.
Documented all of the vertex set operations for the undirected graph and
started adding some static asserts to the graph class to prevent unsupported
operations.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp | 20 ++
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 7
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 193 ++++++++++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 211 ++++++---------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp | 376 +++++++++++++++------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp | 340 ++++++++++-------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 215 ++++++----------------
7 files changed, 579 insertions(+), 783 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp 2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -2,8 +2,26 @@
#ifndef NONE_HPP
#define NONE_HPP
-// The canonical none type.
+#include <boost/utility.hpp>
+
+/** The canonical none type. */
struct none { };
+/** Like none, but not. */
+struct unused { };
+
+// Traits for the none type
+template <typename T>
+struct is_none { BOOST_STATIC_CONSTANT(bool, value = false); };
+
+template <>
+struct is_none<none> { BOOST_STATIC_CONSTANT(bool, value = true); };
+
+template <typename T>
+struct is_not_none { BOOST_STATIC_CONSTANT(bool, value = !is_none<T>::value); };
+
+template <>
+struct is_not_none<none> { BOOST_STATIC_CONSTANT(bool, value = !is_none<none>::value); };
+
#endif
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-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -48,6 +48,11 @@
size_type _size;
};
+// TODO: This eventually needs to be specialized for empty edges. Basically, if
+// you don't want edges, then we can just hand out integers that for each
+// edge - probably.
+#if 0
+
/**
* Partially specialize the property list for the case where the user does
* not want properties. This will completely remove the property list from
@@ -60,6 +65,8 @@
typedef std::size_t property_descriptor;
};
+#endif
+
template <typename P, typename A>
property_list<P,A>::property_list()
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-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -17,6 +17,9 @@
// need to exist. We can just pretend to allocate them and return
// an integer "pseudo descriptor".
+// Note that the graph interface will fail to compile if a mapped graph is
+// requested whose key and property types are the same.
+
#include "descriptor.hpp"
#include "undirected_vertex.hpp"
@@ -24,12 +27,12 @@
#include "vertex_vector.hpp"
#include "vertex_list.hpp"
#include "vertex_set.hpp"
+#include "vertex_map.hpp"
#include "undirected_edge.hpp"
#include "edge_vector.hpp"
#include "edge_list.hpp"
#include "edge_set.hpp"
-#include "edge_iterator.hpp"
#include "adjacency_iterator.hpp"
@@ -83,29 +86,83 @@
typedef typename vertex_store::vertex_range vertex_range;
// FIXME: This is a bit hacky, but without constrained members, we need a key
// type to enable mapped vertices.
- typedef typename VertexStore::key_type key_type;
-
- // Because edges are "distributed" among vertices, the edge iterators are
- // somewhat special.
- typedef basic_edge_iterator<this_type> edge_iterator;
- typedef std::pair<edge_iterator, edge_iterator> edge_range;
+ typedef typename VertexStore::key_type vertex_key;
// Constructors
undirected_graph();
- /** @name Vertex Set
- * These functions operate (mostly) on the vertices of the graph. These
- * functions include the ability to add, disconnect, and remove vertices.
+ /** @name Add Vertex
+ * Add a vertex to the graph. Add operations are determined by the concepts
+ * modeled by the vertex set.
+ *
+ * UnlabeledVertices add_vertex()
+ * LabeledVerteces add_vertex(vertex_properties)
+ * LabeledUniqueVertices add_vertex(vertex_properties)
+ * MappedUniqueVertices add_vertex(vertex_key)
*/
//@{
vertex_descriptor add_vertex();
vertex_descriptor add_vertex(vertex_properties const&);
- vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
+ vertex_descriptor add_vertex(vertex_key const&, vertex_properties const&);
+ //@}
+
+ /** @name Find Vertex
+ * Find a vertex in the graph. These methods only exist for graphs that
+ * have UniqueVertices. These functions can also be used to find the first
+ * vertex of a non-unique vertices.
+ *
+ * LabeledUniqueVertices find_vertex(vertex_properties)
+ * MappedUniqueVertices find_vertex(vertex_key)
+ */
+ //@{
+ vertex_descriptor find_vertex(vertex_properties const&) const;
+ vertex_descriptor find_vertex(vertex_key const&) const;
+ //@{
+
+ /** @name Disconnect Vertex
+ * Disconnect a vertex from the graph by removing all of its incident edges.
+ * These functions only exist for graphs with ReducibleEdgeSets. Functions
+ * that take properties or keys are provided for convenience, but have
+ * additional dependencies and cost. These additonal functions are
+ * equivalent to disconnect_vertex(find_vertex(x)) where x is either a
+ * vertex_properties or vertex_key.
+ *
+ * ReducibleEdgeSet disconnect_vertex(vertex_descriptor)
+ * LabeledUniqueVertices disconnect_vertex(vertex_properties)
+ * MappedUniqueVertices disconnect_vertex(vertex_key)
+ */
+ //@{
void disconnect_vertex(vertex_descriptor);
+ void disconnect_vertex(vertex_properties const&);
+ void disconnect_vertex(vertex_key const&);
+ //@}
+
+ /** @name Remove Vertex
+ * Remove a vertex from the graph. These functions only exist for graphs
+ * with ReducibleVertexSets. Functions that take properties or keys are
+ * provided for convenience, but have additional requirements and cost.
+ * These additional functions are equivalent to remove_vertex(find_vertex(x))
+ * where x is either a vertex_properties or vertex_key.
+ *
+ * ReducibleVertexSet remove_vertex(vertex_descriptor)
+ * LabeledUniqueVertices remove_vertex(vertex_properties)
+ * MappedUniqueVertices remove_vertex(vertex_key)
+ */
+ //@{
void remove_vertex(vertex_descriptor);
+ void remove_vertex(vertex_properties const&);
+ void remove_vertex(vertex_key const&);
//@}
+ /** @name Vertex Key
+ * Return the key for the given vertex. This is only provided for graphs
+ * with MappedVertices (can be multimapped).
+ */
+ //@{
+ vertex_key const& key(vertex_descriptor) const;
+ //@{
+
/** @name Edge Set
* These functions operate on the edges of the graph. This functions
* include the ability to add and remove edges.
@@ -131,9 +188,9 @@
* These function allow iteration over the edge set.
*/
//@{
- edge_range edges() const;
- edge_iterator begin_edges() const;
- edge_iterator end_edges() const;
+ // edge_range edges() const;
+ // edge_iterator begin_edges() const;
+ // edge_iterator end_edges() const;
edges_size_type num_edges() const;
//@}
@@ -152,9 +209,13 @@
incident_edges_size_type degree(vertex_descriptor) const;
//@{
- // Property accesors
+ /** @name Property Accessors
+ * Access the properties of the given vertex or edge.
+ */
+ //@{
vertex_properties& operator[](vertex_descriptor);
edge_properties& operator[](edge_descriptor);
+ //@{
private:
property_store _props;
@@ -187,6 +248,44 @@
}
/**
+ * Add a new vertex with the given properties to the graph and map it to the
+ * given key.
+ *
+ * @requires VertexMap<Graph>
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_key const& k, vertex_properties const& vp)
+{
+ return _verts.add(k, vp);
+}
+
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ *
+ * @requires LabeledUniqueVertex<Graph> ???
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_properties const& vp) const
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ return _verts.find(vp);
+}
+
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ *
+ * @requires MappedUniqueVertex<Graph>
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
+undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_key const& k) const
+{
+ return _verts.find(k);
+}
+
+/**
* Disconnect the vertex from the graph. This removes all edges incident to
* the vertex, but will not remove the vertex itself.
*/
@@ -217,6 +316,35 @@
}
/**
+ * Disconnect the vertex having the given properties from the graph.
+ *
+ * @requires UniqueLabeledVertex<Graph>
+ *
+ * @todo What does this do for multiset vertex stores.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ disconnect_vertex(find_vertex(vp));
+}
+
+/**
+ * Disconnect the vertex having the given key from the graph.
+ *
+ * @requires UniqueMappedVertex<Graph>
+ *
+ * @todo What does this do for multimap vertex stores.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_key const& k)
+{
+ disconnect_vertex(find_vertex(k));
+}
+
+/**
* Remove the vertex from the graph. This will disconnect the vertex from the
* graph prior to remove.
*/
@@ -229,6 +357,41 @@
}
/**
+ * Remove the vertex from the graph identified by the given properties.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ disconnect_vertex(vp);
+ _verts.remove(vp);
+}
+
+/**
+ * Remove the vertex from the graph identified by the given key.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
+{
+ disconnect_vertex(k);
+ _verts.remove(k);
+}
+
+/**
+ * Return the key associated with the given vertex. This function is only
+ * available for graphs with mapped vertices.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::vertex_key const&
+undirected_graph<VP,EP,VS,ES>::key(vertex_descriptor v) const
+{
+ return _verts.key(v);
+}
+
+
+/**
* Create an edge, connecting the vertices u and v.
*/
template <BOOST_GRAPH_UG_PARAMS>
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-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -21,14 +21,15 @@
template <template <typename> class Allocator>
struct basic_vertex_list
{
- typedef none key_type;
+ typedef unused key_type;
typedef void* descriptor_type;
template <typename Vertex>
struct store
{
typedef vertex_list_elem<Vertex, Allocator> stored_vertex;
- typedef vertex_list_impl<stored_vertex, Allocator<stored_vertex> > type;
+ typedef Allocator<stored_vertex> allocator_type;
+ typedef vertex_list_impl<stored_vertex, allocator_type > type;
};
};
@@ -83,26 +84,47 @@
// Add/remove vertices.
vertex_descriptor add();
vertex_descriptor add(vertex_properties const& vp);
-
- // Remove vertices.
+ vertex_descriptor find(vertex_properties const& vp);
void remove(vertex_descriptor v);
+ void remove(vertex_properties const& vp);
- // Number of vertices.
- size_type size() const;
-
- // Vertex iteration.
- vertex_range vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- // Vertex accessors.
- vertex_type& vertex(vertex_descriptor);
- vertex_type const& vertex(vertex_descriptor) const;
- vertex_properties& properties(vertex_descriptor);
- vertex_properties const& properties(vertex_descriptor) const;
+ /** Return the number of vertices in the set. */
+ size_type size() const
+ { return _size; }
+
+ /** @name Vertex Iterators */
+ //@{
+ vertex_iterator begin_vertices() const
+ { return _verts.begin(); }
+
+ vertex_iterator end_vertices() const
+ { return _verts.end(); }
+
+ vertex_range vertices() const
+ { return std::make_pair(begin_vertices(), end_vertices()); }
+ //@}
+
+ /** @name Vertex Accessors */
+ //@{
+ vertex_type& vertex(vertex_descriptor v)
+ { return *static_cast<vertex_type*>(v); }
+
+ vertex_type const& vertex(vertex_descriptor v) const
+ { return *static_cast<vertex_type*>(v); }
+ //@}
+
+ /** @name Vertex Properties */
+ //@{
+ vertex_properties& properties(vertex_descriptor v)
+ { return vertex(v).properties(); }
+
+ vertex_properties const& properties(vertex_descriptor v) const
+ { return vertex(v).properties(); }
+ //@}
private:
vertex_store _verts;
+ size_type _size;
};
#define BOOST_GRAPH_VL_PARAMS \
@@ -114,6 +136,7 @@
template <BOOST_GRAPH_VL_PARAMS>
vertex_list_impl<V,A>::vertex_list_impl()
: _verts()
+ , _size(0)
{ }
/**
@@ -140,12 +163,27 @@
typename vertex_list_impl<V,A>::vertex_descriptor
vertex_list_impl<V,A>::add(vertex_properties const& vp)
{
- typename vertex_store::iterator i = _verts.insert(_verts.end(), vertex_type(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.
*
@@ -155,145 +193,26 @@
void
vertex_list_impl<V,A>::remove(vertex_descriptor v)
{
+ --_size;
vertex_type* vp = static_cast<vertex_type*>(v);
_verts.erase(vp->iter);
}
/**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_range
-vertex_list_impl<V,A>::vertices() const
-{
- return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the list.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::begin_vertices() const
-{
- return _verts.begin();
-}
-
-/**
- * Return an iterator past the end of the vertices in the list.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::end_vertices() const
-{
- return _verts.end();
-}
-
-/**
- * Return the number of vertices in the store.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::size_type
-vertex_list_impl<V,A>::size() const
-{
- return _verts.size();
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_type&
-vertex_list_impl<V,A>::vertex(vertex_descriptor v)
-{
- return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_type const&
-vertex_list_impl<V,A>::vertex(vertex_descriptor v) const
-{
- return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get the properties ofthe given vertex.
- */
-template <BOOST_GRAPH_VL_PARAMS>
-typename vertex_list_impl<V,A>::vertex_properties&
-vertex_list_impl<V,A>::properties(vertex_descriptor v)
-{
- return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VL_PARAMS
-
-#if 0
-
-/**
- * Return the number of vertices in the vertex store.
+ * 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)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertices_size_type
-vertex_list_impl<V,A>::num_vertices() const
-{
- return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
- */
-template <typename V, template <typename> class A>
-std::pair<
- typename vertex_list_impl<V,A>::vertex_iterator,
- typename vertex_list_impl<V,A>::vertex_iterator
->
-vertex_list_impl<V,A>::vertices() const
-{
- return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Return the iterator for the begining of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::begin_vertices() const
-{
- return _verts.begin();
-}
-
-/**
- * Return the iterator for the begining of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_iterator
-vertex_list_impl<V,A>::end_vertices() const
-{
- return _verts.end();
-}
-
-
-/**
- * Access the properties ofthe given vertex.
*/
-template <typename V, template <typename> class A>
-typename vertex_list_impl<V,A>::vertex_properties const&
-vertex_list_impl<V,A>::properties(vertex_descriptor v) const
+template <typename V, typename A>
+void
+vertex_list_impl<V,A>::remove(vertex_properties const& vp)
{
- return *vertex(v);
+ remove(find(vp));
}
-#endif
+#undef BOOST_GRAPH_VL_PARAMS
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp 2008-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -1,54 +1,79 @@
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_VERTEX_MAP_HPP
+#ifndef VERTEX_MAP_HPP
+#define VERTEX_MAP_HPP
#include <map>
-#include <boost/graphs/adjacency_list/descriptor.hpp>
-#include <boost/graphs/adjacency_list/vs/mapped_vertex_iterator.hpp>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
-
// Forward declarations
-template <typename V, typename K, template <typename> class C, template <typename> class A> class vertex_map_elem;
-template <typename V, typename K, typename C, typename A> class vertex_map_impl;
+template <typename, typename, typename, template <typename> class> class vertex_map_elem;
+template <typename, typename, typename, typename> class vertex_map_impl;
-template <typename Key, template <typename> class Compare, template <typename> class Allocator>
+/**
+ * This metafunction defines the implementation requirements of a mapping of
+ * vertices to the keys that describe them. This is function takes three
+ * parameters: the type of key, a comparator template, and vertex allocator.
+ *
+ * The Compare parameter must be a unary template class rather than a fully
+ * instantiated type. This makes it easier to pass arbitrary template functions
+ * (e.g., less and greater) instead of instantiated types.
+ *
+ * The Alloc parameter is also a unary template class. In this case, the caller
+ * does not know the final type of the allocator object. It us ultimately
+ * instantiated as an allocator of key/vertex pairs.
+ *
+ * @param Key The key type of the vertex map can be any LessThanComparable type.
+ * @param Compare A unary template class that implements a comparison of keys.
+ * @param Alloc An allocator for key/value pairs of the underliyng map.
+ */
+template <
+ typename Key,
+ template <typename> class Compare,
+ template <typename> class Alloc>
struct basic_vertex_map
{
- typedef basic_vertex_descriptor<void*> descriptor_type;
+ typedef Key key_type;
+ typedef void* descriptor_type;
template <typename Vertex>
struct store
{
- typedef vertex_map_elem<Vertex, Key, Compare, Allocator> stored_vertex;
- typedef std::pair<const Key, stored_vertex> stored_value;
- typedef vertex_map_impl<stored_vertex, Key, Compare<Key>, Allocator<stored_value> > type;
+ // Build the key comparator (note: independent of vertex!)
+ typedef Compare<key_type> compare_type;
+
+ // Build the stored vertex type.
+ typedef vertex_map_elem<Vertex, Key, compare_type, Alloc> stored_vertex;
+
+ // Build the allocator
+ typedef Alloc<stored_vertex> allocator_type;
+
+ // Build the underlying store
+ typedef vertex_map_impl<stored_vertex, key_type, compare_type, allocator_type> type;
};
};
+/**
+ * The most common vertex set allows parameterization over the comparator used
+ * to sort vertices and uses the standard omnibus allocator.
+ */
template <typename Key, template <typename> class Compare = std::less>
struct vertex_map : basic_vertex_map<Key, Compare, std::allocator> { };
-// Extend the notion of a vertex for set storage so that we can store each
-// vertex's iterator with current vertex. This is used to provide constant
-// time access to the correct position in the underliying store.
+/**
+ * Extend the notion of a vertex for map storage so that we can store each
+ * vertex's iterator with current vertex. This is used to provide constant
+ * time access to the correct position in the underliying store.
+ */
template <
- typename Vertex,
- typename Key,
- template <typename> class Compare,
- template <typename> class Alloc
- >
+ typename Vertex,
+ typename Key,
+ typename Compare,
+ template <typename> class Alloc>
class vertex_map_elem
: public Vertex
{
typedef vertex_map_elem<Vertex, Key, Compare, Alloc> this_type;
public:
- typedef typename std::map<
- Key, this_type, Compare<Key>, Alloc< std::pair<Key, this_type> >
- >::iterator iterator;
+ typedef typename std::map<Key, this_type, Compare, Alloc<this_type> >::iterator iterator;
inline vertex_map_elem(typename Vertex::vertex_properties const& vp)
: Vertex(vp)
@@ -59,272 +84,157 @@
};
/**
- * The vertex_map_impl provides a list-based implementation of vertex storage
- * for an adjacency list. List-based storage is best for graphs with
- * unidentified vertices and requirements for fast vertex addition and deletion.
- *
- * This class requires that the graph's vertex properties be less than
- * comparable since the ordering of vertices in the set is based on that
- * implementation of the ordering. Note that the vertex type provides a built
- * in ordering using operator<() that delegates the call to the properties.
+ * Implementation of the vertex set. This requires that vertices (actually
+ * their properties) are less-than comparable.
*
- * Adding vertices to a list does not invalidate any vertex or edge descriptors.
- * Removing vertices will invalidate descriptors referencing the removed
- * vertex. All insertions and removals occur in constant time. However, getting
- * the number of vertices is linear.
- *
- * @require LessThanComparable<Vertex::properties_type>
+ * @param Vertex The vertex type stored by the class.
+ * @param Key The type of key mapping to vertices.
+ * @param Compare An ordering over keys.
+ * @param Alloc The allocator for Key/Vertex pairs.
*/
template <typename Vertex, typename Key, typename Compare, typename Allocator>
class vertex_map_impl
{
typedef std::map<Key, Vertex, Compare, Allocator> vertex_store;
public:
- typedef Key key_type;
+ typedef void* vertex_descriptor;
+
typedef Vertex vertex_type;
typedef typename Vertex::vertex_properties vertex_properties;
- typedef typename Vertex::vertex_descriptor vertex_descriptor;
- typedef typename vertex_store::size_type vertices_size_type;
- typedef mapped_vertex_iterator<vertex_store> vertex_iterator;
+ typedef typename vertex_store::size_type size_type;
+ typedef typename vertex_store::iterator iterator;
+ typedef typename vertex_store::const_iterator const_iterator;
+
+ typedef Key key_type;
+
+
+ typedef simple_vertex_iterator<vertex_store> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
// Constructors
vertex_map_impl();
- // Add or insert a vertex.
- vertex_descriptor add_vertex(key_type const& k, vertex_properties const& vp);
- std::pair<vertex_descriptor, bool> insert_vertex(key_type const& k, vertex_properties const& vp);
-
- // Remove a vertex.
- void remove_vertex(vertex_descriptor v);
-
- // Find a vertex
- vertex_descriptor find_vertex(key_type const& k) const;
-
- // Number of vertices.
- vertices_size_type num_vertices() const;
-
- // Vertex iteration.
- std::pair<vertex_iterator, vertex_iterator> vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- // Vertex accessors.
- vertex_type& vertex(vertex_descriptor v);
- vertex_type const& vertex(vertex_descriptor v) const;
- vertex_descriptor descriptor(vertex_type const& v) const;
- key_type const& key(vertex_descriptor v) const;
-
- // Property accessors.
- vertex_properties& properties(vertex_descriptor v);
- vertex_properties const& properties(vertex_descriptor v) const;
-
+ vertex_descriptor add(key_type const& k, vertex_properties const& vp);
+ vertex_descriptor find(key_type const& vp) const;
+ void remove(vertex_descriptor);
+ void remove(key_type const&);
+
+ key_type const& key(vertex_descriptor) const;
+
+ /** Return the number of vertices in the map. */
+ inline size_type size() const
+ { return _verts.size(); }
+
+ /** @name Vertex Iteration */
+ //@{
+ inline vertex_iterator begin_vertices() const
+ { return _verts.begin(); }
+
+ inline vertex_iterator end_vertices() const
+ { return _verts.end(); }
+
+ vertex_range vertices() const
+ { return std::make_pair(begin_vertices(), end_vertices()); }
+ //@}
+
+ /** @name Vertex Accessors */
+ //@{
+ vertex_type& vertex(vertex_descriptor v)
+ { return *static_cast<vertex_type*>(v); }
+
+ vertex_type const& vertex(vertex_descriptor v) const
+ { return *static_cast<vertex_type*>(v); }
+ //@}
+
+ /** @name Property Accessors */
+ //@{
+ vertex_properties& properties(vertex_descriptor v)
+ { return vertex(v).properties(); }
+
+ vertex_properties const& properties(vertex_descriptor v) const
+ { return vertex(v).properties(); }
+ //@}
private:
vertex_store _verts;
};
-#define BOOST_GRAPHS_VM_PARAMS \
- typename V, typename K, typename C, typename A
-
-template <BOOST_GRAPHS_VM_PARAMS>
+template <typename V, typename K, typename C, typename A>
vertex_map_impl<V,K,C,A>::vertex_map_impl()
: _verts()
{ }
-#undef BOOST_GRAPHS_VM_PARAMS
-
-#if 0
-
/**
- * Add a vertex to the store with the key and properties. If the key is mapped
- * to a vertex, do nothing. Return a descriptor to the existing or new vertex.
+ * Add the vertex with the given properties. If there is already a vertex with
+ * these properties, then this returns the descriptor of the existing vertex
+ * and does not insert a new vertex.
*
- * @complexity O(log(V))
+ * @complexity O(lg(V))
*/
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::add_vertex(const K& k, vertex_properties const& vp)
-{
- return insert_vertex(k, vp).first;
-}
-
-/**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties and return a descriptor to the
- * inserted vertex. If the vertex exists, the second element of the returned
- * pair is false.
- *
- * @complexity O(log(V))
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-std::pair<typename vertex_map_impl<V,K,C,A>::vertex_descriptor, bool>
-vertex_map_impl<V,K,C,A>::insert_vertex(key_type const& k, vertex_properties const& vp)
+vertex_map_impl<V,K,C,A>::add(key_type const& k, vertex_properties const& vp)
{
- std::pair<vertex_descriptor, bool> ret;
- std::pair<typename vertex_store::iterator, bool> ins =
- _verts.insert(make_pair(k, vertex_type(vp)));
+ // Try to insert the vertex into the map.
+ vertex_descriptor ret;
+ std::pair<iterator, bool> ins = _verts.insert(std::make_pair(k, vertex_type(vp)));
if(ins.second) {
- // Yikes... so dirty. Normally, we can't modify an object via its
- // iterator since that would indicate a change to the key. However,
- // the key is based on the properties of the vertex, not the part of
- // the object that we're going to change.
vertex_type& v = ins.first->second;
v.iter = ins.first;
- ret.first = &v;
+ ret = &v;
}
else {
- ret.first = &(ins.first->second);
+ ret = &ins.first->second;
}
- ret.second = ins.second;
-
return ret;
}
/**
- * Find a vertex given a key. If the key does not exist, return an invalid
- * descriptor.
+ * Find the vertex in the map with the given key.
+ *
+ * @complexity O(log(V))
*/
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::find_vertex(key_type const& k) const
+vertex_map_impl<V,K,C,A>::find(key_type const& k) const
{
- vertex_descriptor ret;
- typename vertex_store::const_iterator iter = _verts.find(k);
- if(iter != _verts.end()) {
- // Because the function is const, the resulting vertex should also be
- // const. Unfortunately, this isn't really going to work for me.
- vertex_type& v = const_cast<vertex_type&>(iter->second);
- ret = &v;
- }
- return ret;
+ return &const_cast<vertex_type&>(_verts.find(k)->second);
}
/**
- * Remove a vertex from the store.
- *
- * Removing a vertex will invalidate all vertex and edge descriptors.
+ * Remove a vertex from the map. Removing a vertex will invalidate all
+ * descriptors and iterators to the vertex being removed.
*
- * @complexity O(|V|)
+ * @complexity O(log(V))
*/
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
void
-vertex_map_impl<V,K,C,A>::remove_vertex(vertex_descriptor v)
+vertex_map_impl<V,K,C,A>::remove(vertex_descriptor v)
{
- vertex_type* vp = static_cast<vertex_type*>(v);
- _verts.erase(vp->iter);
+ _verts.erase(vertex(v).iter);
}
/**
- * Return the number of vertices in the vertex store.
+ * Remove the vertex with the given key from the map. This operation finds
+ * the vertex before removing it.
*
- * @complexity O(V)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertices_size_type
-vertex_map_impl<V,K,C,A>::num_vertices() const
-{
- return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-std::pair<
- typename vertex_map_impl<V,K,C,A>::vertex_iterator,
- typename vertex_map_impl<V,K,C,A>::vertex_iterator
->
-vertex_map_impl<V,K,C,A>::vertices() const
-{
- return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Get a vertex iterator to the beginning iterator of the vertices.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_iterator
-vertex_map_impl<V,K,C,A>::begin_vertices() const
-{ return _verts.begin(); }
-
-/**
- * Get a vertex iterator to an iterator past the end of the vertices.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_iterator
-vertex_map_impl<V,K,C,A>::end_vertices() const
-{ return _verts.end(); }
-
-/**
- * Get access to the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_type&
-vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v)
-{
- return *static_cast<vertex_type*>(v.desc);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_type const&
-vertex_map_impl<V,K,C,A>::vertex(vertex_descriptor v) const
-{
- return *static_cast<vertex_type*>(v.desc);
-}
-
-/**
- * Return a descriptor for the given vertex.
+ * @complexity O(log(V))
*/
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_descriptor
-vertex_map_impl<V,K,C,A>::descriptor(vertex_type const& v) const
+template <typename V, typename K, typename C, typename A>
+void
+vertex_map_impl<V,K,C,A>::remove(key_type const& k)
{
- return &const_cast<vertex_type&>(v);
+ remove(find(k));
}
/**
- * Get the key of a vertex descriptor.
+ * Return the key for the given vertex.
*/
-template <typename V, typename K, template <typename> class C, template <typename> class A>
+template <typename V, typename K, typename C, typename A>
typename vertex_map_impl<V,K,C,A>::key_type const&
vertex_map_impl<V,K,C,A>::key(vertex_descriptor v) const
{
- vertex_type& vert = *static_cast<vertex_type*>(v.desc);
- return vert.iter->first;
+ return vertex(v).iter->first;
}
-
-/**
- * Get the properties of the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_properties&
-vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v)
-{
- return *vertex(v);
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <typename V, typename K, template <typename> class C, template <typename> class A>
-typename vertex_map_impl<V,K,C,A>::vertex_properties const&
-vertex_map_impl<V,K,C,A>::properties(vertex_descriptor v) const
-{
- return *vertex(v);
-}
-
-#endif
-
-} /* namespace adj_list */
-} /* namesapce graphs */
-} /* namespace boost */
-
#endif
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-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -6,25 +6,45 @@
// Forward declarations
template <typename, template <typename> class, template <typename> class> class vertex_set_elem;
+template <typename, typename> class vertex_set_compare;
template <typename, typename, typename> class vertex_set_impl;
/**
* This metafunction defines the implementation requirements of a set of
- * verties.
+ * vertices. This function allos the parameterization of vertex comparability
+ * by allowing the caller to specify the comparator.
+ *
+ * The Compare parameter must be a unary template class. This lets us specify
+ * arbitrary function objects by name without having to explicitly instantiate
+ * them.
+ *
+ * The Alloc parameter is also a unary template class. In this case, the caller
+ * does not actually know what the final instantiated type is going to be.
+ *
+ * @param Compare A unary template class that compares vertex properties.
+ * @param Alloc A unary template class that allocates vertices.
*/
template <template <typename> class Compare, template <typename> class Alloc>
struct basic_vertex_set
{
- typedef none key_type;
+ typedef unused key_type;
typedef void* descriptor_type;
template <typename Vertex>
struct store
{
+ // Build the stored vertex type.
typedef vertex_set_elem<Vertex, Compare, Alloc> stored_vertex;
- typedef Compare<stored_vertex> comp_type;
- typedef Alloc<stored_vertex> alloc_type;
- typedef vertex_set_impl<stored_vertex, comp_type, alloc_type> type;
+
+ // Build the vertex comparator.
+ typedef Compare<typename stored_vertex::vertex_properties> vertex_compare;
+ typedef vertex_set_compare<stored_vertex, vertex_compare> compare_type;
+
+ // Build the allocator.
+ typedef Alloc<stored_vertex> allocator_type;
+
+ // Build the vertex set implementation.
+ typedef vertex_set_impl<stored_vertex, compare_type, allocator_type> type;
};
};
@@ -57,15 +77,42 @@
, iter()
{ }
- inline bool operator<(this_type const& x) const
- { return Vertex::operator<(static_cast<Vertex const&>(x)); }
-
iterator iter;
};
/**
+ * A forwarding comparator for the vertex forwards the comparison to the given
+ * comparator. This type is used internally to forward comparisons of vertices
+ * to the property comparison provided by the edge set parameter.
+ *
+ * @param StoredVertex The type of vertex being compared
+ * @param Compare An ordering over vertex properties.
+ */
+template <typename StoredVertex, typename Compare>
+struct vertex_set_compare
+{
+ inline vertex_set_compare()
+ : comp(Compare())
+ { }
+
+ inline vertex_set_compare(vertex_set_compare const& x)
+ : comp(x.comp)
+ { }
+
+ inline bool operator()(StoredVertex const& a, StoredVertex const& b) const
+ { return comp(a.properties(), b.properties()); }
+
+ Compare comp;
+};
+
+
+/**
* Implementation of the vertex set. This requires that vertices (actually
* their properties) are less-than comparable.
+ *
+ * @param Vertex The type of vertex stored by the set.
+ * @param Compare An ordering of vertices (should delegate to properties).
+ * @param Allocator The allocator for stored vertices.
*/
template <typename Vertex, typename Compare, typename Allocator>
class vertex_set_impl
@@ -89,27 +136,43 @@
// Add vertices. Note that you can't add without properties.
vertex_descriptor add(vertex_properties const& vp);
-
- // Remove vertices.
+ vertex_descriptor find(vertex_properties const& vp) const;
void remove(vertex_descriptor v);
+ void remove(vertex_properties const& v);
- // Find the given vertex.
- const_iterator find(vertex_descriptor v) const;
- const_iterator find(vertex_properties const& vp);
-
- // Number of vertices.
- size_type size() const;
-
- // Vertex iteration.
- vertex_range vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- // Vertex accessors.
- vertex_type& vertex(vertex_descriptor);
- vertex_type const& vertex(vertex_descriptor) const;
- vertex_properties& properties(vertex_descriptor);
- vertex_properties const& properties(vertex_descriptor) const;
+ /** Return the number of vertices in the set. */
+ inline size_type size() const
+ { return _verts.size(); }
+
+ /** @name Vertex Iteration */
+ //@{
+ vertex_iterator begin_vertices() const
+ { return _verts.begin(); }
+
+ vertex_iterator end_vertices() const
+ { return _verts.end(); }
+
+ vertex_range vertices() const
+ { return std::make_pair(begin_vertices(), end_vertices()); }
+ //@}
+
+ /** @name Vertex Accessors */
+ //@{
+ vertex_type& vertex(vertex_descriptor v)
+ { return *static_cast<vertex_type*>(v); }
+
+ vertex_type const& vertex(vertex_descriptor v) const
+ { return *static_cast<vertex_type*>(v); }
+ //@}
+
+ /** @name Property Accessors */
+ //@{
+ vertex_properties& properties(vertex_descriptor v)
+ { return vertex(v).properties(); }
+
+ vertex_properties const& properties(vertex_descriptor v) const
+ { return vertex(v).properties(); }
+ //@{
private:
vertex_store _verts;
@@ -150,240 +213,43 @@
}
/**
- * Remove a vertex from the set. Removing a vertex will invalidate all
- * descriptors and iterators to the vertex being removed.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-void
-vertex_set_impl<V,C,A>::remove(vertex_descriptor v)
-{
- vertex_type* vp = static_cast<vertex_type*>(v);
- _verts.erase(vp->iter);
-}
-
-/**
- * Find a vertex in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::const_iterator
-vertex_set_impl<V,C,A>::find(vertex_descriptor v) const
-{
- return find(vertex(v).properties());
-}
-
-/**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_range
-vertex_set_impl<V,C,A>::vertices() const
-{
- return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::begin_vertices() const
-{
- return _verts.begin();
-}
-
-/**
- * Return an iterator past the end of the vertices in the set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::end_vertices() const
-{
- return _verts.end();
-}
-
-/**
- * Return the number of vertices in this vertex set.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::size_type
-vertex_set_impl<V,C,A>::size() const
-{
- return _verts.size();
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_type&
-vertex_set_impl<V,C,A>::vertex(vertex_descriptor v)
-{
- return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get access to the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_type const&
-vertex_set_impl<V,C,A>::vertex(vertex_descriptor v) const
-{
- return *static_cast<vertex_type*>(v);
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_properties&
-vertex_set_impl<V,C,A>::properties(vertex_descriptor v)
-{
- return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VS_PARAMS
-
-#if 0
-
-/**
- * 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.
+ * Find the descriptor with the given properties.
*
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::add_vertex(vertex_properties const& vp)
+vertex_set_impl<V,C,A>::find(vertex_properties const& vp) const
{
- return insert_vertex(vp).first;
+ return &const_cast<vertex_type&>(*_verts.find(vp));
}
/**
- * Add a vertex to the store with the given properties. If not specified, the
- * vertex is created with default properties and return a descriptor to the
- * inserted vertex. If the vertex exists, the second element of the returned
- * pair is false.
+ * Remove a vertex from the set. Removing a vertex will invalidate all
+ * descriptors and iterators to the vertex being removed.
*
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
-std::pair<typename vertex_set_impl<V,C,A>::vertex_descriptor, bool>
-vertex_set_impl<V,C,A>::insert_vertex(vertex_properties const& vp)
+void
+vertex_set_impl<V,C,A>::remove(vertex_descriptor v)
{
- std::pair<vertex_descriptor, bool> ret;
- std::pair<typename vertex_store::iterator, bool> ins =
- _verts.insert(vertex_type(vp));
- if(ins.second) {
- // Yikes... so dirty. Normally, we can't modify an object via its
- // iterator since that would indicate a change to the key. However,
- // the key is based on the properties of the vertex, not the part of
- // the object that we're going to change.
- vertex_type& v = const_cast<vertex_type&>(*(ins.first));
- v.iter = ins.first;
- ret.first = &v;
- }
- else {
- ret.first = &const_cast<vertex_type&>(*ins.first);
- }
- ret.second = ins.second;
-
- return ret;
+ _verts.erase(vertex(v).iter);
}
/**
- * Remove the vertex identified by the given properties from the store.
+ * Remove the vertex identified by the given properties from the set. This
+ * finds the vertex before removing it.
*
* @complexity O(log(V))
*/
template <BOOST_GRAPH_VS_PARAMS>
void
-vertex_set_impl<V,C,A>::remove_vertex(vertex_properties const& vp)
-{4
- remove_vertex(find(vp));
-}
-
-/**
- * Find a vertex by its properties.
- *
- * @complexity O(log(V))
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_descriptor
-vertex_set_impl<V,C,A>::find_vertex(vertex_properties const& vp) const
-{
- // This is a little gross... We have to tempoararily construct an empty
- // vertex with the given properties in order for the find operations to
- // work.
- vertex_descriptor ret;
- typename vertex_store::iterator iter = _verts.find(vertex_type(vp));
- if(iter != _verts.end()) {
- ret = &const_cast<vertex_type&>(*iter);
- }
- return ret;
-}
-
-/**
- * Return the number of vertices in the vertex store.
- *
- * @complexity O(V)
- *
- * @todo I'm not sure about the interface I'd like to build for list storage.
- * If we don't include a lot of splice-style operations, then it's not a big
- * deal to manage the size of this list internally.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertices_size_type
-vertex_set_impl<V,C,A>::num_vertices() const
+vertex_set_impl<V,C,A>::remove(vertex_properties const& vp)
{
- return _verts.size();
+ remove(find(vp));
}
-/**
- * Return the iterator range for the graph.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-std::pair<
- typename vertex_set_impl<V,C,A>::vertex_iterator,
- typename vertex_set_impl<V,C,A>::vertex_iterator
->
-vertex_set_impl<V,C,A>::vertices() const
-{
- return std::make_pair(_verts.begin(), _verts.end());
-}
-
-/**
- * Get a vertex iterator to the beginning iterator of the vertices.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::begin_vertices() const
-{
- return _verts.begin();
-}
-
-/**
- * Get a vertex iterator to an iterator past the end of the vertices.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_iterator
-vertex_set_impl<V,C,A>::end_vertices() const
-{
- return _verts.end();
-}
-
-/**
- * Access the properties of the given vertex.
- */
-template <BOOST_GRAPH_VS_PARAMS>
-typename vertex_set_impl<V,C,A>::vertex_properties const&
-vertex_set_impl<V,C,A>::properties(vertex_descriptor v) const
-{
- return *vertex(v);
-}
-
-#endif
+#undef BOOST_GRAPH_VS_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-06-19 08:06:49 EDT (Thu, 19 Jun 2008)
@@ -3,17 +3,25 @@
#define VERTEX_VECTOR_HPP
#include <vector>
+#include <algorithm>
// Forward declarations
template <typename V, typename A> struct vertex_vector_impl;
/**
+ * The vertex vector stores vertices in a vector, allowing for fast inserts
+ * and iteration, but slow finds and removals.
*
+ * The Alloc parameter is a unary template class responsible for allocating
+ * the stored vertices. We use a template rather than a type because the caller
+ * does not know the actual types being allocated.
+ *
+ * @param Alloc A unary template class that will allocate stored vertices.
*/
-template <template <typename> class Allocator>
+template <template <typename> class Alloc>
struct basic_vertex_vector
{
- typedef none key_type;
+ typedef unused key_type;
typedef std::size_t descriptor_type;
// The store metafunction generates the type used to store vertices in
@@ -22,7 +30,9 @@
template <typename Vertex>
struct store
{
- typedef vertex_vector_impl<Vertex, Allocator<Vertex> > type;
+ typedef Vertex stored_vertex;
+ typedef Alloc<stored_vertex> allocator_type;
+ typedef vertex_vector_impl<stored_vertex, allocator_type> type;
};
};
@@ -59,32 +69,54 @@
// Constructors
vertex_vector_impl();
- // Add/remove vertex.
+ /** @name Add Vertex */
+ //@{
vertex_descriptor add();
- vertex_descriptor add(vertex_properties const& vp);
+ vertex_descriptor add(vertex_properties const&);
+ //@}
- // Number of vertices.
- size_type size() const;
+ /** Return the vertex with the given properties */
+ vertex_descriptor find(vertex_properties const&) const;
- // Vertex iteration.
- vertex_range vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- // Vertex/vertex property accessors.
- vertex_type& vertex(vertex_descriptor v);
- vertex_type const& vertex(vertex_descriptor v) const;
- vertex_properties& properties(vertex_descriptor);
- vertex_properties const& properties(vertex_descriptor) const;
+ /** Rerturn the number of vertices in the vector. */
+ size_type size() const
+ { return _verts.size(); }
+
+ /** @name Vertex Iterators */
+ //@{
+ vertex_iterator begin_vertices() const
+ { return _verts.begin(); }
+
+ vertex_iterator end_vertices() const
+ { return _verts.end(); }
+
+ vertex_range vertices() const
+ { return std::make_pair(begin_vertices(), end_vertices()); }
+ //@}
+
+ /** @name Vertex Accessors */
+ //@{
+ vertex_type& vertex(vertex_descriptor v)
+ { return _verts[v]; }
+
+ vertex_type const& vertex(vertex_descriptor v) const
+ { return _verts[v]; }
+ //@{
+
+ /** @name Property Accessors */
+ //@{
+ vertex_properties& properties(vertex_descriptor v)
+ { return vertex(v).properties(); }
+
+ vertex_properties const& properties(vertex_descriptor v) const
+ { return vertex(v).properties(); }
+ //@{
private:
vertex_store _verts;
};
-#define BOOST_GRAPH_VV_PARAMS \
- typename V, typename A
-
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
vertex_vector_impl<V,A>::vertex_vector_impl()
: _verts()
{ }
@@ -94,9 +126,9 @@
* the descriptor to the added vertex. Adding a vertex does not invalidate
* any vertices or edges.
*
- * @complexity O(1) amortized
+ * @complexity O(~1)
*/
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
typename vertex_vector_impl<V,A>::vertex_descriptor
vertex_vector_impl<V,A>::add()
{
@@ -107,9 +139,9 @@
* Add a vertex to the store with the given properties. Adding a vertex does
* not invalidate any other descriptors.
*
- * @complexity O(1) amortized
+ * @complexity O(~1)
*/
-template <BOOST_GRAPH_VV_PARAMS>
+template <typename V, typename A>
typename vertex_vector_impl<V,A>::vertex_descriptor
vertex_vector_impl<V,A>::add(vertex_properties const& vp)
{
@@ -119,135 +151,16 @@
}
/**
- * Return an iterator range over the vertices in this graph.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_range
-vertex_vector_impl<V,A>::vertices() const
-{
- return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Return an iterator to the first vertex in the vector.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::begin_vertices() const
-{
- return vertex_iterator(_verts, _verts.begin());
-}
-
-/**
- * Return an iterator past the end of the vertices in the vector.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::end_vertices() const
-{
- return vertex_iterator(_verts, _verts.end());
-}
-
-/**
- * Return the number of vertices in the store.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::size_type
-vertex_vector_impl<V,A>::size() const
-{
- return _verts.size();
-}
-
-/**
- * Get access to the underlying vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_type&
-vertex_vector_impl<V,A>::vertex(vertex_descriptor v)
-{
- return _verts[v];
-}
-
-/**
- * Get access to the underlying vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_type const&
-vertex_vector_impl<V,A>::vertex(vertex_descriptor v) const
-{
- return _verts[v];
-}
-
-/**
- * Get the properties of the given vertex.
- */
-template <BOOST_GRAPH_VV_PARAMS>
-typename vertex_vector_impl<V,A>::vertex_properties&
-vertex_vector_impl<V,A>::properties(vertex_descriptor v)
-{
- return vertex(v).properties();
-}
-
-#undef BOOST_GRAPH_VV_PARAMS
-
-#if 0
-
-/**
- * Return the number of vertices in the vertex store.
+ * Find the vertex with the given properties.
*
- * @complexity constant
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertices_size_type
-vertex_vector_impl<V,A>::num_vertices() const
-{
- return _verts.size();
-}
-
-/**
- * Return the iterator range for the graph.
+ * @complexity O(V)
*/
-template <typename V, template <typename> class A>
-std::pair<
- typename vertex_vector_impl<V,A>::vertex_iterator,
- typename vertex_vector_impl<V,A>::vertex_iterator
->
-vertex_vector_impl<V,A>::vertices() const
-{
- return std::make_pair(begin_vertices(), end_vertices());
-}
-
-/**
- * Get an iterator to the beginning of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::begin_vertices() const
-{
- return vertex_iterator(_verts, _verts.begin());
-}
-
-/**
- * Get an iterator past the end of the vertices.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_iterator
-vertex_vector_impl<V,A>::end_vertices() const
-{
- return vertex_iterator(_verts, _verts.end());
-}
-
-
-/**
- * Get access to the properties of the given vertex.
- */
-template <typename V, template <typename> class A>
-typename vertex_vector_impl<V,A>::vertex_properties const&
-vertex_vector_impl<V,A>::properties(vertex_descriptor v) const
+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 *vertex(v);
+ return std::distance(_verts.begin(),
+ std::find(_verts.begin(), _verts.end(), vp));
}
#endif
-
-#endif