|
|
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