Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2008-06-24 11:38:33


Author: asutton
Date: 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
New Revision: 46648
URL: http://svn.boost.org/trac/boost/changeset/46648

Log:
Implemented the edge() query for undirected graphs. It's probably not going
to work for directed graphs with vectors - I don't know if the functions are
there.

Text files modified:
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp | 11 +++++++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp | 9 +++++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 11 +++++++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 11 +++++++
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 57 +++++++++++++++++++++++++++++++++------
   sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 4 ++
   6 files changed, 93 insertions(+), 10 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -57,6 +57,17 @@
     inline iterator find(incidence_pair p) const
     { return std::find(_edges.begin(), _edges.end(), p); }
 
+ /** Find the edge with the given vertex. */
+ inline iterator find(vertex_descriptor v) const
+ {
+ // TODO How do I write this with std::find?
+ iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
     /**
      * Remove the given incidence pair in this vertex.
      * @complexity O(deg(v))

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -58,7 +58,14 @@
      * @complexity O(lg(deg(v)))
      */
     inline iterator find(incidence_pair p) const
- { return _edges.find(p.first); }
+ { return find(p.first); }
+
+ /**
+ * Find the incidence pair.
+ * @complexity O(lg(deg(v)))
+ */
+ inline iterator find(vertex_descriptor v) const
+ { return _edges.find(v); }
 
     /**
      * Remove the incidence pair from the set.

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -43,6 +43,17 @@
     void add(incidence_pair p)
     { _edges.push_back(p); }
 
+ /** Find the edge with the given vertex. */
+ inline iterator find(vertex_descriptor v) const
+ {
+ // TODO How do I write this with std::find?
+ iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->first == v) return i;
+ }
+ return end;
+ }
+
     inline size_type size() const
     { return _edges.size(); }
 

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -50,6 +50,17 @@
         return boost::prior(_edges.end());
     }
 
+ /** Find the edge with the given vertex. */
+ iterator find(vertex_descriptor v) const
+ {
+ // TODO How do I write this with std::find?
+ iterator i = _edges.begin(), end = _edges.end();
+ for( ; i != end; ++i) {
+ if(i->template get<0>() == v) return i;
+ }
+ return end;
+ }
+
     /** Get the number of outgoing edges. */
     inline size_type size() const
     { return _edges.size(); }

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-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -156,6 +156,16 @@
     edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
     //@}
 
+ /** @name Test Edge
+ * Determine if the edge, given by two vertices exists. This function a few
+ * convenience overloads that depend on the type of vertex store.
+ */
+ //@{
+ std::pair<edge_descriptor, bool> edge(vertex_descriptor, vertex_descriptor) const;
+ std::pair<edge_descriptor, bool> edge(vertex_properties const&, vertex_properties const&) const;
+ std::pair<edge_descriptor, bool> edge(vertex_key const&, vertex_key const&) const;
+ //@}
+
     /** @name Remove Edge(s)
      * Remove one or more edges from the graph. The function taking a single
      * edge descriptor removes exactly that edge. The fucntion(s) taking
@@ -434,23 +444,52 @@
 }
 
 /**
- * Add an edge to the graph that connects the two vertices identified by the
- * given keys and has the given edge properties.
+ * Determine if any edge exists connecting the vertices u and v. Return a
+ * pair containing the edge descriptor (if it exists) and a bool determing
+ * whether or not the edge did exist.
  */
 template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v,
- edge_properties const& ep)
+std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+undirected_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
 {
- return add_edge(find_vertex(u), find_vertex(v), ep);
+ vertex_type& src = _verts.vertex(u);
+ typename vertex_type::iterator i = src.find(v);
+ return i == src.end() ?
+ std::make_pair(edge_descriptor(u, v, i->second), true) :
+ std::make_pair(edge_descriptor(), false);
+}
+
+/**
+ * Determine if any edge exists connecting the vertices identified by the given
+ * properties. Return a pair containing the edge descriptor (if it exists) and
+ * a bool determining whether or not the edge did exist. This is equivalent to
+ * edge(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
+ vertex_properties const& v)
+{
+ return edge(find_vertex(u), find_vertex(v));
+}
+
+/**
+ * Determine if any edge exists connecting the vertices identified by the given
+ * keys. Return a pair containing the edge descriptor (if it exists) and a bool
+ * determining whether or not the edge did exist. This is equivalent to the
+ * expression edge(find_vertex(u), find_vertex(v)).
+ */
+template <BOOST_GRAPH_UG_PARAMS>
+std::pair<typename undirected_graph<VP,EP,VS,ES>::edge_descriptor, bool>
+undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
+ vertex_properties const& v)
+{
+ return edge(find_vertex(u), find_vertex(v));
 }
 
 /**
  * Remove only the given edge from graph. This disconnects both vertices in
  * the edge and removes the property from the graph.
- *
- * @requires HasRemove<edge_store>
  */
 template <BOOST_GRAPH_UG_PARAMS>
 void

Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp 2008-06-24 11:38:32 EDT (Tue, 24 Jun 2008)
@@ -44,6 +44,10 @@
     inline void disconnect(vertex_descriptor, property_descriptor);
     inline iterator disconnect(iterator);
 
+ /** Find return an iterator the edge end with the given vertex. */
+ inline iterator find(vertex_descriptor v) const
+ { return _edges.find(v); }
+
 
     /** @name Property Accessors */
     //@{


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk