[Boost-commit] svn:boost r49992 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost include/boost/descriptors include/boost/graphs include/boost/graphs/adjacency_list include/boost/graphs/adjacency_list/es include/boost/graphs/adjacency_list/vs test

Subject: [Boost-commit] svn:boost r49992 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost include/boost/descriptors 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-28 12:24:27

Author: asutton
Date: 2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
New Revision: 49992
URL: http://svn.boost.org/trac/boost/changeset/49992

Log:
- Reintegrated descriptor kinds to help differentiate descriptors at the
  type level. Integrated changes into the vertex store.
- Implemented find_vertex for undirected graphs and propagated the required
  fixes thru the vertex store.
- Implemented label accesssors for undirected graphs.

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp                           |     9 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors.hpp                            |   112 ++++++++++++-------                     
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp           |    11 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp            |    11 +                                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp       |    17 ++-                                     
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp          |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp      |     7                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp           |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp        |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp |    49 ++++++++                                
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp     |   219 +++++++++++++++++++++++++++++++-------- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/list.hpp          |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/map.hpp           |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/set.hpp           |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vs/vector.hpp        |     3                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/label.hpp                           |    63 ++++++++++-                             
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp                                      |    28 ++++                                    
   17 files changed, 417 insertions(+), 130 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/counted_list.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -6,6 +6,7 @@
 #include <algorithm>
 
 #include <boost/containers.hpp>
+#include <boost/descriptors.hpp>
 
 namespace boost {
 
@@ -145,10 +146,12 @@
 };
 
 // Specialize descriptor traits
-template <typename T, typename Alloc, typename List>
-struct descriptor_traits<counted_list<T, Alloc, List>>
+template <typename T, typename Alloc, typename List, typename Kind>
+struct descriptor_traits<counted_list<T, Alloc, List>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::list<T, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 
 };

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -2,6 +2,8 @@
 #ifndef BOOST_DESCRIPTORS_HPP
 #define BOOST_DESCRIPTORS_HPP
 
+#include <boost/type_traits/is_same.hpp>
+
 // Pull the container traits.
 #include "containers.hpp"
 
@@ -80,27 +82,29 @@
  * containers. This structure must be specialized by each container. By default
  * the types and properties of this class reference nested types of the
  * container, which are basically doomed to fail.
- *
- * This inherits a specialized version of container traits from boost/pending.
  */
-template <typename Container>
+template <typename Container, typename Kind = basic_descriptor_kind>
 struct descriptor_traits
 {
+    typedef Kind descriptor_kind;
     typedef typename Container::descriptor_type descriptor_type;
     typedef typename Container::mutator_stability mutator_stability;
 };
 
+template <typename Container, typename Kind>
+struct descriptor_traits<Container const, Kind> : descriptor_traits<Container, Kind> { };
+
 /**
  * Given a container and a valid iterator into the container, return a
  * descriptor to the object being pointed at. The descriptor is guaranteed to
  * be at least as long as the iterator, generally longer. If the given iterator
  * is past the end of the container, then the returned descriptor is null.
  */
-template <typename Container>
-inline typename descriptor_traits<Container>::descriptor_type
-make_descriptor(Container& c, typename Container::iterator i)
+template <typename Container, typename Kind = basic_descriptor_kind>
+inline typename descriptor_traits<Container, Kind>::descriptor_type
+make_descriptor(Container& c, typename Container::iterator i, Kind = Kind())
 {
-    typedef typename descriptor_traits<Container>::descriptor_type result_type;
+    typedef typename descriptor_traits<Container, Kind>::descriptor_type result_type;
     return i != c.end() ? result_type(c, i) : result_type();
 }
 
@@ -110,18 +114,38 @@
  * not been invalidated (e.g., removing an item from a vector). If the given
  * descriptor is null, then the returned iterator is past the end of the
  * container.
+ * @note Normally, I'd use descriptor traits instead of making the entire
+ * descriptor parameterized, but that isn't quite possible since the kind is
+ * not known and actually factored out of the return type.
  */
-template <typename Container>
+template <typename Container, typename Descriptor>
+inline typename Container::iterator
+make_iterator(Container& c, Descriptor d)
+{
+    static_assert(
+        is_same<
+            typename descriptor_traits<
+                Container,
+                typename Descriptor::descriptor_kind>
+            ::descriptor_type,
+            Descriptor
+        >::value,
+        "Descriptor does not describe Container"
+    );
+    return d ? d.get(c) : c.end();
+}
+
+template <typename Container, typename Descriptor>
 inline typename Container::iterator
-make_iterator(Container& c, typename descriptor_traits<Container>::descriptor_type d)
-{ return d ? d.get(c) : c.end(); }
+make_iterator(Container const& c, Descriptor d)
+{ return make_iterator(const_cast<Container&>(c), d); }
 
 
 /** Return the descriptor stability tag for the given container. */
-template <typename Container>
+template <typename Container, typename Kind = basic_descriptor_kind>
 inline typename descriptor_traits<Container>::mutator_stability
-mutator_stability(Container const&)
-{ return typename descriptor_traits<Container>::mutator_stability(); }
+mutator_stability(Container const&, Kind = Kind())
+{ return typename descriptor_traits<Container,Kind>::mutator_stability(); }
 
 // Metafunctions
 
@@ -129,13 +153,13 @@
  * Returns true if the cotnainer supports insert operations that do not
  * invalidate outstanding descriptors.
  */
-template <typename Container>
+template <typename Container, typename Kind = basic_descriptor_kind>
 struct has_insert_mutator
 {
     // True if not convertible to unstable_insert_tag.
     static bool const value =
         !boost::is_convertible<
-            typename descriptor_traits<Container>::descriptor_stability,
+            typename descriptor_traits<Container, Kind>::descriptor_stability,
             unstable_insert_tag
         >::value;
 };
@@ -144,66 +168,72 @@
  * Returns true if the container supports remove operations that do not
  * invalidate outstanding descriptors.
  */
-template <typename Container>
+template <typename Container, typename Kind = basic_descriptor_kind>
 struct has_remove_mutator
 {
     // True if not convertible to unstable_remove_tag.
     static bool const value =
         !boost::is_convertible<
-            typename descriptor_traits<Container>::descriptor_stability,
+            typename descriptor_traits<Container, Kind>::descriptor_stability,
             unstable_remove_tag
         >::value;
 };
 
 // Specializations
 
-// Vector
-template <typename T, typename Alloc>
-struct descriptor_traits<std::vector<T, Alloc>>
+template <typename T, typename Alloc, typename Kind>
+struct descriptor_traits<std::vector<T, Alloc>, Kind>
 {
-    typedef index_descriptor<typename std::vector<T, Alloc>::size_type> descriptor_type;
+    typedef index_descriptor<
+        typename std::vector<T, Alloc>::size_type, Kind
+    > descriptor_type;
     typedef unstable_remove_tag descriptor_stability;
 };
 
-// List
-template <typename T, typename Alloc>
-struct descriptor_traits<std::list<T, Alloc>>
+template <typename T, typename Alloc, typename Kind>
+struct descriptor_traits<std::list<T, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::list<T, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::list<T, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
 // TODO: Dequeue
 
