|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49795 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: . include/boost include/boost/graphs include/boost/graphs/adjacency_list test
From: asutton_at_[hidden]
Date: 2008-11-16 11:25:25
Author: asutton
Date: 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
New Revision: 49795
URL: http://svn.boost.org/trac/boost/changeset/49795
Log:
Seriously started rewriting all of the vertex container stuff.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/CMakeLists.txt | 9 ++
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/containers.hpp | 19 +++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp | 118 ------------------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp | 128 +++++----------------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 74 ++++++++++++++++++++--
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp | 113 -----------------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/utility.hpp | 23 -------
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt | 5
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp | 28 +++++++-
9 files changed, 136 insertions(+), 381 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/CMakeLists.txt
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/CMakeLists.txt (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/CMakeLists.txt 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -16,6 +16,15 @@
include(BoostDocs)
include(BoostTesting)
+# This is a substitute for add_executable, that automatically adds somem flags
+# to the executable.
+# TODO Make this work better with Boost.Build stuff.
+macro(add_exec name)
+ add_executable(${name} ${ARGN})
+ set_target_properties(${name} PROPERTIES COMPILE_FLAGS "-Wall --std=c++0x")
+endmacro()
+
+
# Define the library project
# TODO: This doesn't actually seem to do very much if we're out of the build.
boost_library_project(
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/containers.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/containers.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/containers.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -258,17 +258,30 @@
*/
template <typename Container, typename T>
inline typename Container::iterator
-insert(Container& c, T const& x)
+container_insert(Container& c, T const& x)
{ return detail::dispatch_insert(c, x, container_category(c)); }
+/** @name Find
+ * Find the first instance in the cotnainer that is equivalent to x.
+ */
+//@{
template <typename Container, typename T>
inline typename Container::iterator
-find(Container& c, T const& x)
+container_find(Container& c, T const& x)
{ return detail::dispatch_find(c, x, container_category(c)); }
+template <typename Container, typename T>
+inline typename Container::const_iterator
+container_find(Container const& c, T const& x)
+{ return detail::dispatch_find(c, x, container_category(c)); }
+//@}
+
+/**
+ * Erase the element in the container pointed to by the iterator i.
+ */
template <typename Container>
void
-erase(Container& c, typename Container::iterator i)
+container_erase(Container& c, typename Container::iterator i)
{ c.erase(i); }
} /* namespace boost */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -5,10 +5,8 @@
#include <list>
#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
#include <boost/counted_list.hpp>
#include <boost/graphs/adjacency_list/vertex_store.hpp>
-#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -16,8 +14,7 @@
template <typename, typename> class vertices_list;
/**
- * This metafunction defines the basic elements of a vertex list. This builds
- * the list on a counted_list over the std::list class.
+ * @param Alloc A unary template class that will allocate stored vertices.
*/
template <template <typename> class Alloc = std::allocator>
struct vertex_list
@@ -50,119 +47,6 @@
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
};
-/**
- * The implementation of the vertex list.
- *
- * @param Vertex The type of stored vertex.
- * @param Alloc The allocator for stored vertices.
- */
-template <typename Vertex, typename Alloc>
-class vertices_list
-{
-public:
- typedef std::list<Vertex, Alloc> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_label vertex_label;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- // Constructors
- inline vertices_list()
- : _verts(), _size(0)
- { }
-
- /** @name Add Vertex
- * Add a vertex to the store with the given label (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- //@{
- inline vertex_descriptor add()
- { return add(vertex_label()); }
-
- inline vertex_descriptor add(vertex_label const& vp)
- {
- ++_size;
- iterator i = insert(_verts, vertex_type(vp));
- return make_descriptor(_verts, i);
- }
- //@}
-
- /** Find the vertex with the given label. */
- inline vertex_descriptor find(vertex_label const& vp)
- {
- iterator i = std::find_if(_verts.begin(), _verts.end(), find_label(vp));
- return make_descriptor(_verts, i);
- }
-
- /** @name Remove Vertex
- * Remove the given vertex from the vertex store. This will probably break
- * if the descriptor is invalid.
- */
- //@{
- inline void remove(vertex_descriptor v)
- {
- erase(_verts, make_iterator(_verts, v));
- --_size;
- }
-
- inline void remove(vertex_label const& vp)
- { remove(find(vp)); }
- //@}
-
- /** Return the number of vertices in the set. */
- inline size_type size() const
- { return _size; }
-
- /** @name Vertex Iterators
- * There are two sets of iterators here: those that provide iterators that
- * dereference as descriptors and those that dereference as vertices.
- */
- //@{
- inline vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- inline vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- inline vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return *make_iterator(_verts, v); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Vertex Properties */
- //@{
- vertex_label& label(vertex_descriptor v)
- { return vertex(v).label(); }
-
- vertex_label const& label(vertex_descriptor v) const
- { return vertex(v).label(); }
- //@}
-
-private:
- mutable store_type _verts;
- size_type _size;
-};
-
} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -5,9 +5,8 @@
#include <set>
#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
+#include <boost/graphs/label.hpp>
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -15,17 +14,6 @@
template <typename, typename, typename> class vertices_set;
/**
- * This metafunction defines the implementation requirements of a set of
- * 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 label.
* @param Alloc A unary template class that allocates vertices.
*/
@@ -39,113 +27,31 @@
typedef std::set<int, Compare<int>, Alloc<int>> dummy;
typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
- // This metafunction generates the underlying vertex store implementation.
template <typename Vertex>
- struct store
+ struct vertex_store
{
+ private:
typedef Alloc<Vertex> allocator;
- typedef label_comparator<Compare<typename Vertex::vertex_label>> compare;
- typedef vertices_set<Vertex, compare, allocator> type;
+ typedef typename label_traits<Vertex>::label_type label_type;
+ typedef labelled_compare<Vertex, Compare<label_type>> compare;
+ public:
+ typedef std::set<Vertex, compare, allocator> type;
};
};
-/**
- * Implementation of the vertex set. This requires that vertices (actually
- * their label) are less-than comparable.
- *
- * @param Vertex The type of vertex stored by the set.
- * @param Compare An ordering of vertices (should delegate to label).
- * @param Allocator The allocator for stored vertices.
- */
-template <typename Vertex, typename Compare, typename Allocator>
-class vertices_set
+template <typename T, typename A, typename C>
+struct vertex_store_traits<std::set<T,A,C>>
{
+private:
+ typedef std::vector<T,A> base_type;
public:
- typedef std::set<Vertex, Compare, Allocator> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_label vertex_label;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- inline vertices_set()
- : _verts()
- { }
-
- /**
- * Add a vertex to the store with the given label (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- inline vertex_descriptor add(vertex_label const& vp)
- { return make_descriptor(_verts, insert(_verts, vertex_type(vp))); }
-
- /** Find the vertex with the given label. */
- inline vertex_descriptor find(vertex_label const& vp) const
- { return make_descriptor(_verts, _verts.find(vp)); }
-
- /** @name Remove Vertex
- * Remove the given vertex or the one identified by the given label.
- */
- //@{
- inline void remove(vertex_descriptor v)
- {
- iterator i = make_iterator(_verts, v);
- erase(_verts, make_iterator(_verts, v));
- }
-
- inline void remove(vertex_label const& v)
- { remove(find(v)); }
- //@}
-
- /** Return the number of vertices in the set. */
- inline size_type size() const
- { return _verts.size(); }
-
- /** @name Vertex Iteration */
- //@{
- inline vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- inline vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return const_cast<vertex_type&>(*make_iterator(_verts, v)); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Property Accessors */
- //@{
- vertex_label& label(vertex_descriptor v)
- { return vertex(v).label(); }
-
- vertex_label const& label(vertex_descriptor v) const
- { return vertex(v).label(); }
- //@{
+ typedef typename base_type::iterator store_iterator;
-private:
- mutable store_type _verts;
+ typedef typename base_type::size_type vertices_size_type;
+ typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
+ typedef basic_vertex_iterator<base_type> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
};
} } } /* namespace boost::graphs::adjacency_list */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -5,9 +5,10 @@
#include <boost/containers.hpp>
#include <boost/descriptors.hpp>
-namespace boost { namespace graphs { namespace adjacency_list {
+#include <boost/graphs/label.hpp>
+#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
-struct vertex_descriptor_kind { };
+namespace boost { namespace graphs { namespace adjacency_list {
/**
* The vertex store traits defines the basic types associate with a vertex set.
@@ -16,15 +17,72 @@
struct vertex_store_traits
{ };
+namespace detail
+{
+ // Iterate and compare for sequences.
+ template <typename Store, typename Label>
+ inline typename Store::iterator
+ dispatch_vs_find(Store& store, Label const& l, sequence_tag)
+ {
+ return std::find_if(
+ store.begin(),
+ store.end(),
+ bind2nd(labelled_equal_to<typename Store::value_type>(), l));
+ }
+
+ // Iterate and compare for sequences.
+ template <typename Store, typename Label>
+ inline typename Store::const_iterator
+ dispatch_vs_find(Store const& store, Label const& l, sequence_tag)
+ {
+ return std::find_if(
+ store.begin(),
+ store.end(),
+ bind2nd(labelled_equal_to<typename Store::value_type>(), l));
+ }
+
+ // Associative containers already forward the label as the key, so we just
+ // have to use the basic find command.
+ template <typename Store, typename Label>
+ inline typename Store::iterator
+ dispatch_vs_find(Store& store, Label const& l, associative_container_tag)
+ { return store.find(l); }
+
+ template <typename Store, typename Label>
+ inline typename Store::const_iterator
+ dispatch_vs_find(Store const& store, Label const& l, associative_container_tag)
+ { return store.find(l); }
+}
+
+
/**
- * Add a vertex to the given store, returning a descriptor to the added
- * vertex. The semantics and performance of this function depend on the
- * kind of vertex store.
+ * Add a vertex to the given store, returning an iterator to the new vertex
+ * vertex. The semantics and performance of this function depend on the kind
+ * of vertex store.
*/
template <typename Store, typename Vertex>
-typename descriptor_traits<Store>::descriptor_type
-add_vertex_to_store(Store& store, Vertex v)
-{ return make_descriptor(store, insert(store, v)); }
+inline typename Store::iterator
+vs_add_vertex(Store& store, Vertex&& v)
+{ return container_insert(store, v); }
+
+/** @name Find Vertex
+ * Return an iterator to the vertex that matches the given label. This is
+ * only applicable to labelled vertex types. The returned iterator will be
+ * equivalent to store.end() if no such vertex is found.
+ */
+//@{
+
+template <typename Store, typename Label>
+inline typename Store::iterator
+vs_find_vertex(Store& store, Label const& l)
+{ return detail::dispatch_vs_find(store, l, container_category(store)); }
+
+template <typename Store, typename Label>
+inline typename Store::const_iterator
+vs_find_vertex(Store const& store, Label const& l)
+{ return detail::dispatch_vs_find(store, l, container_category(store)); }
+//@}
+// template <typename
} } } /* namespace boost::graphs::adjacency_list */
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -6,10 +6,7 @@
#include <algorithm>
#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
#include <boost/graphs/adjacency_list/vertex_store.hpp>
-#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -17,13 +14,6 @@
template <typename, typename> struct vertices_vector;
/**
- * 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 Alloc = std::allocator>
@@ -60,109 +50,6 @@
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
};
-/**
- * The vertex_vector template implements veretex storage for adjacency lists
- * as a vector. This essentially provides a heavily constrained interface
- * to the underlying vector. Note that many operations normally supported by
- * a vector are not allowed with graphs.
- *
- * Adding vertices does not invalidate descriptors, but may result in the
- * reallocation of the underlying store. However, removing vertices could
- * corrupt the entire graph (since indices are adjusted). As a result, this
- * store type does not provide remove operations.
- */
-template <typename Vertex, typename Allocator>
-class vertices_vector
-{
-public:
- typedef std::vector<Vertex, Allocator> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_label vertex_label;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- // Constructors
- inline vertices_vector()
- : _verts()
- { }
-
- /** @name Add Vertex
- * Add a vertex to the store with the given label (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- //@{
- inline vertex_descriptor add()
- { return add(vertex_label()); }
-
- inline vertex_descriptor add(vertex_label const& vp)
- {
- iterator i = insert(_verts, vertex_type(vp));
- return make_descriptor(_verts, i);
- }
- //@}
-
- /**
- * Return a descriptor to the vertex with the given label. If you
- * end up calling this function, you're probably using the wrong graph
- * type.
- */
- vertex_descriptor find(vertex_label const& vp) const
- {
- iterator i = std::find_if(_verts.begin(), _verts.end(), find_label(vp));
- return make_descriptor(_verts, i);
- }
-
- /** Rerturn the number of vertices in the vector. */
- size_type size() const
- { return _verts.size(); }
-
- /** @name Vertex Iterators */
- //@{
- vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline typename store_type::iterator begin() const
- { return _verts.begin(); }
-
- inline typename store_type::iterator end() const
- { return _verts.end(); }
- //@}
-
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return *make_iterator(_verts, v); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Property Accessors */
- //@{
- vertex_label& label(vertex_descriptor v)
- { return vertex(v).label(); }
-
- vertex_label const& label(vertex_descriptor v) const
- { return vertex(v).label(); }
- //@}
-
-private:
- mutable store_type _verts;
-};
-
} } } /* namespace boost::graphs::adjacency_list */
#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -0,0 +1,82 @@
+
+#ifndef BOOST_GRAPHS_LABEL_HPP
+#define BOOST_GRAPHS_LABEL_HPP
+
+#include <functional>
+
+#include <boost/none.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost { namespace graphs {
+
+/**
+ * The label traits class provides a mechanism for generically accessing
+ * information about an object's built in label. A label is data associated
+ * with either a vertex or edge.
+ */
+template <typename Object>
+struct label_traits
+{
+ typedef typename Object::label_type label_type;
+};
+
+/**
+ * Metafunction that returns true if the labeled objects type is none. This
+ * should actually be significantly better adapted - for example with arbitrary
+ * types for which label_traits does not exist.
+ */
+template <typename Object>
+struct has_label
+{
+ enum { value = is_same<typename label_traits<Object>::label_type, none>::value };
+};
+
+/**
+ * Return a reference to the object's label. The generic implementation requires
+ * the object to have a non-const label() member.
+ */
+template <typename Object>
+typename label_traits<Object>::label_type& label(Object& x)
+{ return x.label(); }
+
+/**
+ * Return a const reference to the object's label. The generic implementation
+ * requires the object to have a const label() member.
+ */
+template <typename Object>
+typename label_traits<Object>::label_type const& label(Object const& x)
+{ return x.label(); }
+
+/**
+ * This is a simple template wrapper for building comparison functors for
+ * labelled objects.
+ *
+ * This requires that the first/second argument types are the same as the
+ * Object's label type.
+ */
+template <typename Object, typename Compare>
+struct labelled_compare : std::binary_function<Object, Object, bool>
+{
+ inline bool operator()(Object const& a, Object const& b) const
+ { return comp(label(a), label(b)); }
+
+ Compare comp;
+};
+
+/** Equality comparison of labelled objects. */
+template <
+ typename Object,
+ typename Label = typename label_traits<Object>::label_type>
+struct labelled_equal_to : labelled_compare<Object, std::equal_to<Label>> { };
+
+/** Less than comparison of labelled objects. */
+template <
+ typename Object,
+ typename Label = typename label_traits<Object>::label_type>
+struct labelled_less : labelled_compare<Object, std::less<Label>> { };
+
+
+} } /* namespace boost::graphs */
+
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/utility.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/utility.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/utility.hpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -89,29 +89,6 @@
/**
* @internal
- * A forwarding comparator for proeprties objects that forwards the comparison
- * to the configured comparator. This type is used internally to forward
- * comparisons of vertices to the label comparison provided by the edge set
- * parameter.
- * @param Vertex The type of vertex being compared
- * @param Compare An ordering over vertex labels.
- */
-template <typename Compare>
-struct label_comparator
-{
- inline label_comparator()
- : comp(Compare())
- { }
-
- template <typename Object>
- inline bool operator()(Object const& a, Object const& b) const
- { return comp(a.label(), b.label()); }
-
- Compare comp;
-};
-
-/**
- * @internal
* A functor that returns true when we can find a propertied object with the
* same value as those given in the cosntructor. This works for both vertices
* and edges.
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -1,4 +1,5 @@
-include_directories(${Boost_INCLUDE_DIRS} ${Graphs_INCLUDE_DIRS})
+include_directories(${Graphs_INCLUDE_DIRS} ${Boost_INCLUDE_DIRS})
-add_executable(hello hello.cpp)
+add_exec(hello hello.cpp)
+add_exec(vertex_store vertex_store.cpp)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp 2008-11-16 11:25:24 EST (Sun, 16 Nov 2008)
@@ -1,36 +1,56 @@
#include <iostream>
+#include <string>
#include <boost/graphs/adjacency_list/vertex_store.hpp>
#include <boost/graphs/adjacency_list/vertex_vector.hpp>
#include <boost/graphs/adjacency_list/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_set.hpp>
using namespace std;
using namespace boost;
using namespace boost::graphs::adjacency_list;
struct my_vertex
-{ };
+{
+ typedef string label_type; // Adaptor for vertex_traits
+
+ my_vertex(string const& x)
+ : _label(x)
+ { }
+
+ string& label() { return _label; }
+ string const& label() const { return _label; }
+
+ string _label;
+};
template <typename Store>
void test()
{
typedef typename Store::value_type Vertex;
typedef typename descriptor_traits<Store>::descriptor_type VertexDesc;
+ typedef typename Store::iterator StoreIterator;
Store store;
- VertexDesc u = add_vertex_to_store(store, Vertex());
- VertexDesc v = add_vertex_to_store(store, Vertex());
- cout << u << " " << v << endl;
+ // Add some vertices
+ vs_add_vertex(store, Vertex("b"));
+ vs_add_vertex(store, Vertex("a"));
+
+ // Find a verts
+ StoreIterator i = vs_find_vertex(store, string("b"));
+ cout << "test: " << distance(store.begin(), i) << endl;
}
int main()
{
typedef vertex_vector<>::vertex_store<my_vertex>::type VV;
typedef vertex_list<>::vertex_store<my_vertex>::type VL;
+ typedef vertex_set<>::vertex_store<my_vertex>::type VS;
test<VV>();
test<VL>();
+ test<VS>();
}
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