[Boost-commit] svn:boost r46331 - in sandbox/SOC/2008/graphs/branches/iu: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-11 12:51:44

Author: asutton
Date: 2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
New Revision: 46331
URL: http://svn.boost.org/trac/boost/changeset/46331

Log:
Took a stab at the initial implementation of disconnect_vertex() and
remove_vertex() - which turn out to be kind of sticky algorithms. Not sure if
the implementation can be specialized for different edge sets yet. Doesn't
seem like it at this point.

Text files modified: 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp             |    32 ++++++++++---                           
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp   |     2                                         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp    |     2                                         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp |     2                                         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp    |     6 ++                                      
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp |    93 ++++++++++++++++++++++++++++++++++----- 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp           |    19 ++-----                                 
   sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp                |    31 +++++++++---                            
   8 files changed, 138 insertions(+), 49 deletions(-)

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/edge.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -21,9 +21,24 @@
     inline undirected_edge();
     inline undirected_edge(vertex_descriptor u, vertex_descriptor v, property_descriptor p);
 
-    inline edge_pair const& edge() const;
-    inline property_descriptor property() const;
+    inline property_descriptor properties() const
+    { return _prop; }
 
+    inline edge_pair const& edge() const
+    { return _edge; }
+
+    inline vertex_descriptor first() const
+    { return _edge.first(); }
+
+    inline vertex_descriptor second() const
+    { return _edge.second(); }
+
+    inline vertex_descriptor opposite(vertex_descriptor v)
+    { return v == first() ? second() : first(); }
+
+
+    inline bool operator==(undirected_edge const& x);
+    inline bool operator!=(undirected_edge const& x);
     inline bool operator<(undirected_edge const& x);
 
 private:
@@ -46,17 +61,17 @@
 { }
 
 template <typename VD, typename PD>
-typename undirected_edge<VD,PD>::edge_pair const&
-undirected_edge<VD,PD>::edge() const
+bool
+undirected_edge<VD,PD>::operator==(undirected_edge const& x)
 {
-    return _edge;
+    return _edge == x._edge && _prop == x._prop;
 }
 
 template <typename VD, typename PD>
-typename undirected_edge<VD,PD>::property_descriptor
-undirected_edge<VD,PD>::property() const
+bool
+undirected_edge<VD,PD>::operator!=(undirected_edge const& x)
 {
-    return _prop;
+    return !(*this->operator==(x));
 }
 
 template <typename VD, typename PD>
@@ -66,4 +81,5 @@
     return _edge < x._edge || (!(x._edge < _edge) && _prop < x._prop);
 }
 
+
 #endif

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -26,8 +26,6 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef none incidence_iterator;
-
     // Constructors
     incidence_list();
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -30,8 +30,6 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef none incidence_iterator;
-
     // Constructors
     incidence_set();
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_vector.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -26,8 +26,6 @@
     typedef typename store_type::const_iterator const_iterator;
     typedef typename store_type::size_type size_type;
 
-    typedef none incidence_iterator;
-
     // Constructors
     incidence_vector();
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/property_list.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -32,7 +32,11 @@
     // Property access.
     inline property_type& properties(property_descriptor);
 
-public:
+    // Don't ever call this function.
+    inline typename store_type::size_type size() const
+    { return _props.size(); }
+
+private:
     store_type _props;
 };
 

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -59,13 +59,17 @@
     // Generate the incidence list. The incidence list for a single vertex
     // contains a pair: the opposite edge and a property descriptor.
     typedef typename EdgeStore::template incidence_store<vertex_descriptor, property_descriptor>::type incidence_store;
-    typedef typename incidence_store::size_type incident_edges_size_type;
-    typedef typename incidence_store::incidence_iterator incident_edge_iterator;
 
     // Generate the vertex type over the given properties and the incidence
     // store. Then, turn around and use that to generate the vertex store and its
     // related types.
     typedef vertex<vertex_properties, incidence_store> vertex_type;
