[Boost-commit] svn:boost r46426 - sandbox/SOC/2008/graphs/branches/iu/boost/graphs

From: asutton_at_[hidden]
Date: 2008-06-16 11:01:58

Author: asutton
Date: 2008-06-16 11:01:57 EDT (Mon, 16 Jun 2008)
New Revision: 46426
URL: http://svn.boost.org/trac/boost/changeset/46426

Log:
Implemented an adjacency iterator for undirected graphs.

Added:
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/adjacency_iterator.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/policy.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/traits.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_iterator.hpp |    27 ++++++++++--                            
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_list.hpp     |    32 ++++++++++-----                         
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_set.hpp      |    16 +++++-                                  
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/undirected_graph.hpp   |    82 ++++++++++++++++++++++++++++++++------- 
   sandbox/SOC/2008/graphs/branches/iu/boost/graphs/vertex.hpp             |    17 ++++++++                                
   5 files changed, 139 insertions(+), 35 deletions(-)

Added: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/adjacency_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/adjacency_iterator.hpp	2008-06-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -0,0 +1,81 @@
+
+#ifndef ADJACENCY_ITERATOR_HPP
+#define ADJACENCY_ITERATOR_HPP
+
+#include <iterator>
+
+/**
+ * The adjacency iterator is an abstraction over incidence iterators (provided
+ * by the incidence store). The adjacency iterator actually provides the same
+ * functionality as the incidence iterator, but simply provides access to the
+ * other vertices rather than the edges.
+ *
+ * @todo Depending on the underlying incidence iterator provided by the graph,
+ * we could actually possibly make this a random access iterator rather than
+ * just a bidirectional iterator. For now, we force it to be a bidi iterator.
+ */
+template <typename Iterator>
+class adjacency_iterator
+{
+    typedef Iterator iterator;
+    typedef typename Iterator::vertex_descriptor vertex_descriptor;
+public:
+
+    typedef std::bidirectional_iterator_tag iterator_category;
+    typedef std::size_t difference_type;
+    typedef vertex_descriptor value_type;
+    typedef vertex_descriptor reference;
+    typedef vertex_descriptor pointer;
+
+    // Constructors
+    inline adjacency_iterator()
+        : _iter()
+    { }
+
+    inline adjacency_iterator(Iterator iter)
+        : _iter(iter)
+    { }
+
+    inline adjacency_iterator& operator=(adjacency_iterator const& x)
+    {
+        _iter = x._iter;
+        return *this;
+    }
+
+    inline adjacency_iterator& operator++()
+    {
+        ++_iter;
+        return *this;
+    }
+
+    inline adjacency_iterator& operator--()
+    {
+        --_iter;
+        return *this;
+    }
+
+    inline bool operator==(adjacency_iterator const& x) const
+    {
+        return _iter == x._iter;
+    }
+
+    inline bool operator!=(adjacency_iterator const& x) const
+    {
+        return _iter != x._iter;
+    }
+
+    reference operator*() const
+    {
+        // Return the opposite vertex referenced by the underlying iterator.
+        // This lets us get away without having to store the source vertex
+        // multiple types in the layered iterator.
+        return _iter.opposite();
+    }
+
+private:
+    iterator _iter;
+};
+
+
+#endif
+

Modified: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_iterator.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/incidence_iterator.hpp	2008-06-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -16,9 +16,10 @@
 {
     typedef Iter base_iterator;
     typedef typename base_iterator::value_type base_value_type;
+public:
     typedef typename base_value_type::first_type vertex_descriptor;
     typedef typename base_value_type::second_type property_descriptor;
-public:
+
     // This is a little misleading. This iterator can be either bidi or random.
     // Clearly, we're going to be constraining members using some concept stuff
     // when it becomes available.
@@ -47,6 +48,22 @@
         : _base(v), _iter(x)
     { }
 
+    /**
+     * Extended iterator functionality. Return the source vertex of the
+     * iterator. This is the vertex for which the iterator was originally
+     * created.
+     */
+    vertex_descriptor source() const
+    { return _base; }
+
+    /**
+     * Extended iterator functionality. Return the opposite vertex of the
+     * edge indicated by the iterator. This is mostly provided for use by
+     * the adjacency iterator.
+     */
+    vertex_descriptor opposite() const
+    { return _iter->first; }
+
     inline incidence_iterator& operator++()
     { ++_iter; return *this; }
 
@@ -54,18 +71,18 @@
     { --_iter; return *this; }
 
     // Iterators are equivalent if they reference the same edge.
-    inline bool operator==(incidence_iterator const& x)
+    inline bool operator==(incidence_iterator const& x) const
     { return **this == *x; }
 
-    inline bool operator!=(incidence_iterator const& x)
+    inline bool operator!=(incidence_iterator const& x) const
     { return !this->operator==(x); }
 
     inline reference operator*() const
     { return reference(_base, _iter->first, _iter->second); }
 
 private:
-    vertex_descriptor _base;
-    base_iterator _iter;
+    vertex_descriptor   _base;
+    base_iterator       _iter;
 };
 
 

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-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -35,12 +35,10 @@
     inline iterator find(incidence_pair);
     inline const_iterator find(incidence_pair) const;
 
