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 */
//@{