-// Set
-template <typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::set<T, Comp, Alloc>>
+template <typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::set<T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::set<T, Comp, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
-// Multiset
-template <typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::multiset<T, Comp, Alloc>>
+template <typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::multiset<T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::multiset<T, Comp, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
-// Map
-template <typename Key, typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::map<Key, T, Comp, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::map<Key, T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::map<Key, T, Comp, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 
-// Multimap
-template <typename Key, typename T, typename Comp, typename Alloc>
-struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>>
+template <typename Key, typename T, typename Comp, typename Alloc, typename Kind>
+struct descriptor_traits<std::multimap<Key, T, Comp, Alloc>, Kind>
 {
-    typedef node_descriptor<blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>> descriptor_type;
+    typedef node_descriptor<
+        blob<sizeof(typename std::multimap<Key, T, Comp, Alloc>::iterator)>, Kind
+    > descriptor_type;
     typedef stable_mutators_tag descriptor_stability;
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/index_descriptor.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -11,13 +11,14 @@
  * The index_descriptor simply maintains the descriptor as an index into the
  * given offset.
  */
-template <typename Index>
+template <typename Index, typename Kind = basic_descriptor_kind>
 struct index_descriptor
 {
     typedef index_descriptor<Index> this_type;
     typedef Index this_type::*unspecified_bool_type;
 
     typedef Index descriptor_type;
+    typedef Kind descriptor_kind;
 
     inline index_descriptor()
         : value(-1)
@@ -75,15 +76,15 @@
 };
 
 // A hash function for indexed descriptors.
-template <typename Index>
-std::size_t hash_value(index_descriptor<Index> const& x)
+template <typename Index, typename Kind>
+std::size_t hash_value(index_descriptor<Index, Kind> const& x)
 {
     using boost::hash_value;
     return hash_value(x.value);
 }
 
-template <typename Index>
-std::ostream& operator<<(std::ostream& os, index_descriptor<Index> const& x)
+template <typename Index, typename Kind>
+std::ostream& operator<<(std::ostream& os, index_descriptor<Index, Kind> const& x)
 { return os << x.value; }
 
 } /* namespace boost */

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/descriptors/node_descriptor.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -11,13 +11,14 @@
  * container iterator is just a pattern for the actual iterator and has no
  * real type (it's opaque).
  */
-template <typename Blob>
+template <typename Blob, typename Kind = basic_descriptor_kind>
 struct node_descriptor
 {
     typedef node_descriptor<Blob> this_type;
     typedef Blob this_type::*unspecified_bool_type;
 
     typedef Blob descriptor_type;
+    typedef Kind descriptor_kind;
 
     inline node_descriptor()
         : value()
@@ -75,15 +76,15 @@
 };
 
 // A hash function for indexed descriptors.
-template <typename Blob>
-std::size_t hash_value(node_descriptor<Blob> const& x)
+template <typename Blob, typename Kind>
+std::size_t hash_value(node_descriptor<Blob, Kind> 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)
+template <typename Blob, typename Kind>
+std::ostream& operator<<(std::ostream& os, node_descriptor<Blob, Kind> const& d)
 { return os << hash_value(d); }
 
 } /* namespace boost */

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -8,7 +8,15 @@
 #include <boost/graphs/label.hpp>
 #include <boost/graphs/edge.hpp>
 
+// Defines a kind of edge descriptor.
+struct edge_descriptor_kind { };
+
+#include <boost/graphs/adjacency_list/es/vector.hpp>
+#include <boost/graphs/adjacency_list/es/list.hpp>
+#include <boost/graphs/adjacency_list/es/set.hpp>
+
 // Include specializations for the label and edge interfaces.
+// TODO: Migrate code from these files to here.
 #include <boost/graphs/adjacency_list/es/seq_edge.hpp>
 #include <boost/graphs/adjacency_list/es/assoc_edge.hpp>
 
@@ -27,9 +35,10 @@
 template <typename Store>
 struct edge_store_traits
 {
-    typedef typename Store::value_type edge_type;
+    typedef typename descriptor_traits<Store, edge_descriptor_kind>::descriptor_kind
+        edge_descriptor;
 
-    // These are provided for convenience.
+    typedef typename Store::value_type edge_type;
     typedef typename edge_traits<edge_type>::edge_ends edge_ends;
     typedef typename label_traits<edge_type>::label_type edge_label;
 };
@@ -148,8 +157,4 @@
 
 } } } /* namespace boost::graphs::adjacency_list */
 
