[Boost-commit] svn:boost r49821 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs/adjacency_list test

Subject: [Boost-commit] svn:boost r49821 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs/adjacency_list test
From: asutton_at_[hidden]
Date: 2008-11-18 00:01:59

Author: asutton
Date: 2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
New Revision: 49821
URL: http://svn.boost.org/trac/boost/changeset/49821

Log:
More work on vertex sets
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp   |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp    |     8 ++--                                    
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp    |     5 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_store.hpp  |    79 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp |     4 +-                                      
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp                                 |    52 +++++++++++++++++++++++--               
   6 files changed, 133 insertions(+), 19 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_list.hpp	2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -28,8 +28,8 @@
     template <typename Vertex>
     struct vertex_store
     {
-        typedef Alloc<Vertex> allocator_type;
-        typedef counted_list<Vertex, allocator_type> type;
+        typedef Alloc<Vertex> allocator;
+        typedef counted_list<Vertex, allocator> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_map.hpp	2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -4,8 +4,8 @@
 
 #include <map>
 
-#include <boost/descriptors.hpp>
-#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
+#include <boost/none.hpp>
+#include <boost/graphs/adjacency_list/vertex_store.hpp>
 
 namespace boost { namespace graphs { namespace adjacency_list {
 
@@ -30,11 +30,11 @@
     >::descriptor_type vertex_descriptor;
 
     template <typename Vertex>
-    struct store
+    struct vertex_store
     {
         typedef Alloc<std::pair<Key, Vertex>> allocator;
         typedef Compare<Key> compare;
-        typedef vertices_map<Vertex, Key, compare, allocator> type;
+        typedef std::map<Key, Vertex, compare, allocator> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_set.hpp	2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -24,8 +24,9 @@
 {
     typedef unused key_type;
 
-    typedef std::set<int, Compare<int>, Alloc<int>> dummy;
-    typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
+    typedef typename descriptor_traits<
+        std::set<int, Compare<int>, Alloc<int>>
+    >::descriptor_type vertex_descriptor;
 
     template <typename Vertex>
     struct vertex_store

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-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -2,6 +2,8 @@
 #ifndef BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
 #define BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
 
+#include <boost/concept_check.hpp>
+
 #include <boost/containers.hpp>
 #include <boost/descriptors.hpp>
 
@@ -19,6 +21,24 @@
 
 namespace detail
 {
+    // Try to add the vertex to an associative container. This is a simple
+    // delegation to the container.
+    template <typename Store, typename Vertex>
+    inline std::pair<typename Store::iterator, bool>
+    dispatch_vs_try_add(Store& store, Vertex&& v, associative_container_tag)
+    { return store.insert(v); }
+
+    // Try to add the vertex to a sequential container. Here, we want to search
+    // for the vertex (linear time operation) and either insert at the end
+    // or return an existing iterator.
+    template <typename Store, typename Vertex>
+    inline std::pair<typename Store::iterator, bool>
+    dispatch_vs_try_add(Store& store, Vertex&& v, sequence_tag)
+    {
+        typename Store::iterator i = vs_find_vertex(store, label(v));
+        return std::make_pair(i, i == store.end());
+    }
+
     // Iterate and compare for sequences.
     template <typename Store, typename Label>
     inline typename Store::iterator
@@ -52,26 +72,66 @@
     inline typename Store::const_iterator
     dispatch_vs_find(Store const& store, Label const& l, associative_container_tag)
     { return store.find(l); }
-}
 
+    // Explicitly remove the ability use this function, by failing a concept
+    // check when it is instantiated.
+    template <typename Store>
+    void dispatch_vs_remove(Store&, typename Store::iterator, vector_tag)
+    { function_requires(Integer<Store>()); }
 
-/**
+    template <typename Store, typename Tag>
+    void dispatch_vs_remove(Store& store, typename Store::iterator i, Tag)
+    { store.erase(i); }
+
+
+} /* namespace detail */
+
+/** @name Add Vertex
  * Add a vertex to the given store, returning an iterator to the new vertex
  * vertex. The semantics and performance of this function depend on the kind
  * of vertex store.
  */
+//@{
+/** Insert a vertex into the container. */
 template <typename Store, typename Vertex>
 inline typename Store::iterator
 vs_add_vertex(Store& store, Vertex&& v)
 { return container_insert(store, v); }
 
+/** Insert a vertex into the container, mapped to the given key. */
+template <typename Store, typename Key, typename Vertex>
+inline typename Store::iterator
+vs_add_vertex(Store& store, Key const& k, Vertex&& v)
+{ return container_insert(store, std::make_pair(k, v)); }
+//@}
+
+/** @name Try to Add Vertex
+ * Try to add a vertex to the container, failing to add if a vertex already
+ * exists. This variant is only appropriate for labelled, unique vertices and
+ * associative vertex stores. However, it can be adapted to sequences in
+ * linear time.
+ */
+//@{
+template <typename Store, typename Vertex>
+inline std::pair<typename Store::iterator, bool>
+vs_try_add_vertex(Store& store, Vertex&& v)
+{ return detail::dispatch_vs_try_add(store, v, container_category(store)); }
+
+// There are no mapped linear sequences, so we can just rely on the fact that
+// this is a pair associative container. In fact, this actually requires that
+// Store model the UniqueAssociativeContainer concept.
+template <typename Store, typename Key, typename Vertex>
+inline std::pair<typename Store::iterator, bool>
+vs_try_add_vertex(Store& store, Key const& k, Vertex&& v)
+{ return store.insert(std::make_pair(k, v)); }
+//@}
+
 /** @name Find Vertex
  * Return an iterator to the vertex that matches the given label. This is
  * only applicable to labelled vertex types. The returned iterator will be
  * equivalent to store.end() if no such vertex is found.
  */
 //@{
-
 template <typename Store, typename Label>
 inline typename Store::iterator
 vs_find_vertex(Store& store, Label const& l)
@@ -82,8 +142,19 @@
 vs_find_vertex(Store const& store, Label const& l)
 { return detail::dispatch_vs_find(store, l, container_category(store)); }
 //@}
-// template <typename 
 
+/**
+ * @name Remove Vertex
+ * Remove the vertex from the store. This will only remove the vertex from the
+ * store, it cannot operate on edges.
+ */
+//@{
+// Since all container support a positional erase.
+// TODO: Can I make this fail to compile if Store is 
+template <typename Store>
+void vs_remove_vertex(Store& store, typename Store::iterator i)
+{ detail::dispatch_vs_remove(store, i, container_category(store)); }
+//@}
 } } } /* namespace boost::graphs::adjacency_list */
 
 #endif

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/vertex_vector.hpp	2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -31,8 +31,8 @@
     template <typename Vertex>
     struct vertex_store
     {
-        typedef Alloc<Vertex> allocator_type;
-        typedef std::vector<Vertex, allocator_type> type;
+        typedef Alloc<Vertex> allocator;
+        typedef std::vector<Vertex, allocator> type;
     };
 };
 

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/vertex_store.cpp	2008-11-18 00:01:59 EST (Tue, 18 Nov 2008)
@@ -8,6 +8,9 @@
 #include <boost/graphs/adjacency_list/vertex_set.hpp>
 #include <boost/graphs/adjacency_list/vertex_map.hpp>
 
+#include "typestr.hpp"
+
+
 using namespace std;
 using namespace boost;
 using namespace boost::graphs::adjacency_list;
@@ -16,6 +19,10 @@
 {
     typedef string label_type;  // Adaptor for vertex_traits
 
+    my_vertex()
+        : _label()
+    { }
+
     my_vertex(string const& x)
         : _label(x)
     { }
@@ -26,6 +33,42 @@
     string _label;
 };
 
+struct simple_container_tag : virtual sequence_tag, virtual simple_associative_container_tag { };
+struct pair_container_tag : pair_associative_container_tag { };
+
+simple_container_tag container_arity(vector_tag) { return simple_container_tag(); }
+simple_container_tag container_arity(list_tag) { return simple_container_tag(); }
+simple_container_tag container_arity(set_tag) { return simple_container_tag(); }
+pair_container_tag container_arity(map_tag) { return pair_container_tag(); }
+
+template <typename Store>
+void add_verts(Store& store, simple_container_tag)
+{
+    typedef typename Store::iterator Iterator;
+    typedef typename Store::value_type Vertex;
+    vs_add_vertex(store, Vertex("b"));
+    Iterator iter = vs_add_vertex(store, Vertex("a"));
+
+    vs_remove_vertex(store, iter);
+
+    // Try to re-add a vertex.
+    pair<Iterator, bool> i = vs_try_add_vertex(store, Vertex("b"));
+    cout << "re-add: " << i.second << "\n";
+}
+
+template <typename Store>
+void add_verts(Store& store, pair_container_tag)
+{
+    typedef typename Store::iterator Iterator;
+    typedef typename Store::mapped_type Vertex;
+    vs_add_vertex(store, "a", Vertex());
+    vs_add_vertex(store, "b", Vertex());
+
+    // Try to re-add a vertex.
+    pair<Iterator, bool> i = vs_try_add_vertex(store, string("b"), Vertex());
+    cout << "re-add: " << i.second << "\n";
+}
+
 template <typename Store>
 void test()
 {
@@ -35,9 +78,7 @@
 
     Store store;
 
-    // Add some vertices
-    vs_add_vertex(store, Vertex("b"));
-    vs_add_vertex(store, Vertex("a"));
+    add_verts(store, container_arity(container_category(store)));
 
     // Find a verts
     StoreIterator i = vs_find_vertex(store, string("b"));
@@ -49,10 +90,11 @@
     typedef vertex_vector<>::vertex_store<my_vertex>::type VV;
     typedef vertex_list<>::vertex_store<my_vertex>::type VL;
     typedef vertex_set<>::vertex_store<my_vertex>::type VS;
-    // typedef vertex_map<>::vertex_map<string, my_vertex>::type VM;
+    typedef vertex_map<string>::vertex_store<my_vertex>::type VM;
 
-    test<VV>();
+    // test<VV>();
     test<VL>();
     test<VS>();
+    test<VM>();
 }