[Boost-commit] svn:boost r46769 - in sandbox/SOC/2008/graphs/trunk: boost/graphs libs/graphs

From: asutton_at_[hidden]
Date: 2008-06-27 08:57:14

Author: asutton
Date: 2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
New Revision: 46769
URL: http://svn.boost.org/trac/boost/changeset/46769

Log:
Fixed valgrind errors (invalid memory access).

Text files modified: 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp         |     2 --                                      
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp     |     5 +++--                                   
   sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp    |     1 +                                       
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp |    23 +++++++++++++++++++----                 
   sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp    |     3 ++-                                     
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp   |    32 ++++++++++++--------------------        
   sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp  |    30 +-----------------------------          
   sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp                  |    19 +++++++++++++------                     
   8 files changed, 51 insertions(+), 64 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -38,8 +38,6 @@
 // Comparisons are also based on this unique identifier. Comparing two 
 // descriptors is not the same as comparing the objects that they describe.
 
-// TODO: What's the validity of a descriptor? One that isn't iniitialized?
-
 // Include implementations and their specializations.
 #include "descriptor/common.hpp"
 #include "descriptor/vector.hpp"

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -507,11 +507,12 @@
 directed_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
 {
     // Removing the edge involves the removal of both parts from the two
-    // connected vertices.
+    // connected vertices. We have to disconnect the source first because that
+    // will /not/ erase the edge's iterator.
     vertex_type& src = _verts.vertex(e.source());
     vertex_type& tgt = _verts.vertex(e.target());
-    src.disconnect_target(e);
     tgt.disconnect_source(e);
+    src.disconnect_target(e);
 }
 
 /**

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -2,6 +2,7 @@
 #ifndef DIRECTED_VERTEX_HPP
 #define DIRECTED_VERTEX_HPP
 
+#include "placeholder.hpp"
 #include "directed_edge.hpp"
 
 /**

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -53,7 +53,7 @@
      * iterator. This is the vertex for which the iterator was originally
      * created.
      */
-    vertex_descriptor source() const
+    inline vertex_descriptor source() const
     { return _base; }
 
     /**
@@ -61,22 +61,37 @@
      * edge indicated by the iterator. This is mostly provided for use by
      * the adjacency iterator.
      */
-    vertex_descriptor opposite() const
+    inline vertex_descriptor opposite() const
     { return _iter->first; }
 
+    /**
+     * Return true if the iterator is "valid" (not default constructed). The
+     * shortcut is to simply test the vertex descriptor.
+     */
+    inline bool valid() const
+    { return _base != vertex_descriptor(); }
+
     inline incidence_iterator& operator++()
     { ++_iter; return *this; }
 
+    inline incidence_iterator operator++(int)
+    { incidence_iterator tmp(*this); ++_iter; return tmp; }
+
     inline incidence_iterator& operator--()
     { --_iter; return *this; }
 
-    // Iterators are equivalent if they reference the same edge.
+    inline incidence_iterator operator--(int)
+    { incidence_iterator tmp(*this); --_iter; return tmp; }
+
+    // Incidence iterators are equivalent if they have the same source and are
+    // reference the same incident edge.
     inline bool operator==(incidence_iterator const& x) const
-    { return operator*() == *x; }
+    { return (_base == x._base) && (_iter == x._iter); }
 
     inline bool operator!=(incidence_iterator const& x) const
     { return !this->operator==(x); }
 
+    // This can access invalid memory if the iterator is at the end.
     inline reference operator*() const
     { return reference(_base, _iter->first, _iter->second); }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -43,8 +43,9 @@
     property_descriptor add();
     property_descriptor add(edge_properties const&);
 
+    /** Return the properties referenced by the given descriptor. */
     inline edge_properties& properties(property_descriptor d)
-    { return d->first; }
+    { return d.value().first; }
 
     /** Bind descriptors into the incidence lists into the global property. */
     template <typename VertexDesc>

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -3,6 +3,8 @@
 #define UNDIRECTED_GRAPH_HPP
 
 #include "none.hpp"
+#include "descriptor.hpp"
+#include "placeholder.hpp"
 
 #include "undirected_vertex.hpp"
 #include "vertex_vector.hpp"
@@ -33,8 +35,10 @@
 
     // Generate the property store type first. We can do this first because
     // it's basically independant of everything else, but contributes to almost
-    // everything in the class by virtue of the property descriptor.
+    // everything in the class by virtue of the property descriptor. Use this
+    // to generate the property descriptor...
     typedef typename EdgeStore::template property_store<edge_properties>::type property_store;
+    typedef typename property_store::property_descriptor property_descriptor;
     typedef typename property_store::size_type edges_size_type;
 
     // Generate a bunch of descriptors. The vertex descriptor is fairly
@@ -42,7 +46,6 @@
     // everything. The property descriptor depends entirely upon the property
     // store and the edge descriptor is actually fairly complicated.
     typedef typename VertexStore::descriptor_type vertex_descriptor;