-// Type selectors
-#include <boost/graphs/adjacency_list/es/vector.hpp>
-#include <boost/graphs/adjacency_list/es/set.hpp>
-
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/list.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -13,7 +13,8 @@
 struct edge_list
 {
     typedef typename descriptor_traits<
-        counted_list<int, Alloc<int>>
+        counted_list<int, Alloc<int>>,
+        edge_descriptor_kind
     >::descriptor_type edge_descriptor;
 
     // Ends must be a pair of vertices.

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/seq_edge.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -7,10 +7,9 @@
 // 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.
+// TODO: I'm a little worried about the possibility of type collisions. I may
+// be required to introduce a tagging system to label and edge traits to help
+// distinguish the intent of the specialization.
 
 template <typename VertexDesc, typename EdgeLabel>
 struct label_traits<std::pair<std::pair<VertexDesc, VertexDesc>, EdgeLabel>>

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/set.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -20,7 +20,8 @@
 struct edge_set
 {
     typedef typename descriptor_traits<
-        std::set<int, Compare<int>, Alloc<int>>
+        std::set<int, Compare<int>, Alloc<int>>,
+        edge_descriptor_kind
     >::descriptor_type edge_descriptor;
 
     // This quietly implements a map, not a set because we'll be using the

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/es/vector.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -13,7 +13,8 @@
 struct edge_vector
 {
     typedef typename descriptor_traits<
-        std::vector<int, Alloc<int>>
+        std::vector<int, Alloc<int>>,
+        edge_descriptor_kind
     >::descriptor_type edge_descriptor;
 
     // Ends must be a pair of vertices.

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -40,18 +40,28 @@
     typedef typename VertexStore::key_type vertex_key;
     typedef typename vertex_store::size_type vertices_size_type;
 
+    vertex_label& operator[](vertex_descriptor d)
+    { return vs::label(v, d); }
+    vertex_label const& operator[](vertex_descriptor d) const
+    { return vs::label(v, d); }
+
+    // TODO: Implement me
+    edge_label& operator[](edge_descriptor d)
+    { return edge_label(); }
+    edge_label const& operator[](edge_descriptor d) const
+    { return edge_label(); }
+
 public:
     vertex_store v;
     edge_store e;
 };
 
+/** @name Add Vertex */
+//@{
 template <typename VL, typename EL, typename VS, typename ES, typename IS>
 typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
 add_vertex(undirected_graph<VL,EL,VS,ES,IS>& g)
-{
-    typedef typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label VertexLabel;
-    return vs::insert(g.v, VertexLabel());
-}
+{ return vs::insert(g.v, typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label()); }
 
 template <typename VL, typename EL, typename VS, typename ES, typename IS>
 typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
@@ -65,9 +75,38 @@
            typename undirected_graph<VL,EL,VS,ES,IS>::vertex_key const& k,
            typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label&& l)
 { return vs::insert(g.v, k, l); }
+//@}
 
+/** @name Find Vertex
+ * Return a descriptor to the first vertex found with the given label.
+ *
+ * There are two overloads of this function: one for finding vertices based on
+ * their label, the other based on their key. The latter is only applicable
+ * for graphs with mapped vertices.
+ *
+ * @note, These overloads are ambigous for mapped vertex graphs if the key
+ * and label are the same type. We should probably provide special function to
+ * differentiate these functions.
+ */
+//@{
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+find_vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
+            typename undirected_graph<VL,EL,VS,ES,IS>::vertex_label const& l)
+{ return vs::find(g.v, l); }
 
-
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor
+find_vertex(undirected_graph<VL,EL,VS,ES,IS> const& g,
+            typename undirected_graph<VL,EL,VS,ES,IS>::vertex_key const& k)
+{ return vs::find(g.v, k); }
+//@}
+
+/** @name Remove Vertex
+ * Remove the given vertex from the graph.
+ */
+//@{
+//@}
 
 template <typename VL, typename EL, typename VS, typename ES, typename IS>
 typename undirected_graph<VL,EL,VS,ES,IS>::vertices_size_type

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -12,6 +12,9 @@
 
 #include <boost/graphs/label.hpp>
 
+// Define a common descriptor kind for these containers.
+struct vertex_descriptor_kind { };
+
 // 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>
@@ -31,16 +34,56 @@
 // - Key - a key maapping to a vertex.
 //
 // Supported operations are:
