Subject: [Boost-commit] svn:boost r49849 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es include/boost/graphs/adjacency_list/vs test
From: asutton_at_[hidden]
Date: 2008-11-20 10:32:47
Author: asutton
Date: 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
New Revision: 49849
URL: http://svn.boost.org/trac/boost/changeset/49849
Log:
Started rewriting the edge store for undirected graphs
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp | 171 ++++++++++++---------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp | 139 ++++++++++++++++++++-----------
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp | 6 -
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp | 9 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp | 4
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp | 6 -
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp | 19 ---
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/CMakeLists.txt | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp | 61 ++++++++-----
9 files changed, 192 insertions(+), 225 deletions(-)
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,95 @@
+
+#ifndef BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
+#define BOOST_GRAPH_ADJLIST_EDGE_STORE_TRAITS_HPP
+
+#include <boost/concept_check.hpp>
+
+#include <boost/containers.hpp>
+#include <boost/descriptors.hpp>
+
+#include <boost/graphs/label.hpp>
+#include <boost/graphs/edge.hpp>
+
+// Include specializations for the label and edge interfaces.
+#include <boost/graphs/adjacency_list/es/sequence.hpp>
+#include <boost/graphs/adjacency_list/es/association.hpp>
+
+// The edge store interface defines generic operations on an edge store for
+// undirected graphs.
+
+// NOTE: Directed graphs do not use a global edge store. They use out and in
+// edge stores and have a completely different interface.
+
+// TODO: There is a significant overlap between the sequence selectors for
+// vertex and edge stores. These could easily be integrated into a kind of
+// general purpose selector mechanism. For now, they're separate.
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+template <typename Store>
+struct edge_store_traits
+{
+ typedef typename Store::value_type edge_type;
+};
+
+namespace es {
+
+namespace detail {
+ template <typename Store, typename Ends, typename Label>
+ inline typename edge_store_traits<Store>::edge_type
+ make_edge(Store const&, Ends e, Label&& l)
+ { return typename edge_store_traits<Store>::edge_type(e, l); }
+
+ template <typename Store, typename Ends, typename Label>
+ inline typename Store::iterator
+ dispatch_insert(Store& store, Ends e, Label&& l, sequence_tag)
+ { return store.insert(store.end(), make_edge(store, e, l)); }
+
+ // This re-orders the endpoints before inerting in order to guarantee a
+ // canonical ordering edges, and preserving uniqueness, if required.
+ // TODO: Is there a way to convert Comp<pair<VD,VD>> to Comp<VD>? Yeah, but
+ // it's kind of nasty and uses template template parameters.
+ template <typename Store, typename Ends, typename Label>
+ inline typename Store::iterator
+ dispatch_insert(Store& store, Ends e, Label&& l, pair_associative_container_tag)
+ {
+ if(!(e.first < e.second)) swap(e.first, e.second);
+ return container_insert(store, make_edge(store, e, l));
+ }
+}
+
+/** Insert . */
+template <typename Store, typename Ends, typename Label>
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Ends e, Label&& l)
+{ return make_descriptor(store, detail::dispatch_insert(store, e, l, container_category(store))); }
+
+/** Return the number of edges in the edge store. */
+template <typename Store>
+typename Store::size_type size(Store const& store)
+{ return store.size(); }
+
+/** @name Edge Label
+ * Return a lable for the given edge.
+ */
+//@{
+template <typename Store>
+inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type&
+label(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+{ return graphs::label(*make_iterator(store, d)); }
+
+template <typename Store>
+inline typename label_traits<typename edge_store_traits<Store>::edge_type>::label_type const&
+label(Store const& store, typename descriptor_traits<Store>::descriptor_type d)
+{ return graphs::label(*make_iterator(store, d)); }
+//@}
+
+} /* namespace es */
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+// Type selectors
+#include <boost/graphs/adjacency_list/es/vector.hpp>
+#include <boost/graphs/adjacency_list/es/set.hpp>
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/association.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,38 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_ASSOCIATION_HPP
+
+namespace boost { namespace graphs {
+
+// Specializations to support labels for undirected edges for edge vectors,
+// and lists.
+
+template <typename VertexDesc, typename EdgeLabel>
+struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
+{
+ typedef EdgeLabel label_type;
+};
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel&
+label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>& edge)
+{ return edge.second; }
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel const&
+label(std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel> const& edge)
+{ return edge.second; }
+
+// Specializations of the edge interface for edge sequences (vectors and lists).
+
+// NOTE: I'm un-consting the key type for an associative container. Will this
+// cause problems later? Possibly.
+template <typename VertexDesc, typename EdgeLabel>
+struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc> const, EdgeLabel>>
+{
+ typedef std::pair<VertexDesc, VertexDesc> end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/sequence.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,41 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_SEQUENCE_HPP
+
+namespace boost { namespace graphs {
+
+// Specializations to support labels for undirected edges for edge vectors,
+// and lists.
+
+// TODO: I'm a little worried about the possibility of type collisions with
+// directed graphs. It would be nice if I could specialize on an extra piece
+// of information here. Also, the difference between this and associative
+// specializations is the const-ness of the ends.
+
+template <typename VertexDesc, typename EdgeLabel>
+struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
+{
+ typedef EdgeLabel label_type;
+};
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel&
+label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>& edge)
+{ return edge.second; }
+
+template <typename VertexDesc, typename EdgeLabel>
+inline EdgeLabel const&
+label(std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel> const& edge)
+{ return edge.second; }
+
+// Specializations of the edge interface for edge sequences (vectors and lists).
+
+template <typename VertexDesc, typename EdgeLabel>
+struct edge_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>
+{
+ typedef std::pair<VertexDesc, VertexDesc> end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,40 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_SET_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_SET_HPP
+
+#include <map>
+
+#include <boost/graphs/edge.hpp>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+
+/**
+ * @param Compare A unary template class that compares the ends of edges. The
+ * argument type for this function is Pair<VertexDesc, VertexDesc>.
+ * @param Alloc A unary template class that allocates edges.
+ */
+template <
+ template <typename> class Compare = std::less,
+ template <typename> class Alloc = std::allocator>
+struct edge_set
+{
+ typedef typename descriptor_traits<
+ std::set<int, Compare<int>, Alloc<int>>
+ >::descriptor_type edge_descriptor;
+
+ // This quietly implements a map, not a set because we'll be using the
+ // endpoints as keys to the label.
+ template <typename Ends, typename Label>
+ struct edge_store
+ {
+ typedef Compare<Ends> compare;
+ typedef Alloc<std::pair<Ends, Label>> allocator;
+ public:
+ typedef std::map<Ends, Label, compare, allocator> type;
+ };
+};
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,33 @@
+
+#ifndef BOOST_GRAPHS_ADJLIST_ES_VECTOR_HPP
+#define BOOST_GRAPHS_ADJLIST_ES_VECTOR_HPP
+
+#include <vector>
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+/**
+ * @param Alloc A unary template class that will allocate stored vertices.
+ */
+template <template <typename> class Alloc = std::allocator>
+struct edge_vector
+{
+ typedef typename descriptor_traits<
+ std::vector<int, Alloc<int>>
+ >::descriptor_type edge_descriptor;
+
+ // Ends must be a pair of vertices.
+ template <typename Ends, typename Label>
+ struct edge_store
+ {
+ private:
+ typedef std::pair<Ends, Label> edge;
+ typedef Alloc<edge> allocator;
+ public:
+ typedef std::vector<edge, allocator> type;
+ };
+};
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_edge.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -4,114 +4,81 @@
#include <iosfwd>
-#include <boost/unordered_pair.hpp>
-#include <boost/graphs/directional_edge.hpp>
+#include <boost/functional/hash.hpp>
+
+#include <boost/graphs/edge.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
/**
- * This structure implements an unordered edge - sort of. Because the undirected
- * adjacency list class doesn't ever store a concrete edge type, this edge
- * type simply aggregates descriptors in such a way that it defines an edge.
- * This means that this class can also act (and does) as a descriptor itself.
+ * This structure implements an undirected edge. An undirected edge maintains
+ * a pair of vertices and an edge label.
*/
-template <typename VertexDesc, typename PropDesc>
+template <typename EdgeLabel, typename VertexDesc>
class undirected_edge
{
public:
+ typedef EdgeLabel label_type;
+
typedef VertexDesc vertex_descriptor;
- typedef PropDesc label_descriptor;
- typedef unordered_pair<vertex_descriptor> edge_pair;
+ typedef std::pair<vertex_descriptor, vertex_descriptor> ends_pair;
/** @name Constructors */
//@{
- inline undirected_edge()
+ undirected_edge()
: _ends(), _label()
{ }
- inline undirected_edge(vertex_descriptor u, vertex_descriptor v, label_descriptor p)
- : _ends(u, v), _label(p)
+ undirected_edge(vertex_descriptor u, vertex_descriptor v, label_type const& l)
+ : _ends(u, v), _label(l)
{ }
- inline undirected_edge(std::pair<vertex_descriptor, vertex_descriptor> const& e, label_descriptor p)
- : _ends(e.first, e.second), _label(p)
+ undirected_edge(ends_pair const& e, label_type const& l)
+ : _ends(e.first, e.second), _label(l)
{ }
-
- inline undirected_edge(unordered_pair<vertex_descriptor, vertex_descriptor> const& e, label_descriptor p)
- : _ends(e), _label(p)
- { }
- //@}
-
- /** @name Descriptor-like Functions
- * These allow you to treat the edge descriptor like a typical descriptor.
- * That is, it can be tested for null status (which defers to the _labelerty
- * descriptor).
- */
- //@{
- inline bool is_null() const
- { return _label.is_null(); }
-
- inline operator bool() const
- { return !is_null(); }
- //@}
-
- inline label_descriptor label() const
- { return _label; }
-
- inline edge_pair const& edge() const
- { return _ends; }
-
- /** @name End Points
- * Provide access to the end points of the undirected edge. Because the
- * _ends of this edge are unordered, they do not provide a source and target
- * interface. See the rooted_undirected_edge class for a variant of this
- * type that imposes a source/target interface on these edges.
- */
- //@{
- inline vertex_descriptor first() const
- { return _ends.first(); }
-
- inline vertex_descriptor second() const
- { return _ends.second(); }
-
- inline vertex_descriptor opposite(vertex_descriptor v) const
- { return v == first() ? second() : first(); }
- //@}
-
- /** Return true if the edge connects the two vertices. */
- inline bool connects(vertex_descriptor u, vertex_descriptor v) const
- { return make_unordered_pair(u, v) == _ends; }
-
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(undirected_edge const& x) const
- { return (_ends == x._ends) && (_label == x._label); }
-
- inline bool operator!=(undirected_edge const& x) const
- { return !operator==(x); }
//@}
- /** @name Less Than Comparable */
- //@{
- inline bool operator<(undirected_edge const& x) const
- { return std::make_pair(_ends, _label) < std::make_pair(x._ends < x._label); }
-
- inline bool operator>(undirected_edge const& x) const
- { return x.operator<(*this); }
+ label_type& label() { return _label; }
+ label_type const& label() const { return _label; }
- inline bool operator<=(undirected_edge const& x) const
- { return !x.operator<(*this); }
-
- inline bool operator>=(undirected_edge const& x) const
- { return !operator<(x); }
- //@}
+ ends_pair const& ends() const { return _ends; }
private:
- edge_pair _ends;
- label_descriptor _label;
+ ends_pair _ends;
+ label_type _label;
};
+/** @name Equality Comparable */
+//@{
+template <typename L, typename VD>
+inline bool operator==(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return (a.ends() == b.ends()) && (a.label() == b.label()); }
+
+template <typename L, typename VD>
+inline bool operator!=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(a == b); }
+//@}
+
+/** @name Less Than Comparable */
+//@{
+template <typename L, typename VD>
+inline bool operator<(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return std::make_pair(a.ends(), a.label()) < std::make_pair(b.ends(), b.label()); }
+
+template <typename L, typename VD>
+inline bool operator>(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return b < a; }
+
+template <typename L, typename VD>
+inline bool operator<=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(b < a); }
+
+template <typename L, typename VD>
+inline bool operator>=(undirected_edge<L,VD> const& a, undirected_edge<L,VD> const& b)
+{ return !(a < b); }
+//@}
+
+
template <typename V, typename P>
std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
{ return os << "{" << e.first() << " " << e.second() << "}"; }
@@ -124,10 +91,7 @@
template <typename V, typename P>
inline std::size_t
hash_value(undirected_edge<V,P> const& e)
-{
- using boost::hash;
- return hash_value(e.label());
-}
+{ return hash_value(e.label()); }
/**
* The undirected edge iterator simply wraps the iterator over the global edge
@@ -199,37 +163,6 @@
iterator iter;
};
-} /* namespace adjacency_list */
-
-namespace detail
-{
- // Provide an implementation of directionality for undirected edges.
- template <typename Vert, typename Prop>
- struct directional_edge_adapter<adjacency_list::undirected_edge<Vert,Prop>>
- : adjacency_list::undirected_edge<Vert,Prop>
- {
- inline directional_edge_adapter()
- : adjacency_list::undirected_edge<Vert, Prop>(), src()
- { }
-
- inline directional_edge_adapter(adjacency_list::undirected_edge<Vert,Prop> e, Vert s)
- : adjacency_list::undirected_edge<Vert,Prop>(e), src(s)
- { }
-
- inline directional_edge_adapter(Vert s, Vert t)
- : adjacency_list::undirected_edge<Vert,Prop>(s, t), src(s)
- { }
-
- inline Vert source() const
- { return src; }
-
- inline Vert target() const
- { return this->opposite(src); }
-
- Vert src;
- };
-}
-
-} } /* namespace boost::graphs */
+} } } /* namespace boost::graphs::adjacency_list */
#endif
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-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -8,23 +8,22 @@
#include <boost/descriptors.hpp>
#include <boost/graphs/label.hpp>
-#include <boost/graphs/adjacency_list/vs/vector.hpp>
// The Vertex Store defines the generic interface for working with a vertex
// set for both directed and undirected adjacency lists. Its primary goal is
// to provide generic interfaces that abstract common operations on these
// sets. Important kinds of types are:
// - Store - the selected container. Must model Container.
-// - Iterator - a non-const iterator into the store.
+// - Descriptor - a descriptor into the store
+// - Result - pair<Descriptor, bool>
// - Size - the size type of the container
// - Vertex - a type of vertex. Can be labelled.
// - Label - a vertex label
// - Key - a key maapping to a vertex.
-// - Result - pair<Iterator, bool>
//
// Supported operations are:
-// - Iterator vs_add_vertex (Store, Vertex)
-// - Iterator vs_add_vertex (Store, Key, Vertex)
+// - Descriptor vs_add_vertex (Store, Vertex)
+// - Descriptor vs_add_vertex (Store, Key, Vertex)
// - Result vs_try_add_vertex (Store, Vertex)
// - Result vs_try_add_vertex (Store, Key, Vertex)
// - Iterator vs_find_vertex (Store, Label)
@@ -34,30 +33,25 @@
namespace boost { namespace graphs { namespace adjacency_list {
-namespace detail
+/**
+ * The vertex_store_traits relates associated types with a kind of vertex store.
+ * Mostly, this is useful in cases where we have to get the vertex type from
+ * simple and pair associative containers.
+ */
+template <typename Store>
+struct vertex_store_traits
{
- // Try to add the vertex to an associative container. This is a simple
- // delegation to the container.
- template <typename Store, typename Vertex>
- inline std::pair<typename Store::iterator, bool>
- dispatch_vs_try_add(Store& store, Vertex&& v, associative_container_tag)
- { return store.insert(v); }
+ typedef typename Store::value_type vertex_type;
+};
- // Try to add the vertex to a sequential container. Here, we want to search
- // for the vertex (linear time operation) and either insert at the end
- // or return an existing iterator.
- template <typename Store, typename Vertex>
- inline std::pair<typename Store::iterator, bool>
- dispatch_vs_try_add(Store& store, Vertex&& v, sequence_tag)
- {
- typename Store::iterator i = vs_find_vertex(store, label(v));
- return std::make_pair(i, i == store.end());
- }
+namespace vs {
+
+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)
+ dispatch_find(Store& store, Label const& l, sequence_tag)
{
return std::find_if(
store.begin(),
@@ -69,20 +63,38 @@
// 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)
+ dispatch_find(Store& store, Label const& l, associative_container_tag)
{ return store.find(l); }
+
+ // Try to add the vertex to an associative container. This is a simple
+ // delegation to the container.
+ template <typename Store, typename Vertex>
+ inline std::pair<typename Store::iterator, bool>
+ dispatch_try_insert(Store& store, Vertex&& v, associative_container_tag)
+ { return store.insert(v); }
+
+ // Try to add the vertex to a sequential container. Here, we want to search
+ // for the vertex (linear time operation) and either insert at the end
+ // or return an existing iterator.
+ template <typename Store, typename Vertex>
+ inline std::pair<typename Store::iterator, bool>
+ dispatch_try_insert(Store& store, Vertex&& v, sequence_tag)
+ {
+ typename Store::iterator i = dispatch_find(store, label(v), sequence_tag());
+ return std::make_pair(i, i == store.end());
+ }
+
// Explicitly remove the ability use this function, by failing a concept
// check when it is instantiated.
template <typename Store>
- void dispatch_vs_remove(Store&, typename Store::iterator, vector_tag)
+ void dispatch_remove(Store&, typename Store::iterator, vector_tag)
{ function_requires(Integer<Store>()); }
template <typename Store, typename Tag>
- void dispatch_vs_remove(Store& store, typename Store::iterator i, Tag)
+ void dispatch_remove(Store& store, typename Store::iterator i, Tag)
{ store.erase(i); }
-
} /* namespace detail */
/** @name Add Vertex
@@ -93,15 +105,15 @@
//@{
/** Insert a vertex into the container. */
template <typename Store, typename Vertex>
-inline typename Store::iterator
-vs_add_vertex(Store& store, Vertex&& v)
-{ return container_insert(store, v); }
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Vertex&& v)
+{ return make_descriptor(store, container_insert(store, v)); }
/** Insert a vertex into the container, mapped to the given key. */
template <typename Store, typename Key, typename Vertex>
-inline typename Store::iterator
-vs_add_vertex(Store& store, Key const& k, Vertex&& v)
-{ return container_insert(store, std::make_pair(k, v)); }
+inline typename descriptor_traits<Store>::descriptor_type
+insert(Store& store, Key const& k, Vertex&& v)
+{ return make_descriptor(store, container_insert(store, std::make_pair(k, v))); }
//@}
/** @name Try to Add Vertex
@@ -112,35 +124,47 @@
*/
//@{
template <typename Store, typename Vertex>
-inline std::pair<typename Store::iterator, bool>
-vs_try_add_vertex(Store& store, Vertex&& v)
-{ return detail::dispatch_vs_try_add(store, v, container_category(store)); }
+inline std::pair<typename descriptor_traits<Store>::descriptor_type, bool>
+try_insert(Store& store, Vertex&& v)
+{
+ std::pair<typename Store::iterator, bool> x =
+ detail::dispatch_try_insert(store, v, container_category(store));
+ return std::make_pair(make_descriptor(store, x.first), x.second);
+}
// There are no mapped linear sequences, so we can just rely on the fact that
// this is a pair associative container. In fact, this actually requires that
// Store model the UniqueAssociativeContainer concept.
template <typename Store, typename Key, typename Vertex>
-inline std::pair<typename Store::iterator, bool>
-vs_try_add_vertex(Store& store, Key const& k, Vertex&& v)
-{ return store.insert(std::make_pair(k, v)); }
+inline std::pair<typename descriptor_traits<Store>::descriptor_type, bool>
+try_insert(Store& store, Key const& k, Vertex&& v)
+{
+ std::pair<typename Store::iterator, bool> x =
+ store.insert(std::make_pair(k, v));
+ return std::make_pair(make_descriptor(store, x.first), x.second);
+}
//@}
/** @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.
+ *
+ * If the store is a pair associative container (e.g., map), then this function
+ * will find the vertex mapped to the given key. Otherwise, it tries to find
+ * the vertex with the given label.
*/
//@{
-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 LabelOrKey>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store& store, LabelOrKey const& lk)
+{ return make_descriptor(store, detail::dispatch_find(store, lk, container_category(store))); }
// Does not return a const iterator!
-template <typename Store, typename Label>
-inline typename Store::iterator
-vs_find_vertex(Store const& store, Label const& l)
-{ return detail::dispatch_vs_find(const_cast<Store&>(store), l, container_category(store)); }
+template <typename Store, typename LabelOrKey>
+inline typename descriptor_traits<Store>::descriptor_type
+find(Store const& store, LabelOrKey const& lk)
+{ return find(const_cast<Store&>(store), lk, container_category(store)); }
//@}
/**
@@ -150,20 +174,33 @@
*/
//@{
template <typename Store>
-void vs_remove_vertex(Store& store, typename Store::iterator i)
-{ detail::dispatch_vs_remove(store, i, container_category(store)); }
+void remove(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+{ detail::dispatch_remove(store, make_iterator(store, d), container_category(store)); }
//@}
/** Return the number of elements in the vertex store. */
template <typename Store>
-typename Store::size_type vs_size(Store const& store)
+typename Store::size_type size(Store const& store)
{ return store.size(); }
/** Return true if the store is empty. */
template <typename Store>
-bool vs_empty(Store const& store)
+bool empty(Store const& store)
{ return store.empty(); }
+/** Clear the vertex store. */
+template <typename Store>
+void clear(Store& store)
+{ store.clear(); }
+
+} /* namespace vs */
+
} } } /* namespace boost::graphs::adjacency_list */
+// Include type selectors for the different vertex store implementations
+#include <boost/graphs/adjacency_list/vs/vector.hpp>
+#include <boost/graphs/adjacency_list/vs/list.hpp>
+#include <boost/graphs/adjacency_list/vs/set.hpp>
+#include <boost/graphs/adjacency_list/vs/map.hpp>
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -2,11 +2,7 @@
#ifndef BOOST_GRAPHS_ADJLIST_VS_LIST_HPP
#define BOOST_GRAPHS_ADJLIST_VS_LIST_HPP
-#include <list>
-
-#include <boost/none.hpp>
#include <boost/counted_list.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -16,7 +12,7 @@
template <template <typename> class Alloc = std::allocator>
struct vertex_list
{
- typedef unused key_type;
+ typedef void key_type;
typedef typename descriptor_traits<
std::list<int, Alloc<int>>
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -5,7 +5,6 @@
#include <map>
#include <boost/none.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -35,6 +34,14 @@
};
};
+// Specialize the vertex store traits to refer to the mapped type instead
+// of the value type.
+template <typename Key, typename Value, typename Compare, typename Alloc>
+struct vertex_store_traits<std::map<Key, Value, Compare, Alloc>>
+{
+ typedef typename std::map<Key, Value, Compare, Alloc>::mapped_type vertex_type;
+};
+
} } } /* namespace boost::graphs::adjacency_list */
#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -4,9 +4,7 @@
#include <set>
-#include <boost/none.hpp>
#include <boost/graphs/label.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -20,7 +18,7 @@
template <typename> class Alloc = std::allocator>
struct vertex_set
{
- typedef unused key_type;
+ typedef void key_type;
typedef typename descriptor_traits<
std::set<int, Compare<int>, Alloc<int>>
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -3,10 +3,6 @@
#define BOOST_GRAPHS_ADJLIST_VS_VECTOR_HPP
#include <vector>
-#include <algorithm>
-
-#include <boost/none.hpp>
-#include <boost/graphs/adjacency_list/vertex_store.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -16,7 +12,7 @@
template <template <typename> class Alloc = std::allocator>
struct vertex_vector
{
- typedef unused key_type;
+ typedef void key_type;
typedef typename descriptor_traits<
std::vector<int, Alloc<int>>
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/edge.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,24 @@
+
+#ifndef BOOST_GRAPHS_EDGE_HPP
+#define BOOST_GRAPHS_EDGE_HPP
+
+#include <boost/none.hpp>
+
+namespace boost { namespace graphs {
+
+// The edge interface...
+
+/**
+ * The edge traits class provides information about the end points and semantics
+ * of edges, but not their labels.
+ */
+template <typename Edge>
+struct edge_traits
+{
+ typedef typename Edge::end_pair end_pair;
+};
+
+} } /* namespace boost::graphs */
+
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -20,32 +20,19 @@
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 };
-};
-
-/**
+/** @name Label Access
* 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
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-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -1,5 +1,5 @@
include_directories(${Graphs_INCLUDE_DIRS} ${Boost_INCLUDE_DIRS})
-add_exec(hello hello.cpp)
add_exec(vertex_store vertex_store.cpp)
+add_exec(edge_store edge_store.cpp)
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/edge_store.cpp 2008-11-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -0,0 +1,41 @@
+
+#include <iostream>
+#include <string>
+
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
+#include <boost/graphs/adjacency_list/edge_store.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+using namespace boost::graphs;
+using namespace boost::graphs::adjacency_list;
+
+template <typename Store>
+void test()
+{
+ typedef typename edge_store_traits<Store>::edge_type Edge;
+ typedef typename edge_traits<Edge>::end_pair Ends;
+ typedef typename descriptor_traits<Store>::descriptor_type EdgeDesc;
+
+ Store store;
+
+ EdgeDesc e1 = es::insert(store, Ends(0, 1), 0.5);
+ EdgeDesc e2 = es::insert(store, Ends(0, 2), 1.5);
+ BOOST_ASSERT(es::size(store) == 2u);
+ cout << es::label(store, e1) << endl;
+ cout << es::label(store, e2) << endl;
+}
+
+int main()
+{
+ typedef vertex_vector<>::vertex_descriptor VertexDesc;
+ typedef std::pair<VertexDesc, VertexDesc> Ends;
+
+ typedef edge_vector<>::edge_store<Ends, double>::type EV;
+ typedef edge_set<>::edge_store<Ends, double>::type EM;
+
+ test<EV>();
+ test<EM>();
+}
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-20 10:32:46 EST (Thu, 20 Nov 2008)
@@ -3,14 +3,9 @@
#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>
-#include <boost/graphs/adjacency_list/vertex_map.hpp>
#include "typestr.hpp"
-
using namespace std;
using namespace boost;
using namespace boost::graphs::adjacency_list;
@@ -44,45 +39,63 @@
template <typename Store>
void add_verts(Store& store, simple_container_tag)
{
- typedef typename Store::iterator Iterator;
- typedef typename Store::value_type Vertex;
- vs_add_vertex(store, Vertex("b"));
- Iterator iter = vs_add_vertex(store, Vertex("a"));
-
- vs_remove_vertex(store, iter);
+ typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+ typedef typename vertex_store_traits<Store>::vertex_type Vertex;
+ vs::insert(store, Vertex("b"));
+ vs::insert(store, Vertex("a"));
// Try to re-add a vertex.
- pair<Iterator, bool> i = vs_try_add_vertex(store, Vertex("b"));
- cout << "re-add: " << i.second << "\n";
+ pair<Descriptor, bool> i = vs::try_insert(store, Vertex("b"));
+ BOOST_ASSERT(!i.second);
}
template <typename Store>
void add_verts(Store& store, pair_container_tag)
{
- typedef typename Store::iterator Iterator;
- typedef typename Store::mapped_type Vertex;
- vs_add_vertex(store, "a", Vertex());
- vs_add_vertex(store, "b", Vertex());
+ typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+ typedef typename vertex_store_traits<Store>::vertex_type Vertex;
+ vs::insert(store, "a", Vertex());
+ vs::insert(store, "b", Vertex());
// Try to re-add a vertex.
- pair<Iterator, bool> i = vs_try_add_vertex(store, string("b"), Vertex());
- cout << "re-add: " << i.second << "\n";
+ pair<Descriptor, bool> i = vs::try_insert(store, string("b"), Vertex());
+ BOOST_ASSERT(!i.second);
}
+template <typename Store, typename Tag>
+void remove_vert(Store& store, Tag t)
+{
+ typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
+ Descriptor d = vs::find(store, string("b"));
+ BOOST_ASSERT(d);
+ size_t n = vs::size(store);
+ vs::remove(store, d);
+ BOOST_ASSERT(vs::size(store) == n - 1);
+}
+
+// No-op for vectors... Can't remove vertices.
+template <typename Store>
+void remove_vert(Store& store, vector_tag)
+{ }
+
template <typename Store>
void test()
{
typedef typename Store::value_type Vertex;
- typedef typename descriptor_traits<Store>::descriptor_type VertexDesc;
- typedef typename Store::iterator StoreIterator;
+ typedef typename descriptor_traits<Store>::descriptor_type Descriptor;
Store store;
add_verts(store, container_arity(container_category(store)));
+ BOOST_ASSERT(!vs::empty(store));
+ BOOST_ASSERT(vs::size(store));
// Find a verts
- StoreIterator i = vs_find_vertex(store, string("b"));
- cout << "test: " << distance(store.begin(), i) << endl;
+ Descriptor d = vs::find(store, string("b"));
+ BOOST_ASSERT(d);
+
+ // Check the removal of vertices
+ remove_vert(store, container_category(store));
}
int main()
@@ -92,7 +105,7 @@
typedef vertex_set<>::vertex_store<my_vertex>::type VS;
typedef vertex_map<string>::vertex_store<my_vertex>::type VM;
- // test<VV>();
+ test<VV>();
test<VL>();
test<VS>();
test<VM>();