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

Subject: [Boost-commit] svn:boost r50160 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs/adjacency_list test test/gen
From: asutton_at_[hidden]
Date: 2008-12-06 09:31:36

Author: asutton
Date: 2008-12-06 09:31:35 EST (Sat, 06 Dec 2008)
New Revision: 50160
URL: http://svn.boost.org/trac/boost/changeset/50160

Log:
Implementing (kind of badly) remove_edges(g,v)
Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/gen/
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/gen/star.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/traits.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp  |    39 +++++++++++++++++++++----------         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp |    38 ++++++++++++++++++++++++++++---         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp                                      |    48 ++++++++------------------------------- 
   3 files changed, 70 insertions(+), 55 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_store.hpp	2008-12-06 09:31:35 EST (Sat, 06 Dec 2008)
@@ -63,7 +63,7 @@
     { return store.find(v); }
 
     // A default visitor for the erase_all function.
-    struct noop_erase_visitor
+    struct no_edge_erase
     {
         template <typename Pair> inline void operator()(Pair const&) { }
     };
@@ -145,7 +145,22 @@
 { return find(const_cast<Store&>(store), v); }
 //@}
 
-/** Remove the adjacenct/incident pair from the store. */
+// NOTE Reciprocating and Cascading Erasures
+//
+// Reciprocal erasure is the problem where removing an AI pair from one
+// vertex requires its reciprocal erasure from the incidence store of the
+// adjacent vertex.
+//
+// Cascading erasure is the problem where removing an AI pair from one
+// vertex should also require the erasure from the edge set.
+//
+// Note that reciprocating erasure can be fairly inefficient when erasing
+// multi-edges because it will result in multiple iterations of the adjacent
+// vertex's incidence store,
+
+/**
+ * Remove the adjacenct/incident pair from the store.
+ */
 template <typename Store>
 inline void
 erase(Store& store,
@@ -157,10 +172,10 @@
 }
 
 /**
- * Remove all incident edges with the given endpoint. A visitor parameter can
- * be provided to be invoked just prior to erasure.
+ * Remove all incident edges with the given endpoint. This operation supports
+ * cascading erases via a function object. By default, this is disabled.
  */