+    inline void clear();
     inline void remove(incidence_pair);
     template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
 
-    inline void clear();
-
-
     inline size_type size() const
     { return _edges.size(); }
 
@@ -63,6 +61,20 @@
 { }
 
 /**
+ * Incidence lists always allow the addition of edges, assuming that no policy
+ * conflicts exist. The first element of the return is the end() of the list.
+ *
+ * @complexity O(1)
+ */
+template <BOOST_GRAPH_IL_PARAMS>
+std::pair<typename incidence_list<E,A>::const_iterator, bool>
+incidence_list<E,A>::allow(vertex_descriptor v) const
+{
+    // Since there's no policy, there we must be able to add the edge.
+    return make_pair(_edges.end(), true);
+}
+
+/**
  * Add the incident edge to the incidence set.
  *
  * @complexity O(1)
@@ -75,17 +87,15 @@
 }
 
 /**
- * Incidence lists always allow the addition of edges, assuming that no policy
- * conflicts exist. The first element of the return is the end() of the list.
+ * Remove all incident edges from this set.
  *
- * @complexity O(1)
+ * @complexity  O(d)
  */
-template <BOOST_GRAPH_IL_PARAMS>
-std::pair<typename incidence_list<E,A>::const_iterator, bool>
-incidence_list<E,A>::allow(vertex_descriptor v) const
+template <typename E, typename A>
+void
+incidence_list<E,A>::clear()
 {
-    // Since there's no policy, there we must be able to add the edge.
-    return make_pair(_edges.end(), true);
+    _edges.clear();
 }
 
 /**

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-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -43,13 +43,11 @@
     inline iterator find(incidence_pair);
     inline const_iterator find(incidence_pair) const;
 
-    // Remove the edge.
+    // Remove edges.
+    inline void clear();
     inline void remove(incidence_pair);
     template <typename Eraser> inline void remove(vertex_descriptor, Eraser);
 
-    // Remove all edges.
-    inline void clear();
-
 
     inline size_type size() const
     { return _edges.size(); }
@@ -105,6 +103,16 @@
 }
 
 /**
+ * Remove all incident edges from this edge set.
+ */
+template <typename E, typename C, typename A>
+void
+incidence_set<E,C,A>::clear()
+{
+    _edges.clear();
+}
+
+/**
  * Remove the incidence pair from the set.
  *
  * @complexity O(lg(d))

Added: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/policy.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/policy.hpp	2008-06-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -0,0 +1,5 @@
+
+#ifndef POLICY_HPP
+#define POLICY_HPP
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/iu/boost/graphs/traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/iu/boost/graphs/traits.hpp	2008-06-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -0,0 +1,34 @@
+
+#ifndef TRAITS_HPP
+#define TRAITS_HPP
+
+namespace detail
+{
+    // This isn't quite so simple as it seems. I think we need to have the
+    // catch-all push the query back to a policy object and that policy needs
+    // to be explicit about whether or not it allows multiple edges.
+    template <typename Store>
+    struct is_simple
+    { enum { value = false }; };
+
+    template <typename E, typename C, typename A>
+    struct is_simple< incidence_set<E,C,A> >
+    { enum { value = true }; };
+
+};
+
+/**
+ * This metafunction determines if the graph allows multiple edges.
+ */
+template <typename Graph>
+struct is_simple
+{ enum { value = detail::is_simple<typename Graph::incidence_store>::value }; };
+
+/**
+ * A helper function for the above.
+ */
+template <typename Graph>
+bool is_simple_graph(const Graph& g)
+{ return is_simple<Graph>::value; }
+
+#endif

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-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -30,6 +30,8 @@
 #include "edge_list.hpp"
 #include "edge_set.hpp"
 
+#include "adjacency_iterator.hpp"
+
 template <
     typename VertexProps,
     typename EdgeProps,
@@ -68,6 +70,9 @@
     typedef incidence_iterator<typename vertex_type::iterator> incident_edge_iterator;
     typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
 
+    typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
+    typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
+
     // The vertex store and related properties can also be built on the vertex
     // type.
     typedef typename VertexStore::template store<vertex_type>::type vertex_store;
@@ -87,53 +92,63 @@
     // Constructors
     undirected_graph();
 