-// - 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)
-// - void       vs_remove_vertex    (Store, Iterator)
-// - bool       vs_empty            (Store)
-// - Size       vs_size             (Store)
+// - Descriptor insert      (Store, Vertex)
+// - Descriptor insert      (Store, Key, Vertex)
+// - Result     try_insert  (Store, Vertex)
+// - Result     try_insert  (Store, Key, Vertex)
+// - Iterator   find        (Store, Label)
+// - void       remove      (Store, Descriptor)
+// - bool       empty       (Store)
+// - Size       size        (Store)
+
+namespace boost { namespace graphs {
+
+// Specializations for label traits, etc.
+
+// concept_map HasLabel<...> for most vertex types (vector, list, map).
+//@{
+template <typename Edges, typename Label>
+struct label_traits<std::pair<Edges, Label>>
+{ typedef Label label_type; };
+
+template <typename Edges, typename Label>
+Label& label(std::pair<Edges, Label>& v)
+{ return v.second; }
+
+template <typename Edges, typename Label>
+Label const& label(std::pair<Edges, Label> const& v)
+{ return v.second; }
+//@}
+
+/** @internal @name HasLabel<VertexSet>
+ * This concept map removes the const-ness of the label when accessed as an
+ * l-value. This permits the ability to modify parts of labels that are not
+ * actually involved in a comparison. To be fair, it also allows the ability to
+ * modify the parts that are so-involved so care must be taken. In general,
+ * this does permit a more natural syntax for vertex-set graphs.
+ */
+//@{
+template <typename Edges, typename Label>
+struct label_traits<std::pair<Label const, Edges>>
+{ typedef Label label_type; };
+
+template <typename Edges, typename Label>
+Label& label(std::pair<Label const, Edges>& v)
+{ return const_cast<Label&>(v.first); }
+
+template <typename Edges, typename Label>
+Label const& label(std::pair<Label const, Edges> const& v)
+{ return v.first; }
+//@}
 
-namespace boost { namespace graphs { namespace adjacency_list {
+namespace adjacency_list {
 
 /**
  * The incidence traits class provides a means of accessing type information
@@ -49,11 +92,12 @@
 template <typename Vertex>
 struct vertex_traits
 {
-    typedef typename Vertex::label_type vertex_label;
+    typedef typename label_traits<Vertex>::label_type vertex_label;
     typedef typename Vertex::vertex_edges vertex_edges;
 };
 
-// Specialization for any vertex type implemented as a pair - which all are.
+// Specialization for any vertex type implemented as a pair - which most are
+// implemented this way.
 template <typename Edges, typename Label>
 struct vertex_traits<std::pair<Edges, Label>>
 {
@@ -61,7 +105,7 @@
     typedef Edges vertex_edges;
 };
 
-// Specialization for vertex_set, which quietly implements the set as a map.
+// Specialization for vertex_set, which is actually a map.
 template <typename Edges, typename Label>
 struct vertex_traits<std::pair<Label const, Edges>>
 {
@@ -77,7 +121,13 @@
 template <typename Store>
 struct vertex_store_traits
 {
+    typedef typename descriptor_traits<Store, vertex_descriptor_kind>::descriptor_type
+        vertex_descriptor;
+    typedef typename Store::size_type vertices_size_type;
+
     typedef typename Store::value_type vertex_type;
+    typedef typename vertex_traits<vertex_type>::vertex_label vertex_label;
+    typedef typename vertex_traits<vertex_type>::vertex_edges vertex_edges;
 };
 
 // Specialization for vertex map. This will not match for vertex set since the
@@ -85,43 +135,82 @@
 template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
 struct vertex_store_traits<std::map<Key, std::pair<Edges, Label>, Compare, Alloc>>
 {
-    typedef typename std::map<Key, std::pair<Edges, Label>, Compare, Alloc>::mapped_type vertex_type;
+    typedef std::map<Key, std::pair<Edges, Label>, Compare, Alloc> base_type;
+
+    typedef typename descriptor_traits<base_type, vertex_descriptor_kind>::descriptor_type
+        vertex_descriptor;
+    typedef typename base_type::size_type vertices_size_type;
+
+    typedef typename base_type::mapped_type vertex_type;
+    typedef typename vertex_traits<vertex_type>::vertex_label vertex_label;
+    typedef typename vertex_traits<vertex_type>::vertex_edges vertex_edges;
 };
 
 namespace vs {
 
 namespace detail {
 
-    // For some reason (possbily a GCC bug), we have to do a better job
-    // specializing the make_vertex functions. No idea why... Either way, this
-    // looks a bit hacky.
+    /** @internal @name Make Vertex
+     * For some reason (possbily a GCC bug), we have to do a better job
+     * specializing the make_vertex functions. No idea why... Either way, this
+     * looks a bit hacky.
+     */
+    //@{
     template <typename Vertex, typename Alloc, typename Label>
     inline Vertex
     make_vertex(std::vector<Vertex, Alloc> const&, Label&& l)
-    {
-        typedef typename vertex_traits<Vertex>::vertex_edges Edges;
-        return Vertex(Edges(), l);
-    }
+    { return Vertex(typename vertex_traits<Vertex>::vertex_edges(), l); }
 
     template <typename Vertex, typename Alloc, typename Label>
     inline Vertex
     make_vertex(counted_list<Vertex, Alloc> const&, Label&& l)
-    {
-        typedef typename vertex_traits<Vertex>::vertex_edges Edges;
-        return Vertex(Edges(), l);
-    }
+    { return Vertex(typename vertex_traits<Vertex>::vertex_edges(), l); }
 
-    // Specialization for vertex_set
+    // Overload for vertex_set
     template <typename Label, typename Edges, typename Compare, typename Alloc>
     inline std::pair<Label const, Edges>
     make_vertex(std::map<Label, Edges, Compare, Alloc> const&, Label const& l)
     { return std::make_pair(l, Edges()); }
 
-    // Specialization for vertex_map
+    // Overload for vertex_map
     template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
     inline std::pair<Edges, Label>
     make_vertex(std::map<Key, std::pair<Edges, Label>, Compare, Alloc> const&, Label&& l)
     { return std::make_pair(l, Edges()); }
+    //@}
+
+    /** @internal @name Get Vertex
+     * Get the part of a stored vertex that represents just the vertex - the
+     * label and edges. Generally, this is the same as dereferencing an,
+     * iterator, but differs for graphs with mapped vertices.
+     *
+     * There may be some weirdness with the iterators and the container since
+     * the container is passed as const in some cases, but the iterator is not
+     * a const_iterator.
+     */
+    //@{
+    // Overload for non-mapped vertices.
+    template <typename Store>
+    inline typename Store::value_type& get_vertex(Store&, typename Store::iterator i)
+    { return *i; }
+
+    template <typename Store>
+    inline typename Store::value_type const& get_vertex(Store const&, typename Store::iterator i)
+    { return *i; }
+
+    // Overload(s) for vertex_map
+    template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
+    inline std::pair<Edges, Label>&
+    get_vertex(std::map<Key, std::pair<Edges, Label>, Compare, Alloc>&,
+               typename std::map<Key, std::pair<Edges, Label>, Compare, Alloc>::iterator i)
+    { return i->second; }
+
+    template <typename Key, typename Edges, typename Label, typename Compare, typename Alloc>
+    inline std::pair<Edges, Label> const&
+    get_vertex(std::map<Key, std::pair<Edges, Label>, Compare, Alloc> const&,
+               typename std::map<Key, std::pair<Edges, Label>, Compare, Alloc>::iterator i)
+    { return i->second; }
+    //@}
 
 
     // Iterate and compare for sequences.
@@ -132,7 +221,7 @@
         return std::find_if(
             store.begin(),
             store.end(),
-            bind2nd(labelled_equal_to<typename Store::value_type>(), l));
+            has_label_equal_to(l));
     }
 
     // Associative containers already forward the label as the key, so we just
@@ -180,28 +269,31 @@
  */
 //@{
 /** Insert a vertex into the container. */
-template <typename Store, typename Label>
-inline typename descriptor_traits<Store>::descriptor_type
-insert(Store& store, Label&& l)
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_descriptor
+insert(Store& store,
+       typename vertex_store_traits<Store>::vertex_label&& l)
 {
     typedef typename Store::iterator Iterator;
     Iterator i = container_insert(store, detail::make_vertex(store, l));
-    return make_descriptor(store, i);
+    return make_descriptor(store, i, vertex_descriptor_kind());
 }
 
 /** Insert a vertex into the container, mapped to the given key. */
-template <typename Store, typename Key, typename Label>
-inline typename descriptor_traits<Store>::descriptor_type
-insert(Store& store, Key const& k, Label&& l)
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_descriptor
+insert(Store& store,
+       typename Store::key_type const& k,
+       typename vertex_store_traits<Store>::vertex_label&& l)
 {
     // TODO: This is a bit hacky w.r.t. the generic make_vertex function
     // in that it doesn't call it - but it probably should. For some reason,
     // the make_vertex that I think should match, doesn't.
     typedef typename Store::iterator Iterator;
     typedef typename vertex_store_traits<Store>::vertex_type Vertex;
-    typedef typename vertex_traits<Vertex>::vertex_edges Edges;
+    typedef typename vertex_store_traits<Store>::vertex_edges Edges;
     Iterator i = container_insert(store, std::make_pair(k, Vertex(Edges(), l)));
-    return make_descriptor(store, i);
+    return make_descriptor(store, i, vertex_descriptor_kind());
 }
 //@}
 
@@ -245,15 +337,18 @@
  */
 //@{
 template <typename Store, typename LabelOrKey>
-inline typename descriptor_traits<Store>::descriptor_type
+inline typename vertex_store_traits<Store>::vertex_descriptor
 find(Store& store, LabelOrKey const& lk)
-{ return make_descriptor(store, detail::dispatch_find(store, lk, container_category(store))); }
+{
+    typename Store::iterator i = detail::dispatch_find(store, lk, container_category(store));
+    return make_descriptor(store, i, vertex_descriptor_kind());
+}
 
 // Does not return a const iterator!
 template <typename Store, typename LabelOrKey>
-inline typename descriptor_traits<Store>::descriptor_type
+inline typename vertex_store_traits<Store>::vertex_descriptor
 find(Store const& store, LabelOrKey const& lk)
-{ return find(const_cast<Store&>(store), lk, container_category(store)); }
+{ return vs::find(const_cast<Store&>(store), lk); }
 //@}
 
 /**
@@ -263,23 +358,59 @@
  */
 //@{
 template <typename Store>
-void remove(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+inline void
+remove(Store& store, typename descriptor_traits<Store>::descriptor_type d)
 { detail::dispatch_remove(store, make_iterator(store, d), container_category(store)); }
 //@}
 
+/** @name Vertex Object */
+//@{
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_type&
+vertex(Store& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return detail::get_vertex(store, make_iterator(store, v)); }
+
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_type const&
+vertex(Store const& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return detail::get_vertex(store, make_iterator(store, v)); }
+//@}
+
+/** @name Vertex Label
+ *
+ * @todo There's a problem with vertex_sets that causes the compiler to select
+ * a non-const return type and then causes an error because we can't convert
+ * the const label to the non-const label. One solution would be to provide an
+ * internal overload that casted out the const - this isn't a terribly bad idea
+ * since its easily possible that the only part of the label required to be
+ * immutable is the part involved in the comparison and sorting.
+ */
+//@{
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_label&
+label(Store& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return graphs::label(vertex(store, v)); }
+
+template <typename Store>
+inline typename vertex_store_traits<Store>::vertex_label const&
+label(Store const& store, typename vertex_store_traits<Store>::vertex_descriptor v)
+{ return graphs::label(vertex(store, v)); }
+//@}
+
 /** Return the number of elements in the vertex store. */
 template <typename Store>
-typename Store::size_type size(Store const& store)
+inline typename vertex_store_traits<Store>::vertices_size_type
+size(Store const& store)
 { return store.size(); }
 
 /** Return true if the store is empty. */
 template <typename Store>
-bool empty(Store const& store)
+inline bool empty(Store const& store)
 { return store.empty(); }
 
 /** Clear the vertex store. */
 template <typename Store>
-void clear(Store& store)
+inline void clear(Store& store)
 { store.clear(); }
 
 } /* namespace vs */

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -15,7 +15,8 @@
     typedef void key_type;
 
     typedef typename descriptor_traits<
-        std::list<int, Alloc<int>>
+        std::list<int, Alloc<int>>,
+        vertex_descriptor_kind
     >::descriptor_type vertex_descriptor;
 
     template <typename Edges, typename Label>

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -22,7 +22,8 @@
     typedef Key key_type;
 
     typedef typename descriptor_traits<
-        std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>>
+        std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>>,
+        vertex_descriptor_kind
     >::descriptor_type vertex_descriptor;
 
     template <typename Edges, typename Label>

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -21,7 +21,8 @@
     typedef void key_type;
 
     typedef typename descriptor_traits<
-        std::set<int, Compare<int>, Alloc<int>>
+        std::set<int, Compare<int>, Alloc<int>>,
+        vertex_descriptor_kind
     >::descriptor_type vertex_descriptor;
 
     // Quietly define a set as a map from label (which is the key being

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -15,7 +15,8 @@
     typedef void key_type;
 
     typedef typename descriptor_traits<
-        std::vector<int, Alloc<int>>
+        std::vector<int, Alloc<int>>,
+        vertex_descriptor_kind
     >::descriptor_type vertex_descriptor;
 
     template <typename Edges, typename Label>

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-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -9,29 +9,53 @@
 
 namespace boost { namespace graphs {
 
-/**
+/** @name Label Traits
  * The label traits class provides a mechanism for generically accessing
  * information about an object's built in label. A label is data associated
  * with either a vertex or edge.
  */
+//@{
 template <typename Object>
 struct label_traits
 {
     typedef typename Object::label_type label_type;
 };
 
+template <typename Object>
+struct label_traits<Object const> : label_traits<Object> { };
+//@}
+
 /** @name Label Access
  * Return a reference to the object's label. The generic implementation requires
  * the object to have a non-const label() member.
+ *
+ * @note These functions are currently disabled because they seem to be hiding
+ * specializations. This is generally okay since these implemntations are
+ * never actually valid.
+ *
+ * @bug Overloading and Instantiation Problem
+ * There is some strange interplay with overloading during parsing and
+ * instantiation. Apparently, if any overloads are visible during parsing, then
+ * the selection of functions is restricted to that set of overloads during
+ * instantiation. If no overloads are found, then name resolution is fully
+ * deferred until instantiation.
+ *
+ * Here's the problem. Defining these functions will cause has_label_equal_to()
+ * to refer to these functions - which will almost always result in a compiler
+ * error when the function is instantiated in vs::dispatch_find(). Leaving these
+ * out will allow the correct overloads to be found.
+ *
+ * One solution might be to create a firewall by invoking a templated get_label
+ * function which is specialized by different parts of the library.
  */
 //@{
-template <typename Object>
-typename label_traits<Object>::label_type& label(Object& x)
-{ return x.label(); }
-
-template <typename Object>
-typename label_traits<Object>::label_type const& label(Object const& x)
-{ return x.label(); }
+// template <typename Object>
+// typename label_traits<Object>::label_type& label(Object& x)
+// { return x.label(); }
+//
+// template <typename Object>
+// typename label_traits<Object>::label_type const& label(Object const& x)
+// { return x.label(); }
 //@}
 
 /**
@@ -62,6 +86,29 @@
     typename Label = typename label_traits<Object>::label_type>
 struct labelled_less : labelled_compare<Object, std::less<Label>> { };
 
+/**
+ * A helper for find_if, returns true if an object has the given label.
+ * @note This is not a proper function object since the arguments to the
+ * function are not known ahead of time.
+ */
+template <typename Label>
+struct has_label_equal_to_func
+{
+    has_label_equal_to_func(Label const& l)
+        : lbl(l)
+    { }
+
+    template <typename Object>
+    bool operator()(Object const& x) const
+    { return label(x) == lbl; }
+
+    Label const& lbl;
+};
+
+// A generator the struct above. This is parameterized on the store rather th
+template <typename Label>
+has_label_equal_to_func<Label> has_label_equal_to(Label const& l)
+{ return has_label_equal_to_func<Label>(l); }
 
 } } /* namespace boost::graphs */
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp	2008-11-28 12:24:25 EST (Fri, 28 Nov 2008)
@@ -32,7 +32,8 @@
     node() : n() { }
     node(int n) : n(n) { }
 
-    bool operator<(node const& x) const { return n < x.n; }
+    bool operator==(node const& x) const    { return n == x.n; }
+    bool operator<(node const& x) const     { return n < x.n; }
 
     int n;
 };
@@ -47,10 +48,27 @@
 template <typename Graph>
 void add_vertices(Graph& g, mpl::false_)
 {
-    add_vertex(g);
+    add_vertex(g);  // This is really a test for unlabeled verts
     add_vertex(g, node(3));
     add_vertex(g, std::move(node(5)));
     BOOST_ASSERT(num_vertices(g) == 3);
+
+    // Test the non-cosnt find
+    {
+        typedef typename Graph::vertex_descriptor VertexDesc;
+        VertexDesc v = find_vertex(g, node(3));
+        BOOST_ASSERT(!v.is_null());
+        BOOST_ASSERT(g[v] == node(3));
+    }
+
+    // Test the const find.
+    {
+        Graph const& h = g;
+        typedef typename Graph::vertex_descriptor VertexDesc;
+        VertexDesc v = find_vertex(h, node(3));
+        BOOST_ASSERT(!v.is_null());
+        BOOST_ASSERT(h[v] == node(3));
+    }
 }
 
 template <typename Graph>
@@ -60,6 +78,12 @@
     add_vertex(g, "b", node(3));
     add_vertex(g, "c", std::move(node(5)));
     BOOST_ASSERT(num_vertices(g) == 3);
+
+    // Test the find also.
+    typedef typename Graph::vertex_descriptor VertexDesc;
+    VertexDesc v = find_vertex(g, "b");
+    BOOST_ASSERT(!v.is_null());
+    BOOST_ASSERT(g[v] == node(3));
 }
 
 template <typename Graph>