+    typedef typename vertex_type::size_type incident_edges_size_type;
+
+    // Incident edge iterators are abstracted over the iterators of the vertex.
+    typedef incidence_iterator<typename vertex_type::iterator> incident_edge_iterator;
+    typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
+
     typedef typename VertexStore::template store<vertex_type>::type vertex_store;
     typedef typename vertex_store::size_type vertices_size_type;
     typedef typename vertex_store::vertex_iterator vertex_iterator;
@@ -83,7 +87,8 @@
     vertex_descriptor add_vertex(vertex_properties const&);
     vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
 
-    // Remove vertices
+    // Disconnect and Remove vertices
+    void disconnect_vertex(vertex_descriptor);
     void remove_vertex(vertex_descriptor);
 
     // Add edges
@@ -98,8 +103,13 @@
     vertex_iterator end_vertices() const;
     vertices_size_type num_vertices() const;
 
+    // Edge incidence
+    incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
+    incident_edge_iterator end_incident_edges(vertex_descriptor) const;
+    incident_edge_range incident_edges(vertex_descriptor) const;
     incident_edges_size_type degree(vertex_descriptor) const;
 
+    // Property accesors
     vertex_properties& operator[](vertex_descriptor);
     edge_properties& operator[](edge_descriptor);
 
@@ -134,6 +144,32 @@
 }
 
 /**
+ * Disconnect the vertex from the graph. This removes all edges incident to
+ * the vertex, but will not remove the vertex itself.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+void
+undirected_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_descriptor v)
+{
+    // Disconnecting a vertex is not quite so simple as clearing the incidence
+    // set since we have to remove all the edge properties and remove the
+    // opposite edges from other vertices.
+    // TODO: Can we specialize this at all?
+
+    // Start by disconnecting all of the incident edges from adjacent vertices.
+    incident_edge_range rng = incident_edges(v);
+    for( ; rng.first != rng.second; ++rng.first) {
+        edge_descriptor e = *rng.first;
+        vertex_type& opp = _verts.vertex(e.opposite(v));
+        opp.disconnect(v, e.properties());
+
+        // Remove all the properties too. Does this make sense here?
+        _props.remove(e.properties());
+
+    }
+}
+
+/**
  * Remove the vertex from the graph. This will disconnect the vertex from the
  * graph prior to remove.
  */
@@ -141,6 +177,7 @@
 void
 undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
 {
+    disconnect_vertex(v);
     _verts.remove(v);
 }
 
@@ -181,19 +218,17 @@
         // edge. Otherwise, we can simply return an edge over the existing
         // iterator.
         if(ins.first == src.end()) {
-            property_descriptor p = _props.add();
+            property_descriptor p = _props.add(ep);
             src.connect(v, p);
             tgt.connect(u, p);
-            std::cout << "added new edge" << std::endl;
             return edge_descriptor(u, v, p);
         }
         else {
-            std::cout << "reusing old edge" << std::endl;
             return edge_descriptor(u, v, ins.first->second);
         }
     }
     else {
-        std::cout << "can't add?" << std::endl;
+        // Can't add the edge?
     }
 
     // This is a null iterator
@@ -210,10 +245,12 @@
 void
 undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
 {
-    // Cache some useful info for the erasure.
-    property_descriptor p = e.property();
-    vertex_descriptor u = e.edge().first();
-    vertex_descriptor v = e.edge().second();
+    // Grab descriptors out of the edge.
+    property_descriptor p = e.properties();
+    vertex_descriptor u = e.first();
+    vertex_descriptor v = e.second();
+
+    // And translate to real data structres.
     vertex_type& src = _verts.vertex(u);
     vertex_type& tgt = _verts.vertex(v);
 
@@ -221,6 +258,8 @@
     // the global property store.
     src.disconnect(v, p);
     tgt.disconnect(u, p);
+
+    std::cout << "removing properties: " << _props.properties(p) << std::endl;
     _props.remove(p);
 }
 