-    typedef typename property_store::property_descriptor property_descriptor;
     typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
 
     // Generate the incidence list. The incidence list for a single vertex
@@ -69,6 +72,7 @@
     typedef typename vertex_store::size_type vertices_size_type;
     typedef typename vertex_store::vertex_iterator vertex_iterator;
     typedef typename vertex_store::vertex_range vertex_range;
+
     // FIXME: This is a bit hacky, but without constrained members, we need a key
     // type to enable mapped vertices.
     typedef typename VertexStore::key_type vertex_key;
@@ -683,35 +687,23 @@
     return _props.size();
 }
 
-/**
- * Return an iterator to the first incident edge of the given vertex.
- */
+/** 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 incident_edge_iterator(v, _verts.vertex(v).begin()); }
 
-/**
- * Return an iterator past the end of the incident edges of the given vertex.
- */
+/** 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 incident_edge_iterator(v, _verts.vertex(v).end()); }
 
-/**
- * Return an iterator range over the incident edges of the given vertex.
- */
+/** 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 make_pair(begin_incident_edges(v), end_incident_edges(v)); }
 
 /**
  * Return an iterator to the first adjacent vertex of the the given vertex.

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_descriptor.hpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -6,34 +6,6 @@
 
 #include <boost/functional/hash.hpp>
 
-// Important notes about descriptors
-//
-// A descriptor is basically an opaque reference to an object. It's kind of
-// like an iterator that can't be moved or dereferenced. It's kind of like a
-// flyweight, but you can't implicitly cast it as the shared object. In short,
-// you can't use descriptors without their graph. In general, we'd like the
-// descriptor types to be as trivial as possible. One of the most important
-// facts about descriptors is that, by themselves, they have absolutely no
-// semantics. They cannot be used (in general) be used to access the vertices
-// or edges that they represent.
-//
-// The most important thing to understand about descriptors is that they attempt
-// to model the most "consistent" reference into a storage mechanism. By the
-// term "consistent", we mean a means of accessing elements that allow us to
-// actually build a graph without invalidating memory or iterators. For example,
-// we can't use pointers as descriptors into vectors since vectors occasionally
-// reallocate all their memory (oops), but indices work just fine.
-//
-// Descriptors must be completely independent of the actual type of vertices
-// and edges. Two problems arise if we don't do this. First, we end up with
-// weird cyclic type dependencies that can probably be unrolled using some
-// funky lazy template evaluation, but that's generally beyond me. Second,
-// this would
-
-// Build trivial wrappers around the underlying descriptor types. This allows
-// us to differentiate descriptors based on these types rather than their
-// simple descriptor types.
-
 namespace detail
 {
     inline std::size_t invalid_value(std::size_t)
@@ -84,7 +56,7 @@
     { return _d; }
 
     /** Returns true if the descriptor is valid. */
-    inline bool is_valid() const
+    inline bool valid() const
     { return _d != detail::invalid_value(D()); }
 
 private:

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp	2008-06-27 08:57:13 EDT (Fri, 27 Jun 2008)
@@ -186,10 +186,13 @@
     g.add_edge(v, u, 2);
     g.add_edge(u, v, 3);
     g.add_edge(v, u, 4);
+    cout << "done building" << endl;
 
     typename Graph::incident_edge_range x = g.incident_edges(v);
-    for( ; x.first != x.second; ++x.first) {
-        // cout << "test: " << g[*x.first] << endl;
+
+    typename Graph::incident_edge_iterator i = x.first;
+    for(typename Graph::incident_edge_iterator i = x.first; i != x.second; ++i) {
+        cout << *i << endl;
     }
 }
 
@@ -223,15 +226,16 @@
 {
     cout << "---- vec/vec ----" << endl;
     typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
-    test_add_vertices<Graph>();
-    test_add_edges<Graph>();
-    test_add_multi_edges<Graph>();
+    // test_add_vertices<Graph>();
+    // test_add_edges<Graph>();
+    // test_add_multi_edges<Graph>();
     test_incidence_iterator<Graph>();
-    test_adjacency_iterator<Graph>();
+    // test_adjacency_iterator<Graph>();
 }
 
 void list_list()
 {
+    /*
     cout << "---- list/list ----" << endl;
     typedef undirected_graph<City, Road, vertex_list<>, edge_list<> > Graph;
     test_add_remove_vertices<Graph>();
@@ -242,11 +246,13 @@
     test_remove_multi_edges<Graph>();
     test_incidence_iterator<Graph>();
     test_adjacency_iterator<Graph>();
+    */
 }
 
 
 void set_set()
 {
+    /*
     cout << "---- set/set ----" << endl;
     typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
     test_add_remove_vertices<Graph>();
@@ -257,5 +263,6 @@
     test_remove_multi_edges<Graph>();
     test_incidence_iterator<Graph>();
     test_adjacency_iterator<Graph>();
+    */
 }