From: asutton_at_[hidden]
Date: 2008-07-07 13:35:00
Author: asutton
Date: 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
New Revision: 47194
URL: http://svn.boost.org/trac/boost/changeset/47194
Log:
Started rewriting some of the edge addition protocol for associative/sequence
edge containers - it's easier to tag-dispatch the correct algorithm than
to force everything into a single algorithm. Good design question: when
is it correct to move generic functionality into a class and when is it
better to leave it as a generic algorithm?
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp | 4 +
sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp | 18 ++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp | 35 +++++++++-----
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 44 +++++++++++++-----
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 15 ++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp | 15 ++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp | 38 ++++++++++-----
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 16 ++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp | 17 ++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp | 11 ++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp | 3 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp | 6 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp | 94 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp | 14 +++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 4
16 files changed, 245 insertions(+), 90 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -74,4 +74,8 @@
return hash_value(x.value);
}
+template <typename Index>
+std::ostream& operator<<(std::ostream& os, index_descriptor<Index> const& x)
+{ return os << x.value; }
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -1,6 +1,8 @@
-#ifndef VECTOR_DESCRIPTOR_HPP
-#define VECTOR_DESCRIPTOR_HPP
+#ifndef NODE_DESCRIPTOR_HPP
+#define NODE_DESCRIPTOR_HPP
+
+#include <boost/functional/hash.hpp>
/**
* The node descriptor contains an iterator into the target container. The
@@ -64,4 +66,16 @@
descriptor_type value;
};
+// A hash function for indexed descriptors.
+template <typename Blob>
+std::size_t hash_value(node_descriptor<Blob> const& x)
+{
+ using boost::hash_value;
+ return hash_value(x.value);
+}
+
+template <typename Blob>
+std::ostream& operator<<(std::ostream& os, node_descriptor<Blob> const& d)
+{ return os << hash_value(d); }
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -2,13 +2,10 @@
#ifndef EDGE_LIST_HPP
#define EDGE_LIST_HPP
-#include "triple.hpp"
-#include "placeholder.hpp"
-
#include "property_list.hpp"
#include "incidence_list.hpp"
-#include "out_list.hpp"
-#include "in_list.hpp"
+// #include "out_list.hpp"
+// #include "in_list.hpp"
// The edge list does two things. First, it indicates that edges will
// be stored in an incidence list (as opposed to a vector or set).
@@ -24,27 +21,40 @@
template <typename> class SecondAlloc = std::allocator>
struct edge_list
{
+ // A couple of dummy vectors used to build descriptors.
+ typedef std::list<int, FirstAlloc<int>> first_dummy;
+ typedef std::list<int, SecondAlloc<int>> second_dummy;
+
+ // Descriptor types for undirected graphs.
+ typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
+ typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
+
// The property store metafunction generates the underlying global store
// type for edge properties in undirected graphs.
- template <typename EdgeProps>
+ template <typename EdgeProps, typename VertexDesc>
struct property_store
{
- typedef placeholder<sizeof(typename std::list<int>::iterator)> dummy_type;
- typedef triple<EdgeProps, dummy_type, dummy_type> property;
- typedef SecondAlloc<property> allocator;
- typedef property_list<property, allocator> type;
+ typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
+ typedef SecondAlloc<edge> allocator;
+ typedef property_list<edge, allocator> type;
};
// The incidence store metafunction generates the per-vertex storage type
// for undirected vertices.
- template <typename VertexDesc, typename PropDesc>
+ template <typename VertexDesc>
struct incidence_store
{
- typedef std::pair<VertexDesc, PropDesc> incidence_pair;
+ typedef std::pair<VertexDesc, property_descriptor> incidence_pair;
typedef FirstAlloc<incidence_pair> allocator;
typedef incidence_list<incidence_pair, allocator > type;
};
+ // Descriptor types for directed graphs
+ typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
+ typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
+
+
+ /*
// The out store metafunction generates the type of list used to store
// out edges of a vertex in a directed graph.
template <typename VertexDesc, typename Props>
@@ -74,6 +84,7 @@
typedef SecondAlloc<edge> allocator;
typedef in_list<edge, allocator> type;
};
+ */
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -2,13 +2,13 @@
#ifndef EDGE_SET_HPP
#define EDGE_SET_HPP
-#include "triple.hpp"
-#include "placeholder.hpp"
+#include <list>
+#include <map>
#include "property_list.hpp"
#include "incidence_set.hpp"
-#include "out_set.hpp"
-#include "in_set.hpp"
+// #include "out_set.hpp"
+// #include "in_set.hpp"
/**
* The edge set metafunction defines the basic facets of set-based edge
@@ -25,28 +25,45 @@
template <typename> class SecondAlloc = std::allocator>
struct edge_set
{
- // The property store metafunnction generates the global store type
- // for undirected graphs.
- template <typename EdgeProps>
+ // A couple of dummy vectors used to build descriptors. This looks really
+ // weird since we're expecting a set type somewhere around here. However,
+ // there isn't actually a real "set" used in these stores. The property
+ // store only needs to be a list, and the incidence/in/out stores are
+ // actually all maps (vertex to something).
+ typedef std::map<int, int, Compare<int>, FirstAlloc<int>> first_dummy;
+ typedef std::list<int, SecondAlloc<int>> second_dummy;
+
+ // Descriptor types for undirected graphs.
+ typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
+ typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
+
+ // The property store metafunnction generates the global store type for
+ // undirected graphs. The property list only needs to be a list, not a set.
+ template <typename EdgeProps, typename VertexDesc>
struct property_store
{
- typedef typename hold<std::list<int>::iterator>::type dummy_type;
- typedef triple<EdgeProps, dummy_type, dummy_type> property;
- typedef SecondAlloc<property> allocator;
- typedef property_list<property, allocator> type;
+ typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
+ typedef SecondAlloc<edge> allocator;
+ typedef property_list<edge, allocator> type;
};
// The incidence store metafunction generates the per-vertex stores for
// incident edges.
- template <typename VertexDesc, typename PropDesc>
+ template <typename VertexDesc>
struct incidence_store
{
- typedef std::pair<VertexDesc, PropDesc> value;
+ typedef std::pair<VertexDesc, property_descriptor> value;
typedef Compare<VertexDesc> compare;
typedef FirstAlloc<value> allocator;
typedef incidence_set<value, compare, allocator> type;
};
+ // Descriptor types for directed graphs
+ typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
+ typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
+
+
+ /*
// The out store metafunction generates the type of set used to store out
// edges of a vertex in a directed graph.
template <typename VertexDesc, typename Props>
@@ -78,6 +95,7 @@
typedef SecondAlloc<edge> allocator;
typedef in_set<edge, compare, allocator> type;
};
+ */
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -4,8 +4,8 @@
#include "property_vector.hpp"
#include "incidence_vector.hpp"
-#include "out_vector.hpp"
-#include "in_vector.hpp"
+// #include "out_vector.hpp"
+// #include "in_vector.hpp"
// What's in an edge vector? Basically, an edge vector has to specify
// the type of property storage and the type of incidence storage. What
@@ -47,26 +47,25 @@
// The property store metafunction generates the type of vector used to
// store global properties for undirected graphs.
- template <typename EdgeProps, typename IncDesc>
+ template <typename EdgeProps, typename VertexDesc>
struct property_store
{
- typedef std::pair<EdgeProps, std::pair<IncDesc, IncDesc>> edge;
+ typedef std::pair<EdgeProps, std::pair<VertexDesc, VertexDesc>> edge;
typedef SecondAlloc<edge> allocator;
typedef property_vector<edge, allocator> type;
};
// The incidence store metafunction generates the type of vector used to
// store edges incident to the an undirected vertex.
- template <typename VertexDesc, typename PropDesc>
+ template <typename VertexDesc>
struct incidence_store
{
- typedef std::pair<VertexDesc, PropDesc> incidence_pair;
+ typedef std::pair<VertexDesc, property_descriptor> incidence_pair;
typedef FirstAlloc<incidence_pair> incidence_allocator;
typedef incidence_vector<incidence_pair, incidence_allocator> type;
};
-
- // Descritor types for directed graphs
+ // Descriptor types for directed graphs
typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -19,11 +19,10 @@
class incidence_list
{
public:
- typedef std::list<Edge, Alloc> store_type;
-
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type property_descriptor;
+ typedef std::list<Edge, Alloc> store_type;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -35,14 +34,6 @@
{ }
/**
- * Incidence lists always allow the addition of edges, assuming that no policy
- * conflicts exist. The first element of the return is the end() of the list.
- * @complexity O(1)
- */
- inline std::pair<incidence_descriptor, bool> allow(vertex_descriptor) const
- { return make_pair(make_descriptor(_edges, _edges.end()), true); }
-
- /**
* Add a vertex to the list.
* @complexity O(1)
*/
@@ -84,6 +75,10 @@
inline size_type size() const
{ return _size; }
+ /** Return true if this is empty. */
+ inline bool empty() const
+ { return _edges.empty(); }
+
/** @name Iterators */
//@{
inline iterator begin() const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -30,7 +30,6 @@
// aspect of the key at times, but changing that value would be absolutely
// catastrophic.
typedef std::map<vertex_descriptor, property_descriptor, Compare, Alloc> store_type;
-
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -41,25 +40,29 @@
: _edges()
{ }
- /**
- * Deteremine whether or not the edge exists or is even allowed to be added.
- * This returns a pair containing an iterator indicating the position of the
- * edge if it already exists and a bool value indicating whether or not the
- * addition would even be allowed by policy.
- * @complexity O(lg(dd))
- */
- inline std::pair<incidence_descriptor, bool> allow(vertex_descriptor v) const
- { return make_pair(make_descriptor(_edges, _edges.find(v)), true); }
-
- /**
- * Add the incidence pair to the vertex.
+ /** @name Add Incident Edge.
+ * Try adding the incident edge to the vertex. The first version is used in
+ * a two-step edge addition where the property descriptor is bound in the
+ * second phase of the insertion.
* @complexity O(lg(d))
*/
+ //@{
+ inline incidence_descriptor add(vertex_descriptor v)
+ { return add(v, property_descriptor()); }
+
inline incidence_descriptor add(vertex_descriptor v, property_descriptor p)
{
std::pair<iterator, bool> i = _edges.insert(make_pair(v, p));
- return make_descriptor(_edges, i.first);
+ return i.second ? make_descriptor(_edges, i.first) : incidence_descriptor();
}
+ //@}
+
+ /**
+ * Bind the given property descriptor to this vertex. This is useful when
+ * the incidence pair is added before property is allocated.
+ */
+ inline void bind(incidence_descriptor d, property_descriptor p)
+ { make_iterator(_edges, d)->second = p; }
/**
* Find the incident edge whose opposite end is v.
@@ -83,6 +86,13 @@
inline size_type size() const
{ return _edges.size(); }
+ /** Return true if this is empty. */
+ inline bool empty() const
+ { return _edges.empty(); }
+
+ inline bool valid(incidence_descriptor d)
+ { return make_iterator(_edges, d) != _edges.end(); }
+
/** @name Iterators */
//@{
inline iterator begin() const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -20,11 +20,10 @@
class incidence_vector
{
public:
- typedef std::vector<Edge, Alloc> store_type;
-
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type property_descriptor;
+ typedef std::vector<Edge, Alloc> store_type;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -35,15 +34,6 @@
: _edges()
{ }
- /**
- * Incidence vectors always allow the addition of edges, assuming that no
- * policy conflicts exist. The first element of the return is the end() of
- * the vector.
- * @complexity O(1)
- */
- std::pair<incidence_descriptor, bool> allow(vertex_descriptor) const
- { return make_pair(incidence_descriptor(), true); }
-
/** Add the incidence pair to the vector. */
incidence_descriptor add(vertex_descriptor v, property_descriptor p)
{
@@ -62,6 +52,10 @@
inline size_type size() const
{ return _edges.size(); }
+ /** Return true if this is empty. */
+ inline bool empty() const
+ { return _edges.empty(); }
+
/** @name Iterators */
//@{
inline iterator begin() const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -75,18 +75,21 @@
inline edge_properties& properties(property_descriptor d)
{ return make_iterator(_props, d)->first; }
- /** Bind iterators into the incidence lists into the global property. */
- template <typename Iter>
- void bind(property_descriptor d, Iter src, Iter tgt)
- {
- d.value().second.put(src);
- d.value().third.put(tgt);
- }
+ /**
+ * Bind vertex descriptors into the incidence lists into the global
+ * property. This is the last step of edge creation for undirected graphs.
+ */
+ void bind(property_descriptor d, edge_pair const& p)
+ { make_iterator(_props, d)->second = p; }
/** Return the number of properties. */
inline size_type size() const
{ return _size; }
+ /** Return true if this is empty. */
+ inline bool empty() const
+ { return _props.empty(); }
+
/** @name Iterators */
//@{
inline iterator begin() const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -58,6 +58,13 @@
return make_descriptor(_props, i);
}
+ /**
+ * Bind vertex descriptors into the incidence lists into the global
+ * property. This is the last step of edge creation for undirected graphs.
+ */
+ void bind(property_descriptor d, edge_pair const& p)
+ { make_iterator(_props, d)->second = p; }
+
/** Return the properties referenced by the given descriptor. */
inline edge_properties& properties(property_descriptor d)
{ return d.value().first; }
@@ -66,6 +73,10 @@
inline size_type size() const
{ return _props.size(); }
+ /** Return true if this is empty. */
+ inline bool empty() const
+ { return _props.empty(); }
+
/** @name Iterators */
//@{
inline iterator begin() const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/utility.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -2,6 +2,9 @@
#ifndef UTILITY_HPP
#define UTILITY_HPP
+#include <boost/descriptors.hpp>
+
+
/**
* @internal
* A forwarding comparator for proeprties objects that forwards the comparison
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -105,7 +105,6 @@
size_type size() const
{ return _verts.size(); }
-
/** @name Vertex Iterators */
//@{
vertex_iterator begin_vertices() const
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -2,9 +2,9 @@
#ifndef INCIDENCE_TRAITS_HPP
#define INCIDENCE_TRAITS_HPP
-struct incidence_vector_tag : unstable_remove_tag { };
-struct incidence_list_tag : stable_mutators_tag { };
-struct incidence_set_tag : stable_mutators_tag { };
+struct incidence_vector_tag : sequence_tag, unstable_remove_tag { };
+struct incidence_list_tag : sequence_tag, stable_mutators_tag { };
+struct incidence_set_tag : associative_container_tag, stable_mutators_tag { };
template <typename IncStore>
struct incidence_traits
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -3,17 +3,89 @@
#include <boost/next_prior.hpp>
#include <boost/graphs/edge_vector.hpp>
+#include <boost/graphs/edge_list.hpp>
+#include <boost/graphs/edge_set.hpp>
#include "typestr.hpp"
+#include "properties_traits.hpp"
+#include "incidence_traits.hpp"
using namespace std;
using namespace boost;
-// These are things that we can't do much about...
+// These are things that we can't do much about... Note that we can actually
+// generate all of these types prior to the definition of the edge store - it
+// seems a little odd since IncDesc is actually IN the edge store, but its
+// not instantiated until a little later.
typedef int VertexProps;
typedef int EdgeProps;
typedef index_descriptor<size_t> VertexDesc;
-typedef index_descriptor<size_t> IncDesc;
+
+template <typename Props, typename Incs, typename Vertex, typename Edge>
+void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep, associative_container_tag)
+{
+ typedef typename Props::property_descriptor PropDesc;
+ typedef typename Incs::incidence_descriptor IncDesc;
+
+ Vertex u = VertexDesc(0);
+
+ // This is a little different protocol.. First, try to insert the edge
+ // into the incidence list, but lave the property slot "empty".
+ IncDesc i = incs.add(v);
+ if(incs.valid(i)) {
+ PropDesc p = props.add(ep);
+ incs.bind(i, p);
+ props.bind(p, make_pair(u, v));
+ cout << " * added: " << u << ", " << v << endl;
+ }
+ else {
+ cout << " * did not add: " << u << ", " << v << endl;
+ }
+}
+
+// These are basically multigraphs (i.e., multiple edges allowed).
+template <typename Props, typename Incs, typename Vertex, typename Edge>
+void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep, sequence_tag)
+{
+ typedef typename Props::property_descriptor PropDesc;
+ typedef typename Incs::incidence_descriptor IncDesc;
+
+ Vertex u = VertexDesc(0);
+
+ // Pretty simple... add the vertex and create the incident pair, and then
+ // bind both the implicit (0) vertex and v to the property.
+ size_t m = props.size(), n = incs.size();
+ PropDesc p = props.add(ep);
+ IncDesc i = incs.add(v, p);
+ props.bind(p, make_pair(u, v));
+
+ cout << " * added: " << u << ", " << v << endl;
+ BOOST_ASSERT(props.size() == m + 1);
+ BOOST_ASSERT(incs.size() == n + 1);
+}
+
+// Add an edge with the given properties to the implicit vertex.
+template <typename Props, typename Incs, typename Vertex, typename Edge>
+void add_edge(Props& props, Incs& incs, Vertex v, Edge const& ep)
+{
+ add_edge(props, incs, v, ep, incidence_category(incs));
+}
+
+// Test the addition of edges as if we were adding them to an implicit vertex 0.
+template <typename Props, typename Incs>
+void add_edges(Props& props, Incs& incs)
+{
+ BOOST_ASSERT(props.empty());
+ BOOST_ASSERT(incs.empty());
+
+ size_t const N = 5;
+ for(size_t i = 0; i < N; ++i) {
+ add_edge(props, incs, VertexDesc(i + 1), i * i);
+ }
+
+ // Just for good measure, add antoher that duplicates the first.
+ add_edge(props, incs, VertexDesc(1), 1);
+}
template <typename EdgeStore>
void
@@ -23,15 +95,23 @@
// Instantiate data structures related to the storage of edges and their
// properties.
- typedef typename EdgeStore::template property_store<EdgeProps, IncDesc>::type PropStore;
- typedef typename EdgeStore::template incidence_store<EdgeProps, IncDesc>::type IncStore;
- cout << " * " << typestr<PropStore>() << endl;
- cout << " * " << typestr<IncStore>() << endl;
+ typedef typename EdgeStore::template property_store<EdgeProps, VertexDesc>::type PropStore;
+ typedef typename EdgeStore::template incidence_store<VertexDesc>::type IncStore;
+
+ PropStore props;
+ IncStore incs;
+
+ cout << " * " << typestr(properties_category(props)) << endl;
+ cout << " * " << typestr(incidence_category(incs)) << endl;
+
+ add_edges(props, incs);
}
int main()
{
undirected<edge_vector<>>();
+ undirected<edge_list<>>();
+ undirected<edge_set<>>();
- return 0;
+ return 0;
}
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -17,6 +17,20 @@
typedef allocator<Edge> Alloc;
typedef std::less<VertexDesc> Compare;
+template <typename IncStore, typename Vertex, typename Property>
+void add(IncStore& incs, Vertex v, Property p, associative_container_tag)
+{
+ typename IncStore::incidence_descriptor i = incs.add(v);
+ incs.bind(i, p);
+}
+
+template <typename IncStore, typename Vertex, typename Property>
+void add(IncStore& incs, Vertex v, Property p, sequence_tag)
+{
+ incs.add(v, p);
+}
+
+
template <typename IncStore>
void test_remove(IncStore& incs, stable_mutators_tag)
{
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp 2008-07-07 13:34:58 EDT (Mon, 07 Jul 2008)
@@ -81,8 +81,8 @@
{
test<vertex_vector<>>();
test<vertex_list<>>();
- test<vertex_set<>>();
- test<vertex_map<int>>();
+ // test<vertex_set<>>();
+ // test<vertex_map<int>>();
return 0;
}
\ No newline at end of file