-template <typename Store, typename Visitor = detail::noop_erase_visitor>
+template <typename Store, typename Visitor = detail::no_edge_erase>
 inline void
 erase_all(Store& store,
           typename incidence_store_traits<Store>::vertex_descriptor v,
@@ -168,20 +183,18 @@
 { detail::dispatch_erase_all(store, v, vis, container_category(store)); }
 
 /**
- * Remove all incident edges from the edge set, invoking a visitor just prior
- * to erasing the edge.
+ * Remove all incident edges from the edge set. This operation supports
+ * reciprocation and cascading erases via function object. By default, this is
+ * disabled.
  */
-template <typename Store, typename Visitor = detail::noop_erase_visitor>
+template <typename Store, typename Visitor = detail::no_edge_erase>
 inline void
 clear(Store& store, Visitor vis = Visitor())
 {
-    typename Store::iterator i, end = store.end();
-    for(i = store.begin() ; i != end; ++i) {
-        vis(*i);
-    }
+    std::for_each(store.begin(), store.end(), vis);
+    store.clear();
 }
 
-
 /** Return the size of an adjacency list for the given vertex, its degree. */
 template <typename Store>
 inline typename incidence_store_traits<Store>::incident_edges_size_type

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-12-06 09:31:35 EST (Sat, 06 Dec 2008)
@@ -245,7 +245,6 @@
 namespace detail {
     // This functor automatically erases edges from the edge set when visited
     // during incident edge erasure.
-    // TODO: Make this fail for vectors.
     template <typename EdgeList>
     struct edge_eraser
     {
@@ -276,14 +275,45 @@
     incs::erase_all(vs::edges(g.v, v), u);
 }
 
+namespace detail {
+    // Reciprocating and cascading erasure for remove_edges(g,v).
+    // TODO: This is not an efficient solution for multigraphs with sequential
+    // incidence stores. For associative incidence stores, this is probably
+    // fine.
+    template <typename Graph, typename Vertex>
+    struct edge_clearer
+    {
+        edge_clearer(Graph& g, Vertex v)
+            : g(g), v(v)
+        { }
+
+        template <typename Pair>
+        void operator()(Pair const& x)
+        {
+            // Don't erase self-loops. That would modify the sequence that
+            // this functor is visiting - which could have some pretty nasty
+            // side-effects.
+            if(v != x.first) {
+                incs::erase(vs::edges(g.v, x.first), v, x.second);
+            }
+            es::erase(g.e, x.second);
+        }
+
+        Graph& g;
+        Vertex v;
+    };
+
+    template <typename Graph, typename Vertex>
+    edge_clearer<Graph, Vertex> clear_edges(Graph& g, Vertex v)
+    { return edge_clearer<Graph, Vertex>(g, v); }
+}
+
 /** Remove all edges incident to the given vertex. */
 template <typename VL, typename EL, typename VS, typename ES, typename IS>
 inline void
 remove_edges(undirected_graph<VL,EL,VS,ES,IS>& g,
              typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v)
-{
-    incs::clear(vs::edges(g.v, v));
-}
+{ incs::clear(vs::edges(g.v, v), detail::clear_edges(g, v)); }
 
 /** Return the number of edges in the graph. */
 template <typename VL, typename EL, typename VS, typename ES, typename IS>

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/gen/star.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/gen/star.hpp	2008-12-06 09:31:35 EST (Sat, 06 Dec 2008)
@@ -0,0 +1,25 @@
+
+#ifndef GEN_STAR_HPP
+#define GEN_STAR_HPP
+
+#include <vector>
+
+#include "../traits.hpp"
+
+// Generate an (n-1)-spoked star. Vertex 0 is the center. This assumes that
+//
+template <typename Graph>
+typename Graph::vertex_descriptor
+make_star(Graph& g, int n)
+{
+    std::vector<typename Graph::vertex_descriptor> v(n);
+    for(int i = 0; i < n; ++i) {
+        v[i] = detail::make_vertex(g, i);
+    }
+    for(int i = 1; i < n; ++i) {
+        add_edge(g, v[0], v[i], i - 1);
+    }
+    return v[0];
+}
+
+#endif

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/traits.hpp	2008-12-06 09:31:35 EST (Sat, 06 Dec 2008)
@@ -0,0 +1,76 @@
+
+#ifndef TRAITS_HPP
+#define TRAITS_HPP
+
+#include <boost/mpl/bool.hpp>
+
+// Forward declare our common label types.
+class node;
+class arc;
+
+/** @name Has Mapped Vertices */
+//@{
+template <typename Graph>
+struct _has_mapped_vertices
+{ typedef boost::mpl::false_ type; };
+
+template <
+    typename VL, typename EL,
+    typename K, template <typename> class C, template <typename> class A,
+    typename ES, typename IS>
+struct _has_mapped_vertices<
+    boost::graphs::adjacency_list::undirected_graph<
+        VL, EL, boost::graphs::adjacency_list::vertex_map<K,C,A>, ES, IS
+    >
+>
+{ typedef boost::mpl::true_ type; };
+
+template <typename Graph>
+typename _has_mapped_vertices<Graph>::type
+has_mapped_vertices(Graph const& g)
+{ return typename _has_mapped_vertices<Graph>::type(); }
+//@}
+
+/** @name Can Remove Vertices */
+//@{
+template <typename Graph>
+struct _can_remove_vertices
+{ typedef boost::mpl::true_ type; };
+
+template <
+    typename VL, typename EL,
+    template <typename> class A,
+    typename ES, typename IS>
+struct _can_remove_vertices<
+    boost::graphs::adjacency_list::undirected_graph<
+        VL, EL, boost::graphs::adjacency_list::vertex_vector<A>, ES, IS
+    >
+>
+{ typedef boost::mpl::false_ type; };
+
+template <typename Graph>
+typename _can_remove_vertices<Graph>::type
+can_remove_vertices(Graph const& g)
+{ return typename _can_remove_vertices<Graph>::type(); }
+//@}
+
+
+// Helper functions
+namespace detail {
+    template <typename Graph>
+    typename Graph::vertex_descriptor
+    do_make_vertex(Graph& g, int i, boost::mpl::false_)
+    { return add_vertex(g, node(i)); }
+
+    template <typename Graph>
+    typename Graph::vertex_descriptor
+    do_make_vertex(Graph& g, int i, boost::mpl::true_)
+    { return add_vertex(g, i, node(i)); }
+
+    template <typename Graph>
+    typename Graph::vertex_descriptor
+    make_vertex(Graph& g, int i)
+    { return do_make_vertex(g, i, has_mapped_vertices(g)); }
+}
+
+#endif

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-12-06 09:31:35 EST (Sat, 06 Dec 2008)
@@ -4,51 +4,15 @@
 #include <iostream>
 
 #include <boost/assert.hpp>
-#include <boost/mpl/bool.hpp>
 #include <boost/graphs/adjacency_list/undirected_graph.hpp>
 
+#include "traits.hpp"
+#include "gen/star.hpp"
 
 using namespace std;
 using namespace boost;
 using namespace boost::graphs::adjacency_list;
 
-/** @name Has Mapped Vertices */
-//@{
-template <typename Graph>
-struct _has_mapped_vertices
-{ typedef mpl::false_ type; };
-
-template <
-    typename VL, typename EL,
-    typename K, template <typename> class C, template <typename> class A,
-    typename ES, typename IS>
-struct _has_mapped_vertices<undirected_graph<VL, EL, vertex_map<K,C,A>, ES, IS>>
-{ typedef mpl::true_ type; };
-
-template <typename Graph>
-typename _has_mapped_vertices<Graph>::type
-has_mapped_vertices(Graph const& g)
-{ return typename _has_mapped_vertices<Graph>::type(); }
-//@}
-
-/** @name Can Remove Vertices */
-//@{
-template <typename Graph>
-struct _can_remove_vertices
-{ typedef mpl::true_ type; };
-
-template <
-    typename VL, typename EL,
-    template <typename> class A,
-    typename ES, typename IS>
-struct _can_remove_vertices<undirected_graph<VL, EL, vertex_vector<A>, ES, IS>>
-{ typedef mpl::false_ type; };
-
-template <typename Graph>
-typename _can_remove_vertices<Graph>::type
-can_remove_vertices(Graph const& g)
-{ return typename _can_remove_vertices<Graph>::type(); }
-//@}
 
 struct node
 {
@@ -169,11 +133,19 @@
 template <typename Graph>
 void test()
 {
+    typedef typename Graph::vertex_descriptor Vertex;
     Graph g;
     BOOST_ASSERT(num_vertices(g) == 0);
 
     test_verts(g, has_mapped_vertices(g));
     test_edges(g);
+
+    Graph h;
+    Vertex v = make_star(h, 5);
+    BOOST_ASSERT(num_vertices(h) == 5);
+    BOOST_ASSERT(num_edges(h) == 4);
+    remove_edges(h, v);
+    BOOST_ASSERT(num_edges(h) == 0);
 }
 
 int main()