|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-07 11:43:08
Author: asutton
Date: 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
New Revision: 47192
URL: http://svn.boost.org/trac/boost/changeset/47192
Log:
Changing a couple of type and tag naems.
Started adding traits for components of graphs.
Added:
sandbox/SOC/2008/graphs/trunk/libs/graphs/README (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp | 22 ++++++++++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp | 8 +++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp | 8 +++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp | 8 +++---
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 8 +++---
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp | 34 +++---------------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp | 13 ++++++++---
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 44 +++++++++++++++------------------------
9 files changed, 57 insertions(+), 89 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -50,7 +50,7 @@
// strategies. Of course, these policies can be reduced to a single template
// using inheritance and/or template aliases.
-// Operator Stability Tags
+// Mutator Stability Tags
// These tags define the stability of container's descriptors under insert and
// remove operations. Note that unstable operations should not be used in
// relational data structures (like graphs) since these operations will
@@ -61,7 +61,7 @@
// Note that it is certainly possible for a container to be unstable for both
// insertions and removals. These data structures are generally constructed over
// a known set of objects and are generally immutable afterwards.
-struct stable_descriptor_tag { };
+struct stable_mutators_tag { };
struct unstable_insert_tag { };
struct unstable_remove_tag { };
struct unstable_mutators_tag : unstable_insert_tag, unstable_remove_tag { };
@@ -78,7 +78,7 @@
struct descriptor_traits
{
typedef typename Container::descriptor_type descriptor_type;
- typedef typename Container::descriptor_stability descriptor_stability;
+ typedef typename Container::mutator_stability mutator_stability;
};
/**
@@ -112,9 +112,9 @@
/** Return the descriptor stability tag for the given container. */
template <typename Container>
-inline typename descriptor_traits<Container>::descriptor_stability
-descriptor_stability(Container const&)
-{ return typename descriptor_traits<Container>::descriptor_stability(); }
+inline typename descriptor_traits<Container>::mutator_stability
+mutator_stability(Container const&)
+{ return typename descriptor_traits<Container>::mutator_stability(); }
// Metafunctions
@@ -163,7 +163,7 @@
struct descriptor_traits<std::list<T, Alloc>>
{
typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
+ typedef stable_mutators_tag descriptor_stability;
};
// TODO: Dequeue
@@ -173,7 +173,7 @@
struct descriptor_traits<std::set<T, Comp, Alloc>>
{
typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>> descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
+ typedef stable_mutators_tag descriptor_stability;
};
// Multiset
@@ -181,7 +181,7 @@
struct descriptor_traits<std::multiset<T, Comp, Alloc>>
{
typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>> descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
+ typedef stable_mutators_tag descriptor_stability;
};
// Map
@@ -189,7 +189,7 @@
struct descriptor_traits<std::map<Key, T, Comp, Alloc>>
{
typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
+ typedef stable_mutators_tag descriptor_stability;
};
// Multimap
@@ -197,7 +197,7 @@
struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>>
{
typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
+ typedef stable_mutators_tag descriptor_stability;
};
// TODO: Unordered Set
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -10,7 +10,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, typename> class vertex_list_impl;
+template <typename, typename> class vertices_list;
/**
* This metafunction defines the basic elements of a vertex list.
@@ -26,7 +26,7 @@
template <typename Vertex>
struct store
{
- typedef vertex_list_impl<Vertex, Alloc<Vertex>> type;
+ typedef vertices_list<Vertex, Alloc<Vertex>> type;
};
};
@@ -37,7 +37,7 @@
* @param Alloc The allocator for stored vertices.
*/
template <typename Vertex, typename Alloc>
-class vertex_list_impl
+class vertices_list
{
public:
typedef std::list<Vertex, Alloc> store_type;
@@ -54,7 +54,7 @@
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
// Constructors
- inline vertex_list_impl()
+ inline vertices_list()
: _verts(), _size(0)
{ }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -9,7 +9,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, typename, typename, typename> class vertex_map_impl;
+template <typename, typename, typename, typename> class vertices_map;
/**
* This metafunction defines the implementation requirements of a mapping of
@@ -42,7 +42,7 @@
template <typename Vertex>
struct store
{
- typedef vertex_map_impl<
+ typedef vertices_map<
Vertex, Key, Compare<Key>, Alloc<std::pair<Key, Vertex>>
> type;
};
@@ -58,7 +58,7 @@
* @param Alloc The allocator for Key/Vertex pairs.
*/
template <typename Vertex, typename Key, typename Compare, typename Allocator>
-class vertex_map_impl
+class vertices_map
{
public:
typedef std::map<Key, Vertex, Compare, Allocator> store_type;
@@ -76,7 +76,7 @@
typedef simple_vertex_iterator<store_type> vertex_iterator;
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
- inline vertex_map_impl()
+ inline vertices_map()
: _verts()
{ }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -11,7 +11,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, typename, typename> class vertex_set_impl;
+template <typename, typename, typename> class vertices_set;
/**
* This metafunction defines the implementation requirements of a set of
@@ -42,7 +42,7 @@
template <typename Vertex>
struct store
{
- typedef vertex_set_impl<
+ typedef vertices_set<
Vertex,
property_comparator<Compare<typename Vertex::vertex_properties>>,
Alloc<Vertex>
@@ -60,7 +60,7 @@
* @param Allocator The allocator for stored vertices.
*/
template <typename Vertex, typename Compare, typename Allocator>
-class vertex_set_impl
+class vertices_set
{
public:
typedef std::set<Vertex, Compare, Allocator> store_type;
@@ -76,7 +76,7 @@
typedef simple_vertex_iterator<store_type> vertex_iterator;
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
- inline vertex_set_impl()
+ inline vertices_set()
: _verts()
{ }
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 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -12,7 +12,7 @@
#include "vertex_iterator.hpp"
// Forward declarations
-template <typename, typename> struct vertex_vector_impl;
+template <typename, typename> struct vertices_vector;
/**
* The vertex vector stores vertices in a vector, allowing for fast inserts
@@ -38,7 +38,7 @@
template <typename Vertex>
struct store
{
- typedef vertex_vector_impl<Vertex, Alloc<Vertex>> type;
+ typedef vertices_vector<Vertex, Alloc<Vertex>> type;
};
};
@@ -54,7 +54,7 @@
* store type does not provide remove operations.
*/
template <typename Vertex, typename Allocator>
-class vertex_vector_impl
+class vertices_vector
{
public:
typedef std::vector<Vertex, Allocator> store_type;
@@ -71,7 +71,7 @@
typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
// Constructors
- inline vertex_vector_impl()
+ inline vertices_vector()
: _verts()
{ }
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/README
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/README 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,46 @@
+
+Notes...
+
+
+Q: What's up with the extra descriptors in the property store?
+With undirected graphs, the global property store (which stores the edge
+properties for each distinct edge) blocks out storage for two descriptors (this
+is actually done by the edge_* store templates). These two descriptors are used
+to index the endpoints of the edge. Without this, the construction of the edge
+descriptor is non-constant (i.e., probably linear in G) when being built
+directly from the edge store. This solution arises from the implementation of
+edge iterators for undirected graphs, which simply iterate over the property
+store, creating edges.
+
+The property stores do not actually store edges - because the extra descriptors
+are (basically) iterators into the incidence stores of referenced vertices. The
+property store does not have access to the underlying stores so it can't really
+access the iterators, but the graph and edge iterators will have access to them.
+
+The decision to store extra information and inflate the size of the graph is
+a design decision. There are probably ways to build this data structure without
+the additional size cost at the expense of more complex edge iterators, or to
+provide an implementation without edge iterators (which would be just fine with
+me). There is nothing to stop programmers from building these alternative
+implementations - they're good projects.
+
+
+Q: Why are the property list and vector different types when their
+implementations are nearly identical.
+The property list has to associate its size with the container since `st::list`s
+have a linear size operation. Since the property store does not allow arbitrary
+inserts and removes (just one at a time), we can effectively track the size to
+provide a constant size function.
+
+
+Q: Why are all the containers `mutable`?
+Because the descriptor library does not translate between const and non-`const`
+iterators. This stems from the fact that you can't cast out the `const` aspect
+of an iterator.
+
+
+Q: Is there an easy way to get a template from a template instance? For example,
+I have `std::list<int>`, can I get `std::list`?
+Probably for specific instances of templates, but probably not generically...
+But then again. Who knows?
+
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,30 @@
+
+#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 { };
+
+template <typename IncStore>
+struct incidence_traits
+{ typedef typename IncStore::category category; };
+
+template <typename IncStore>
+typename incidence_traits<IncStore>::category
+incidence_category(IncStore const&)
+{ return typename incidence_traits<IncStore>::category(); }
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_vector<Edge, Alloc>>
+{ typedef incidence_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct incidence_traits<incidence_list<Edge, Alloc>>
+{ typedef incidence_list_tag category; };
+
+template <typename Edge, typename Comp, typename Alloc>
+struct incidence_traits<incidence_set<Edge, Comp, Alloc>>
+{ typedef incidence_set_tag category; };
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/properties_traits.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,25 @@
+#ifndef PROPERTIES_TRAITS_HPP
+#define PROPERTIES_TRAITS_HPP
+
+// These actually determine the mutability of the entire edge set.
+struct property_vector_tag : unstable_remove_tag { };
+struct property_list_tag : stable_mutators_tag { };
+
+template <typename Props>
+struct properties_traits
+{ typedef typename Props::category category; };
+
+template <typename Props>
+typename properties_traits<Props>::category
+properties_category(Props const&)
+{ return typename properties_traits<Props>::category(); }
+
+template <typename Edge, typename Alloc>
+struct properties_traits<property_vector<Edge, Alloc>>
+{ typedef property_vector_tag category; };
+
+template <typename Edge, typename Alloc>
+struct properties_traits<property_list<Edge, Alloc>>
+{ typedef property_list_tag category; };
+
+#endif
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 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -25,7 +25,6 @@
// 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;
}
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 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -6,51 +6,25 @@
#include <boost/graphs/incidence_set.hpp>
#include "typestr.hpp"
+#include "incidence_traits.hpp"
using namespace std;
using namespace boost;
-struct incidence_vector_tag : unstable_remove_tag { };
-struct incidence_list_tag : stable_descriptor_tag { };
-struct incidence_set_tag : stable_descriptor_tag { };
-
-template <typename IncStore>
-struct incidence_traits
-{ typedef typename IncStore::category category; };
-
-template <typename IncStore>
-typename incidence_traits<IncStore>::category
-incidence_category(IncStore const&)
-{ return typename incidence_traits<IncStore>::category(); }
-
-template <typename Edge, typename Alloc>
-struct incidence_traits<incidence_vector<Edge, Alloc>>
-{ typedef incidence_vector_tag category; };
-
-template <typename Edge, typename Alloc>
-struct incidence_traits<incidence_list<Edge, Alloc>>
-{ typedef incidence_list_tag category; };
-
-template <typename Edge, typename Comp, typename Alloc>
-struct incidence_traits<incidence_set<Edge, Comp, Alloc>>
-{ typedef incidence_set_tag category; };
-
-
-
typedef index_descriptor<size_t> VertexDesc;
typedef index_descriptor<size_t> PropDesc;
typedef std::pair<VertexDesc, PropDesc> Edge;
typedef allocator<Edge> Alloc;
typedef std::less<VertexDesc> Compare;
-
-
template <typename IncStore>
-void test_remove(IncStore& incs, stable_descriptor_tag)
+void test_remove(IncStore& incs, stable_mutators_tag)
{
// Kind of strange, but we can actually construct some types of descriptors
// withou an iterator.
+ size_t n = incs.size();
incs.remove(incs.find(VertexDesc(0)));
+ BOOST_ASSERT(incs.size() == n - 1);
cout << " * num incs after removing " << incs.size() << endl;
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -5,17 +5,21 @@
#include <boost/graphs/property_list.hpp>
#include "typestr.hpp"
+#include "properties_traits.hpp"
using namespace std;
using namespace boost;
+
typedef int EdgeProperties;
typedef descriptor_traits<std::list<int>>::descriptor_type IncDesc;
template <typename PropSet>
-void test_remove(PropSet& props, stable_descriptor_tag)
+void test_remove(PropSet& props, stable_mutators_tag)
{
+ size_t n = props.size();
props.remove(props.find(5));
+ BOOST_ASSERT(props.size() == n - 1);
std::cout << "num props after remove: " << props.size() << endl;
}
@@ -27,18 +31,19 @@
void test()
{
typedef typename PropSet::property_descriptor PropDesc;
- typedef typename descriptor_traits<typename PropSet::store_type>::descriptor_stability Stability;
cout << "--- " << typestr<PropSet>() << " ---" << endl;
// Add some properties
+ size_t const N = 10;
PropSet props;
- for(int i = 0; i < 10; ++i) {
+ for(size_t i = 0; i < N; ++i) {
props.add(i);
}
+ BOOST_ASSERT(props.size() == N);
cout << "num props after build: " << props.size() << endl;
- test_remove(props, Stability());
+ test_remove(props, properties_category(props));
}
int main()
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 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -7,12 +7,13 @@
#include <boost/graphs/vertex_map.hpp>
#include "typestr.hpp"
+#include "vertices_traits.hpp"
using namespace std;
using namespace boost;
-struct no_remove_tag { };
-struct has_remove_tag { };
+struct unlabled_vertex_tag { };
+struct labeled_vertex_tag { };
// A fake vertex type.
struct Vertex
@@ -32,59 +33,48 @@
int value;
};
-template <typename Store>
-void populate(Store& verts, sequence_tag)
+template <typename Verts>
+void populate(Verts& verts, simple_vertex_store_tag)
{
for(int i = 0; i < 5; ++i) {
verts.add(i);
}
}
-
-template <typename Store>
-void populate(Store& verts, simple_associative_container_tag)
-{
- for(int i = 0; i < 5; ++i) {
- verts.add(i);
- }
-}
-
-template <typename Store>
-void populate(Store& verts, pair_associative_container_tag)
+template <typename Verts>
+void populate(Verts& verts, mapped_vertex_store_tag)
{
for(int i = 0; i < 5; ++i) {
verts.add(i, 2 * i);
}
}
-template <typename Store>
-void test_remove(Store& verts, stable_descriptor_tag)
+template <typename Verts>
+void test_remove(Verts& verts, stable_mutators_tag)
{
verts.remove(3);
cout << "num verts after remove: " << verts.size() << endl;
}
-template <typename VertexSet>
-void test_remove(VertexSet& vs, unstable_remove_tag)
+template <typename Verts>
+void test_remove(Verts& vs, unstable_remove_tag)
{ /* Noop for unstable removes */ }
-template <typename VertexSet>
+template <typename Verts>
void test()
{
- typedef typename VertexSet::template store<Vertex>::type Store;
- typedef typename VertexSet::descriptor_type Descriptor;
- typedef typename Store::store_type StoreImpl;
-
- cout << "--- " << typestr<VertexSet>() << " ---" << endl;
+ typedef typename Verts::template store<Vertex>::type Store;
+ typedef typename Verts::descriptor_type Descriptor;
Store verts;
+ cout << "--- " << typestr(verts) << " ---" << endl;
- populate(verts, typename container_traits<StoreImpl>::category());
+ populate(verts, vertices_category(verts));
cout << "num verts after building: " << verts.size() << endl;
Descriptor d = verts.find(3);
cout << "value of vertex properties: " << verts.properties(d) << endl;
- test_remove(verts, typename descriptor_traits<StoreImpl>::descriptor_stability());
+ test_remove(verts, vertices_category(verts));
}
int main()
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/vertices_traits.hpp 2008-07-07 11:43:06 EDT (Mon, 07 Jul 2008)
@@ -0,0 +1,39 @@
+
+#ifndef VERTICES_TRAITS_HPP
+#define VERTICES_TRAITS_HPP
+
+struct simple_vertex_store_tag { };
+struct mapped_vertex_store_tag { };
+
+struct vertex_vector_tag : simple_vertex_store_tag, unstable_remove_tag { };
+struct vertex_list_tag : simple_vertex_store_tag, stable_mutators_tag { };
+struct vertex_set_tag : simple_vertex_store_tag, stable_mutators_tag { };
+struct vertex_map_tag : mapped_vertex_store_tag, stable_mutators_tag { };
+
+template <typename Verts>
+struct vertices_traits
+{ typedef typename Verts::category category; };
+
+template <typename Verts>
+typename vertices_traits<Verts>::category
+vertices_category(Verts const&)
+{ return typename vertices_traits<Verts>::category(); }
+
+
+template <typename Vertex, typename Alloc>
+struct vertices_traits<vertices_vector<Vertex, Alloc>>
+{ typedef vertex_vector_tag category; };
+
+template <typename Vertex, typename Alloc>
+struct vertices_traits<vertices_list<Vertex, Alloc>>
+{ typedef vertex_list_tag category; };
+
+template <typename Vertex, typename Compare, typename Alloc>
+struct vertices_traits<vertices_set<Vertex, Compare, Alloc>>
+{ typedef vertex_set_tag category; };
+
+template <typename Vertex, typename Key, typename Compare, typename Alloc>
+struct vertices_traits<vertices_map<Vertex, Key, Compare, Alloc>>
+{ typedef vertex_map_tag category; };
+
+#endif
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