-    // Add vertices
+    /** @name Vertex Set
+     * These functions operate (mostly) on the vertices of the graph. These
+     * functions include the ability to add, disconnect, and remove vertices.
+     */
+    //@{
     vertex_descriptor add_vertex();
     vertex_descriptor add_vertex(vertex_properties const&);
     vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
-
-    // Disconnect and Remove vertices
     void disconnect_vertex(vertex_descriptor);
     void remove_vertex(vertex_descriptor);
+    //@{
 
-    // Add edges
+    /** @name Edge Set
+     * These functions operate on the edges of the graph. This functions
+     * include the ability to add and remove edges.
+     */
+    //@{
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
     edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
-
     void remove_edge(edge_descriptor);
     void remove_edges(vertex_descriptor, vertex_descriptor);
+    //@}
 
     /** @name Vertex Iteration
-     * These functions allow the iteration over the vertex set.
+     * These functions allow iteration over the vertex set.
      */
     //@{
     vertex_range vertices() const;
     vertex_iterator begin_vertices() const;
     vertex_iterator end_vertices() const;
+    vertices_size_type num_vertices() const;
     //@}
 
     /** @name Edge Iteration
-     * These function allow the iteration over the edge set.
+     * These function allow iteration over the edge set.
      */
     //@{
     edge_range edges() const;
     edge_iterator begin_edges() const;
     edge_iterator end_edges() const;
+    edges_size_type num_edges() const;
     //@}
 
-    /** @name Graph Size
-     * These functions return the number of vertices and edges in the graph.
+    /** @name Incident Edge Iteration
+     * These functions allow iteration over the incident edges of a vertex.
      */
     //@{
-    vertices_size_type num_vertices() const;
-    edges_size_type num_edges() 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;
+
+    adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
+    adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
+    adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
+
     incident_edges_size_type degree(vertex_descriptor) const;
+    //@{
 
     // Property accesors
     vertex_properties& operator[](vertex_descriptor);
@@ -192,6 +207,11 @@
         // Remove all the properties too. Does this make sense here?
         _props.remove(e.properties());
     }
+
+    // Clear the incident edge set of the vertex. We don't do this in the
+    // previous loop because we'll probably end up invalidating our own
+    // iterators.
+    _verts.vertex(v).disconnect();
 }
 
 /**
@@ -284,7 +304,6 @@
     src.disconnect(v, p);
     tgt.disconnect(u, p);
 
-    std::cout << "removing properties: " << _props.properties(p) << std::endl;
     _props.remove(p);
 }
 
@@ -393,6 +412,37 @@
 }
 
 /**
+ * Return an iterator to the first adjacent vertex of the the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
+undirected_graph<VP,EP,VS,ES>::begin_adjacent_vertices(vertex_descriptor v) const
+{
+    return begin_incident_edges(v);
+}
+
+/**
+ * Return an iterator past the end of the adjacent vertices of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
+undirected_graph<VP,EP,VS,ES>::end_adjacent_vertices(vertex_descriptor v) const
+{
+    return end_incident_edges(v);
+}
+
+/**
+ * Return an iterator range over the adjacent vertices of the given vertex.
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_range
+undirected_graph<VP,EP,VS,ES>::adjacent_vertices(vertex_descriptor v) const
+{
+    return std::make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v));
+}
+
+
+/**
  * Return the degree (number of incdent edges) of the given vertex.
  */
 template <BOOST_GRAPH_UG_PARAMS>
@@ -424,5 +474,7 @@
 
 #undef BOOST_GRAPH_UG_PARAMS
 
+#include "traits.hpp"
+
 #endif
 

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-16 11:01:57 EDT (Mon, 16 Jun 2008)
@@ -27,8 +27,14 @@
     inline vertex();
     inline vertex(vertex_properties const& vp);
 
+    /** @name Edge Connection and Disconnection
+     * These functions control how edges are added to and removed from the
+     * vertex. The allow() function determines whether or not the edge
+     * connection is allowed and/or already existing.
+     */
     inline std::pair<iterator, bool> allow(vertex_descriptor) const;
     inline void connect(vertex_descriptor, property_descriptor);
+    inline void disconnect();
     inline void disconnect(vertex_descriptor, property_descriptor);
     template <typename Eraser> inline void disconnect(vertex_descriptor, Eraser);
 
@@ -90,6 +96,17 @@
 }
 
 /**
+ * Disconect all edges from this vertex. This does not remove the connection
+ * from adjacent vertices to this vertex.
+ */
+template <typename VP, typename IS>
+void
+vertex<VP,IS>::disconnect()
+{
+    _edges.clear();
+}
+
+/**
  * Disconnect the incidedent edge given by the vertex v with edge properties p.
  */
 template <typename VP, typename IS>