Boost-Commit :

Date view	Thread view	Subject view	Author view

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

Date view	Thread view	Subject view	Author view

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