Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2008-05-30 19:49:44


Author: asutton
Date: 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
New Revision: 45966
URL: http://svn.boost.org/trac/boost/changeset/45966

Log:
Finished building out the directed graph, but haven't tested it at all.
Need to finish figuring out all the required interfaces and add/remove
algorithms.

Added:
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/directed.hpp
      - copied, changed from r45965, /sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp
Removed:
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp
Text files modified:
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/directed.hpp | 11 -
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/edge.hpp | 58 +++++-------
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/vertex.hpp | 183 +++++++++++++++++++++++++--------------
   sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp | 1
   4 files changed, 143 insertions(+), 110 deletions(-)

Copied: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/directed.hpp (from r45965, /sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/directed.hpp 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
@@ -1,20 +1,13 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_HPP
 
-#include <list>
-
-#include <boost/graphs/utility/ordered.hpp>
-#include <boost/graphs/adjacency_list/vertex.hpp>
-#include <boost/graphs/adjacency_list/edge.hpp>
 #include <boost/graphs/adjacency_list/storage_traits.hpp>
 
 namespace boost {
 namespace graphs {
 namespace adj_list {
 
-// Implementation of directed adjacency lists.
-
 // Forward declarations
 template <typename VP, typename EP, typename V, typename E, template <typename> class VES> struct directed_vertex;
 template <typename VP, typename EP, typename V, typename E> struct directed_edge;

Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/edge.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/edge.hpp 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
@@ -1,8 +1,8 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EDGE_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EGE_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_EDGE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_EDGE_HPP
 
-#include <boost/graphs/utility/unordered_pair.hpp>
+#include <boost/graphs/utility/ordered_pair.hpp>
 #include <boost/graphs/adjacency_list/edge.hpp>
 
 namespace boost {
@@ -10,15 +10,7 @@
 namespace adj_list {
 
 /**
- * An undirected edge is an unordered pair of pointers to its endpoints. Note
- * that because the unordered pair is instantiated over pointers, these are
- * trivially ordered by their addresses. There is no other way available to
- * order the vertices (i.e., by custom comparison).
- *
- * Note that the edge does allow construction over null endpoints, but that
- * isn't really recommended since we don't offer any real mutators for the
- * endpoints. For constructors that do take vertex descriptors, we might also
- * point out that the ordering is not guaranteed after construction.
+ * A directed edge
  */
 template <
         typename VertexProps,
@@ -26,7 +18,7 @@
         typename VertexDesc,
         typename EdgeDesc
>
-class undirected_edge
+class directed_edge
     : public edge<EdgeProps>
 {
 public:
@@ -37,10 +29,10 @@
     // leverage vertex properties for add/insert functions.
     typedef VertexDesc vertex_descriptor;
 
- undirected_edge();
- undirected_edge(properties_type const& ep);
- undirected_edge(vertex_descriptor u, vertex_descriptor v);
- undirected_edge(vertex_descriptor u, vertex_descriptor v, properties_type const& ep);
+ directed_edge();
+ directed_edge(properties_type const& ep);
+ directed_edge(vertex_descriptor u, vertex_descriptor v);
+ directed_edge(vertex_descriptor u, vertex_descriptor v, properties_type const& ep);
 
     unordered_pair<vertex_descriptor> const& ends() const;
 
@@ -59,25 +51,25 @@
     typename VP, typename EP, typename V, typename E
 
 template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge()
+directed_edge<VP,EP,V,E>::directed_edge()
     : edge<EP>()
     , _ends()
 { }
 
 template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(properties_type const& ep)
+directed_edge<VP,EP,V,E>::directed_edge(properties_type const& ep)
     : edge<EP>(ep)
     , _ends()
 { }
 
 template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u, vertex_descriptor v)
+directed_edge<VP,EP,V,E>::directed_edge(vertex_descriptor u, vertex_descriptor v)
     : edge<EP>()
     , _ends(u, v)
 { }
 
 template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u,
+directed_edge<VP,EP,V,E>::directed_edge(vertex_descriptor u,
                                             vertex_descriptor v,
                                             properties_type const& ep)
     : edge<EP>(ep)
@@ -88,8 +80,8 @@
  * Return the endpoints of the edge.
  */
 template <BOOST_GRAPH_UE_PARAMS>
-unordered_pair<typename undirected_edge<VP,EP,V,E>::vertex_descriptor> const&
-undirected_edge<VP,EP,V,E>::ends() const
+unordered_pair<typename directed_edge<VP,EP,V,E>::vertex_descriptor> const&
+directed_edge<VP,EP,V,E>::ends() const
 { return _ends; }
 
 /**
@@ -97,8 +89,8 @@
  * necessarily the same as the way it is connected.
  */
 template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::source() const
+typename directed_edge<VP,EP,V,E>::vertex_descriptor
+directed_edge<VP,EP,V,E>::source() const
 { return _ends.first(); }
 
 /**
@@ -106,16 +98,16 @@
  * necessarily the same as the way it is connected.
  */
 template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::target() const
+typename directed_edge<VP,EP,V,E>::vertex_descriptor
+directed_edge<VP,EP,V,E>::target() const
 { return _ends.second(); }
 
 /**
  * Return the vertex opposite the given vertex on this edge.
  */
 template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::opposite(vertex_descriptor u) const
+typename directed_edge<VP,EP,V,E>::vertex_descriptor
+directed_edge<VP,EP,V,E>::opposite(vertex_descriptor u) const
 {
     return u == _ends.first() ? _ends.second() : _ends.first();
 }
@@ -132,8 +124,8 @@
  */
 template <BOOST_GRAPH_UE_PARAMS>
 bool
-operator<(undirected_edge<VP,EP,V,E> const& a,
- undirected_edge<VP,EP,V,E> const& b)
+operator<(directed_edge<VP,EP,V,E> const& a,
+ directed_edge<VP,EP,V,E> const& b)
 {
     return a.ends() < b.ends();
 }
@@ -144,8 +136,8 @@
  */
 template <BOOST_GRAPH_UE_PARAMS>
 bool
-operator==(undirected_edge<VP,EP,V,E> const& a,
- undirected_edge<VP,EP,V,E> const& b)
+operator==(directed_edge<VP,EP,V,E> const& a,
+ directed_edge<VP,EP,V,E> const& b)
 {
     return a.ends() == b.ends();
 }

Deleted: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/undirected.hpp 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
+++ (empty file)
@@ -1,64 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_HPP
-
-#include <list>
-
-#include <boost/graphs/utility/ordered.hpp>
-#include <boost/graphs/adjacency_list/vertex.hpp>
-#include <boost/graphs/adjacency_list/edge.hpp>
-#include <boost/graphs/adjacency_list/storage_traits.hpp>
-
-namespace boost {
-namespace graphs {
-namespace adj_list {
-
-// Implementation of directed adjacency lists.
-
-// Forward declarations
-template <typename VP, typename EP, typename V, typename E, template <typename> class VES> struct directed_vertex;
-template <typename VP, typename EP, typename V, typename E> struct directed_edge;
-
-// Unfortunately, I have to hack out a little tag dispatch here... This will
-// go away with the concepts.
-struct directed_tag { };
-
-/**
- * This is the metafunction for directed types.
- */
-template <
- typename VertexProps,
- typename EdgeProps,
- typename VertexStore,
- typename EdgeStore,
- template <typename> class VertexEdgeStore
- >
-struct directed
-{
- typedef directed_tag tag;
-
- typedef vertex_desc<
- typename storage_traits<VertexStore>::descriptor_type
- > vertex_descriptor;
-
- typedef edge_desc<
- typename storage_traits<EdgeStore>::descriptor_type
- > edge_descriptor;
-
- typedef directed_vertex<
- VertexProps, EdgeProps, vertex_descriptor, edge_descriptor, VertexEdgeStore
- > vertex_type;
-
- typedef directed_edge<
- VertexProps, EdgeProps, vertex_descriptor, edge_descriptor
- > edge_type;
-};
-
-} /* namespace adj_list */
-} /* namespace graphs */
-} /* namespace boost */
-
-#include <boost/graphs/adjacency_list/directed/vertex.hpp>
-#include <boost/graphs/adjacency_list/directed/edge.hpp>
-
-#endif

Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/directed/vertex.hpp 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
@@ -1,6 +1,6 @@
 
-#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
-#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_VERTEX_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_DIRECTED_VERTEX_HPP
 
 #include <boost/graphs/adjacency_list/vertex.hpp>
 
@@ -9,13 +9,14 @@
 namespace adj_list {
 
 /**
- * An undirected vertex tracks the incident edges of the given vertex. Note
- * that the edges actually being stored are pointers to edges in the graph's
- * edge list. The reason for this is so we don't duplicate the properties
- * of each edge.
+ * A directed vertex provides access to two separate sets of incident
+ * edges - both in-edges and out-edges.
  *
- * @todo What happens if I store incident edges as a pair... The edge and the
- * opposite end. That might be kind of interesting.
+ * This varies from the original BGL, which provided directed (which
+ * was only the out edges) and bidirectional (both in and out edges).
+ * The cost of providing both as a directed graph doesn't particularly
+ * phase me too much. I'm basically saying that I haven't seen too
+ * many useful applications of half-directed graphs.
  */
 template <
         typename VertexProps,
@@ -24,7 +25,7 @@
         typename EdgeDesc,
         template <typename> class VertexEdgeStore
>
-class undirected_vertex
+class directed_vertex
     : public vertex<VertexProps>
 {
 public:
@@ -39,8 +40,8 @@
     typedef std::pair<incidence_iterator, incidence_iterator> incidence_range;
     typedef typename vertex_edge_store::size_type degree_type;
 
- undirected_vertex();
- undirected_vertex(VertexProps const& vp);
+ directed_vertex();
+ directed_vertex(VertexProps const& vp);
 
     // Connection interface.
     void connect_to(edge_descriptor e);
@@ -51,31 +52,40 @@
     void disconnect_from(edge_descriptor e);
     void disconnect_all();
 
- std::pair<incidence_iterator, incidence_iterator> incident_edges() const;
- incidence_iterator begin_incident_edges() const;
- incidence_iterator end_incident_edges() const;
+ // Edge iterators
+ incidence_range out_edges() const;
+ incidence_iterator begin_out_edges() const;
+ incidence_iterator end_out_edges() const;
+
+ incidence_range in_edges() const;
+ incidence_iterator begin_in_edges() const;
+ incidence_iterator end_in_edges() const;
 
- degree_type degree() const;
+ degree_type out_degree() const;
+ degree_type in_degree() const;
 
 private:
- vertex_edge_store _edges;
+ vertex_edge_store _out;
+ vertex_edge_store _in;
 };
 
 // Functions
 
-#define BOOST_GRAPH_UV_PARAMS \
+#define BOOST_GRAPH_DV_PARAMS \
     typename VP, typename EP, typename V, typename E, template <typename> class VES
 
-template <BOOST_GRAPH_UV_PARAMS>
-undirected_vertex<VP,EP,V,E,VES>::undirected_vertex()
+template <BOOST_GRAPH_DV_PARAMS>
+directed_vertex<VP,EP,V,E,VES>::directed_vertex()
     : vertex<VP>()
- , _edges()
+ , _out()
+ , _in()
 { }
 
-template <BOOST_GRAPH_UV_PARAMS>
-undirected_vertex<VP,EP,V,E,VES>::undirected_vertex(VP const& vp)
+template <BOOST_GRAPH_DV_PARAMS>
+directed_vertex<VP,EP,V,E,VES>::directed_vertex(VP const& vp)
         : vertex<VP>(vp)
- , _edges()
+ , _out()
+ , _in()
     { }
 
 /**
@@ -83,97 +93,134 @@
  * that this vertex is neither truly the source nor target of the edge. This
  * does not guarantee that source(e) == this.
  */
-template <BOOST_GRAPH_UV_PARAMS>
+template <BOOST_GRAPH_DV_PARAMS>
 void
-undirected_vertex<VP,EP,V,E,VES>::connect_to(edge_descriptor e)
+directed_vertex<VP,EP,V,E,VES>::connect_to(edge_descriptor e)
 {
- _edges.add(e);
+ _out.add(e);
 }
 
 /**
  * Connect this vertex to the vertex at the opposite end of the edge. Note that
  * this does not guarantee that the target(e) == this.
  */
-template <BOOST_GRAPH_UV_PARAMS>
+template <BOOST_GRAPH_DV_PARAMS>
 void
-undirected_vertex<VP,EP,V,E,VES>::connect_from(edge_descriptor e)
-{
- _edges.add(e);
+directed_vertex<VP,EP,V,E,VES>::connect_from(edge_descriptor e)
+{
+ _in.add(e);
 }
 
 /**
  * Locally remove the given edge that connects this vertex to another endpoint.
  */
-template <BOOST_GRAPH_UV_PARAMS>
+template <BOOST_GRAPH_DV_PARAMS>
 void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_to(edge_descriptor e)
+directed_vertex<VP,EP,V,E,VES>::disconnect_to(edge_descriptor e)
 {
- _edges.remove(e);
+ _out.remove(e);
 }
 
 /**
  * Locally remove the given edge that connects this vertex to another endpoint.
  */
-template <BOOST_GRAPH_UV_PARAMS>
+template <BOOST_GRAPH_DV_PARAMS>
 void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_from(edge_descriptor e)
-{
- _edges.remove(e);
+directed_vertex<VP,EP,V,E,VES>::disconnect_from(edge_descriptor e)
+{
+ _in.remove(e);
 }
 
 /**
  * Locally disconnect of all the incident edges from this vertex. Note that
  * this is really only used by the disconnect algorithm.
  */
-template <BOOST_GRAPH_UV_PARAMS>
+template <BOOST_GRAPH_DV_PARAMS>
 void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_all()
+directed_vertex<VP,EP,V,E,VES>::disconnect_all()
 {
- _edges.clear();
+ _out.clear();
+ _in.clear();
 }
 
 /**
- * Get an iterator range over the incident edges of this vertex.
+ * Get an iterator range over the out edges of this vertex.
  */
-template <BOOST_GRAPH_UV_PARAMS>
-std::pair<
- typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator,
- typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
- >
-undirected_vertex<VP,EP,V,E,VES>::incident_edges() const
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_range
+directed_vertex<VP,EP,V,E,VES>::out_edges() const
+{
+ return std::make_pair(_out.begin(), _out.end());
+}
+
+/**
+ * Get an iterator to the first in edge.
+ */
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_iterator
+directed_vertex<VP,EP,V,E,VES>::begin_out_edges() const
+{
+ return _out.begin();
+}
+
+/**
+ * Get an iterator pas the end of the out edges.
+ */
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_iterator
+directed_vertex<VP,EP,V,E,VES>::end_out_edges() const
+{
+ return _out.end();
+}
+
+/**
+ * Get an iterator range to the in-edges.
+ */
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_range
+directed_vertex<VP,EP,V,E,VES>::in_edges() const
+{
+ return std::make_pair(_in.begin(), _in.end());
+}
+
+/**
+ * Get an iterator to the first in-edge.
+ */
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_iterator
+directed_vertex<VP,EP,V,E,VES>::begin_in_edges() const
 {
- return std::make_pair(_edges.begin(), _edges.end());
+ return _in.begin();
 }
 
 /**
- * Get an iterator to the first incident edge.
+ * Get an iterator past the end of in edges.
  */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
-undirected_vertex<VP,EP,V,E,VES>::begin_incident_edges() const
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::incidence_iterator
+directed_vertex<VP,EP,V,E,VES>::end_in_edges() const
 {
- return _edges.begin();
+ return _in.end();
 }
 
 /**
- * Get an iterator pas the end of the incident edges.
+ * Return the out-degree of this vertex.
  */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
-undirected_vertex<VP,EP,V,E,VES>::end_incident_edges() const
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::degree_type
+directed_vertex<VP,EP,V,E,VES>::out_degree() const
 {
- return _edges.end();
+ return _out.size();
 }
 
 /**
- * Return the degree of this vertex. The degree of the vertex is the number
- * of incident edges.
+ * Return the out-degree of this vertex.
  */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::degree_type
-undirected_vertex<VP,EP,V,E,VES>::degree() const
+template <BOOST_GRAPH_DV_PARAMS>
+typename directed_vertex<VP,EP,V,E,VES>::degree_type
+directed_vertex<VP,EP,V,E,VES>::in_degree() const
 {
- return _edges.size();
+ return _in.size();
 }
 
 /**
@@ -184,7 +231,7 @@
  */
 template <typename Graph>
 void
-disconnect(Graph& g, typename Graph::vertex_type& u, undirected_tag)
+disconnect(Graph& g, typename Graph::vertex_type& u, directed_tag)
 {
     // Undirected - iterate over each of the incident edges I and get the
     // opposite vertex w. Remove all edges from the adjacent vertex that
@@ -203,8 +250,8 @@
     vertex_descriptor ud = g.descriptor(u);
 
     incidence_iterator
- i = u.begin_incident_edges(),
- end = u.end_incident_edges();
+ i = u.begin_incident_out(),
+ end = u.end_incident_out();
     for( ; i != end; ++i) {
         // Get the vertex at the opposite end of the current edge.
         edge_descriptor ed = *i;
@@ -222,7 +269,7 @@
     u.disconnect_all();
 }
 
-#undef BOOST_GRAPH_UV_PARAMS
+#undef BOOST_GRAPH_DV_PARAMS
 
 } /* namespace adj_list */
 } /* namespace graphs */

Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp 2008-05-30 19:49:43 EDT (Fri, 30 May 2008)
@@ -26,5 +26,6 @@
 // for directed vertices that simply returns or something like that.
 
 #include <boost/graphs/adjacency_list/undirected/undirected.hpp>
+#include <boost/graphs/adjacency_list/directed/directed.hpp>
 
 #endif


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