@@ -292,6 +331,36 @@
 }
 
 /**
+ * Return an iterator to the first incident edge of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
+undirected_graph<VP,EP,VS,ES>::begin_incident_edges(vertex_descriptor v) const
+{
+    return incident_edge_iterator(v, _verts.vertex(v).begin());
+}
+
+/**
+ * Return an iterator past the end of the incident edges of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
+undirected_graph<VP,EP,VS,ES>::end_incident_edges(vertex_descriptor v) const
+{
+    return incident_edge_iterator(v, _verts.vertex(v).end());
+}
+
+/**
+ * Return an iterator range over the incident edges of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::incident_edge_range
+undirected_graph<VP,EP,VS,ES>::incident_edges(vertex_descriptor v) const
+{
+    return make_pair(begin_incident_edges(v), end_incident_edges(v));
+}
+
+/**
  * Return the degree (number of incdent edges) of the given vertex.
  */
 template <BOOST_GRAPH_UG_PARAMS>
@@ -318,7 +387,7 @@
 typename undirected_graph<VP,EP,VS,ES>::edge_properties&
 undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
 {
-    return _props.properties(e.prop);
+    return _props.properties(e.properties());
 }
 
 #undef BOOST_GRAPH_UG_PARAMS

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -2,6 +2,8 @@
 #ifndef VERTEX_HPP
 #define VERTEX_HPP
 
+#include "incidence_iterator.hpp"
+
 // A vertex, at least for an undirected graph, is simply an repository
 // for the vertex' properties and an interface for the its incidence
 // list.
@@ -20,7 +22,7 @@
     typedef typename incidence_store::property_descriptor property_descriptor;
 
     typedef typename incidence_store::const_iterator iterator;
-    typedef typename incidence_store::size_type incidence_size_type;
+    typedef typename incidence_store::size_type size_type;
 
     inline vertex();
     inline vertex(vertex_properties const& vp);
@@ -30,8 +32,6 @@
     inline void disconnect(vertex_descriptor, property_descriptor);
     template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
 
-    inline incidence_size_type degree() const;
-
     inline vertex_properties& properties();
     inline vertex_properties const& properties() const;
 
@@ -42,6 +42,9 @@
     inline iterator end() const
     { return _edges.end(); }
 
+    inline size_type degree() const
+    { return _edges.size(); }
+
     inline bool operator<(vertex const&) const;
 
 private:
@@ -105,16 +108,6 @@
 }
 
 /**
- * Return the degree (number of incident edges) of this vertex.
- */
-template <typename VP, typename IS>
-typename vertex<VP,IS>::incidence_size_type
-vertex<VP,IS>::degree() const
-{
-    return _edges.size();
-}
-
-/**
  * Return the properties associated with this vertex (if any).
  */
 template <typename VP, typename IS>

Modified: sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/libs/graphs/un.cpp	2008-06-11 12:51:43 EDT (Wed, 11 Jun 2008)
@@ -11,7 +11,7 @@
 using namespace boost;
 
 typedef int City;
-struct Road { };
+typedef int Road;
 
 void list_list();
 void vec_vec();
@@ -90,6 +90,19 @@
 }
 
 template <typename Graph>
+void test_remove_vert(Graph& g)
+{
+    cout << "*** Remove Vertex" << endl;
+    cout << "*** " << demangle(typeid(Graph).name()) << endl;
+    typename Graph::vertex_descriptor u = g.add_vertex(300);
+    typename Graph::vertex_descriptor v = g.add_vertex(301);
+    typename Graph::vertex_descriptor w = g.add_vertex(302);
+    g.add_edge(u, v, 1);
+    g.add_edge(v, w, 2);
+    g.remove_vertex(v);
+}
+
+template <typename Graph>
 void print_verts(Graph& g)
 {
     typename Graph::vertex_range rng = g.vertices();
@@ -101,12 +114,11 @@
 
 int main()
 {
-    vec_vec();
-    cout << endl << endl;
+    // vec_vec();
+    // cout << endl << endl;
     list_list();
-    cout << endl << endl;
-    set_set();
-    cout << endl << endl;
+    // cout << endl << endl;
+    // set_set();
 
     return 0;
 }
@@ -125,9 +137,10 @@
     typedef undirected_graph<City, Road, vertex_list, edge_list> Graph;
 
     Graph g;
-    add_verts(g);
-    add_and_del_edges(g);
-    test_multi_edge(g);
+    // add_verts(g);
+    // add_and_del_edges(g);
+    // test_multi_edge(g);
+    test_remove_vert(g);
 }