|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-06-19 10:26:56
Author: asutton
Date: 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
New Revision: 46509
URL: http://svn.boost.org/trac/boost/changeset/46509
Log:
Initial support for directed graphs. Can now add vertices, edges. Implemented
degree functions.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 61 ++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 340 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 103 ++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 9
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp | 43 ++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 80 +--------
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 78 ++++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 45 +---
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 5
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 7
10 files changed, 617 insertions(+), 154 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -2,15 +2,68 @@
#ifndef DIRECTED_EDGE_HPP
#define DIRECTED_EDGE_HPP
-#include "ordered_pair.hpp"
-
/**
- * A directed edge represents and edge within directed.
+ * A directed edge represents an edge in a directed graph. A directed edge is
+ * uniquely identified by its source and target verties and edge property.
+ *
+ * @param VertexDesc A vertex descriptor
+ * @param OutDesc An out edge descriptor.
*/
-template <typename SourceDesc, typename TargetDesc>
+template <typename VertexDesc, typename OutDesc>
class directed_edge
{
public:
+ typedef VertexDesc vertex_descriptor;
+ typedef OutDesc out_descriptor;
+ typedef typename out_descriptor::edge_properties edge_properties;
+
+ /** @name Constructors */
+ //@{
+ inline directed_edge()
+ : _src()
+ , _out()
+ { }
+
+ inline directed_edge(vertex_descriptor v, OutDesc o)
+ : _src(v)
+ , _out(o)
+ { }
+ //@}
+
+ /** Return the source of the edge. */
+ inline vertex_descriptor source() const
+ { return _src; }
+
+ /** Return the target of the edge. */
+ inline vertex_descriptor target() const
+ { return _out.target(); }
+
+ /** @name Property Accessors
+ * Return the properties associated with the edge.
+ */
+ //@{
+ inline edge_properties& properties()
+ { return _out.properties(); }
+
+ inline edge_properties const& properties() const
+ { return _out.properties(); }
+ //@}
+
+ /** @name Operators */
+ //@{
+ inline bool operator==(directed_edge const& x)
+ { return _src == x._src && _out = x._out; }
+
+ inline bool operator!=(directed_edge const& x)
+ { return !operator==(x); }
+
+ inline bool operator<(directed_edge const& x)
+ { return std::make_pair(_src, _out) < std::make_pair(x._src, x._out); }
+ //@}
+
+private:
+ VertexDesc _src;
+ OutDesc _out;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -2,7 +2,9 @@
#ifndef DIRECTED_GRAPH_HPP
#define DIRECTED_GRAPH_HPP
-// Notes on directed graphs... Unlike undirected graphs, which are required
+#include <boost/static_assert.hpp>
+
+// Notes on directed graphs... Unlike directed graphs, which are required
// to globally store edge properties, the vertices directed graphs act as
// the stores for nested properties. Edge properties are stored with the
// out edges of each vertex.
@@ -37,44 +39,58 @@
public:
typedef VertexProps vertex_properties;
typedef EdgeProps edge_properties;
-
+
// In order to create the vertex store, we have to create the vertex type.
// In order to create the vertex type we need to create the edge store
// types. There are two types of edge store types - one that stores outgoing
// edges (a pair of vertex and edge property) and another that stores the
// descriptors of incoming vertices.
-
+
// We have to generate the vertex descriptor before we can do anything else.
typedef typename VertexStore::descriptor_type vertex_descriptor;
-
- // Use the vertex descriptor and edge properties to generate the out edge
- // store for the graph.
+
+ // Use the vertex descriptor and edge properties to generate the out and in
+ // edge stores for the graph. Get the out edge descriptor type from the out
+ // store.
typedef typename EdgeStore::template out_store<vertex_descriptor, edge_properties>::type out_edge_store;
-
- // Like above, but generate the in edge store.
- typedef typename EdgeStore::template in_store<vertex_descriptor, edge_properties>::type in_edge_store;
-
+ typedef typename out_edge_store::out_descriptor out_descriptor;
+ typedef typename EdgeStore::template in_store<vertex_descriptor, out_descriptor>::type in_edge_store;
+
+ // We can now generate the edge descriptor.
+ typedef directed_edge<vertex_descriptor, out_descriptor> edge_descriptor;
+
// Generate the vertex type over the vertex properties, and in/out stores.
+ // We can also pull size
// NOTE: Omitting the in-edge store allows us to create half-directed
// graphs.
typedef directed_vertex<vertex_properties, out_edge_store, in_edge_store> vertex_type;
-
+ typedef typename vertex_type::out_size_type out_edges_size_type;
+ typedef typename vertex_type::in_size_type in_edges_size_type;
+ typedef typename vertex_type::incident_size_type incident_edges_size_type;
+
// Finally, use the vertex type to generate the vertex store. This is then
// used to generate types iteration and size functions.
typedef typename VertexStore::template store<vertex_type>::type vertex_store;
typedef typename vertex_store::size_type vertices_size_type;
typedef typename vertex_store::vertex_iterator vertex_iterator;
typedef typename vertex_store::vertex_range vertex_range;
+
// FIXME: This is a bit hacky, but without constrained members, we need a key
// type to enable mapped vertices.
typedef typename VertexStore::key_type vertex_key;
+
// Constructors
directed_graph();
- /** @name Vertex Set
- * These functions operate (mostly) on the vertices of the graph. These
- * functions include the ability to add, disconnect, and remove vertices.
+ /** @name Add Vertex
+ * Add a vertex to the graph. Add operations are determined by the concepts
+ * modeled by the vertex set.
+ *
+ * UnlabeledVertices add_vertex()
+ * LabeledVerteces add_vertex(vertex_properties)
+ * LabeledUniqueVertices add_vertex(vertex_properties)
+ * MappedUniqueVertices add_vertex(vertex_key)
*/
//@{
vertex_descriptor add_vertex();
@@ -82,6 +98,93 @@
vertex_descriptor add_vertex(vertex_key const&, vertex_properties const&);
//@}
+ /** @name Find Vertex
+ * Find a vertex in the graph. These methods only exist for graphs that
+ * have UniqueVertices. These functions can also be used to find the first
+ * vertex of a non-unique vertices.
+ *
+ * LabeledUniqueVertices find_vertex(vertex_properties)
+ * MappedUniqueVertices find_vertex(vertex_key)
+ */
+ //@{
+ vertex_descriptor find_vertex(vertex_properties const&) const;
+ vertex_descriptor find_vertex(vertex_key const&) const;
+ //@{
+
+ /** @name Disconnect Vertex
+ * Disconnect a vertex from the graph by removing all of its incident edges.
+ * These functions only exist for graphs with ReducibleEdgeSets. Functions
+ * that take properties or keys are provided for convenience, but have
+ * additional dependencies and cost. These additonal functions are
+ * equivalent to disconnect_vertex(find_vertex(x)) where x is either a
+ * vertex_properties or vertex_key.
+ *
+ * ReducibleEdgeSet disconnect_vertex(vertex_descriptor)
+ * LabeledUniqueVertices disconnect_vertex(vertex_properties)
+ * MappedUniqueVertices disconnect_vertex(vertex_key)
+ */
+ //@{
+ void disconnect_vertex(vertex_descriptor);
+ void disconnect_vertex(vertex_properties const&);
+ void disconnect_vertex(vertex_key const&);
+ //@}
+
+ /** @name Remove Vertex
+ * Remove a vertex from the graph. These functions only exist for graphs
+ * with ReducibleVertexSets. Functions that take properties or keys are
+ * provided for convenience, but have additional requirements and cost.
+ * These additional functions are equivalent to remove_vertex(find_vertex(x))
+ * where x is either a vertex_properties or vertex_key.
+ *
+ * ReducibleVertexSet remove_vertex(vertex_descriptor)
+ * LabeledUniqueVertices remove_vertex(vertex_properties)
+ * MappedUniqueVertices remove_vertex(vertex_key)
+ */
+ //@{
+ void remove_vertex(vertex_descriptor);
+ void remove_vertex(vertex_properties const&);
+ void remove_vertex(vertex_key const&);
+ //@}
+
+ /** @name Vertex Key
+ * Return the key for the given vertex. This is only provided for graphs
+ * with MappedVertices (can be multimapped).
+ */
+ //@{
+ vertex_key const& key(vertex_descriptor) const;
+ //@{
+
+ /** @name Add Edge
+ * Add an edge, connecting two vertices, to the graph.
+ */
+ //@{
+ edge_descriptor add_edge(vertex_descriptor, vertex_descriptor);
+ edge_descriptor add_edge(vertex_properties const&, vertex_properties const&);
+ edge_descriptor add_edge(vertex_key const&, vertex_key const&);
+
+ edge_descriptor add_edge(vertex_descriptor, vertex_descriptor, edge_properties const&);
+ edge_descriptor add_edge(vertex_properties const&, vertex_properties const&, edge_properties const&);
+ edge_descriptor add_edge(vertex_key const&, vertex_key const&, edge_properties const&);
+ //@{
+
+ /** @name Degree
+ * Return the in/out or cumulative degree of the given vertex.
+ */
+ //@{
+ out_edges_size_type out_degree(vertex_descriptor v) const;
+ in_edges_size_type in_degree(vertex_descriptor v) const;
+ incident_edges_size_type degree(vertex_descriptor v) const;
+ //@}
+
+
+ /** @name Property Accessors
+ * Access the properties of the given vertex or edge.
+ */
+ //@{
+ vertex_properties& operator[](vertex_descriptor);
+ edge_properties& operator[](edge_descriptor);
+ //@{
+
private:
vertex_store _verts;
};
@@ -95,20 +198,23 @@
{ }
/**
- * Add a vertex to the graph with no or default graph properties. Return a
- * descriptor to the vertex being returned.
+ * Add a vertex to the graph with no or default graph properties, and return a
+ * descriptor to the vertex being returned. This function should not be used
+ * with graphs that have LabeledUniqueVertices since each addition will return
+ * the same default-propertied vertex.
*/
template <BOOST_GRAPH_DG_PARAMS>
typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
directed_graph<VP,EP,VS,ES>::add_vertex()
{
+ // BOOST_STATIC_ASSERT(!LabeledUniqueVertices<this_type>);
return _verts.add();
}
/**
* Add a vertex to the graph with the given properties and return a descriptor
- * for that vertex. If the graph has labeled, unique vertices, and the given
- * properties describe a vertex already in the graph, then a new vertex is not
+ * for that vertex. If the graph has labeled, unique vertices, and the given
+ * properties describe a vertex already in the graph, then a new vertex is not
* added and the descriptor for the existing vertex is returned.
*/
template <BOOST_GRAPH_DG_PARAMS>
@@ -130,4 +236,202 @@
return _verts.add(k, vp);
}
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
+directed_graph<VP,EP,VS,ES>::find_vertex(vertex_properties const& vp) const
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ return _verts.find(vp);
+}
+
+/**
+ * Find the vertex with the given properties, returning a descriptor to it.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
+directed_graph<VP,EP,VS,ES>::find_vertex(vertex_key const& k) const
+{
+ return _verts.find(k);
+}
+
+/**
+ * Disconnect the vertex from the graph. This removes all edges incident (both
+ * incoming and outgoing) to the vertex, but will not remove the vertex itself.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_descriptor v)
+{
+ // TODO: Implement me!
+}
+
+/**
+ * Disconnect the vertex having the given properties from the graph.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ disconnect_vertex(find_vertex(vp));
+}
+
+/**
+ * Disconnect the vertex having the given key from the graph.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::disconnect_vertex(vertex_key const& k)
+{
+ disconnect_vertex(find_vertex(k));
+}
+
+/**
+ * Remove the vertex from the graph. This will disconnect the vertex from the
+ * graph prior to remove.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
+{
+ disconnect_vertex(v);
+ _verts.remove(v);
+}
+
+/**
+ * Remove the vertex from the graph identified by the given properties.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_vertex(vertex_properties const& vp)
+{
+ BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
+ disconnect_vertex(vp);
+ _verts.remove(vp);
+}
+
+/**
+ * Remove the vertex from the graph identified by the given key.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+void
+directed_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
+{
+ disconnect_vertex(k);
+ _verts.remove(k);
+}
+
+/**
+ * Return the key associated with the given vertex. This function is only
+ * available for graphs with mapped vertices.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_key const&
+directed_graph<VP,EP,VS,ES>::key(vertex_descriptor v) const
+{
+ return _verts.key(v);
+}
+
+/**
+ * Add an edge, connecting the two vertices to the graph with default or no
+ * properties. The edge is added to both the in and out edge stores of the
+ * target and source vertices respectively.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u, vertex_descriptor v)
+{
+ return add_edge(u, v, edge_properties());
+}
+
+/**
+ * Add an edge, connecting the two vertices to the graph with the given
+ * properties. The edge is added to both the in and out edge stores of the
+ * target and source vertices respectively.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_descriptor
+directed_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ edge_properties const& ep)
+{
+ vertex_type &src = _verts.vertex(u);
+ vertex_type &tgt = _verts.vertex(v);
+
+ // Do we add the edge or not?
+ std::pair<typename vertex_type::out_iterator, bool> ins = src.allow(v);
+ if(ins.second) {
+ // The addition is allowed... Was there already an edge there? If not,
+ // connect u to v (and vice-versa) with the given properties. Otherwise,
+ // just return the existing edge.
+ if(ins.first == src.end_out()) {
+ out_descriptor o = src.connect_to(v, ep);
+ tgt.connect_from(u, o);
+ return edge_descriptor(u, o);
+ }
+ else {
+ return edge_descriptor(u, *ins.first);
+ }
+ }
+ else {
+ // Can't add the edge? This is a flat refusal (as in a loop).
+ }
+
+ return edge_descriptor();
+}
+
+/**
+ * Return the out degree of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::out_edges_size_type
+directed_graph<VP,EP,VS,ES>::out_degree(vertex_descriptor v) const
+{
+ return _verts.vertex(v).out_degree();
+}
+
+/**
+ * Return the in degree of the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::in_edges_size_type
+directed_graph<VP,EP,VS,ES>::in_degree(vertex_descriptor v) const
+{
+ return _verts.vertex(v).in_degree();
+}
+
+/**
+ * Return the degree of the given vertex. This is simply the sum of the in
+ * and out degree of the vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::incident_edges_size_type
+directed_graph<VP,EP,VS,ES>::degree(vertex_descriptor v) const
+{
+ return _verts.vertex(v).degree();
+}
+
+/**
+ * Return the properties for the given vertex.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_properties&
+directed_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
+{
+ return _verts.properties(v);
+}
+
+/**
+ * Return the properties for the given edge.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::edge_properties&
+directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
+{
+ return e.properties();
+}
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -16,17 +16,48 @@
typedef VertexProps vertex_properties;
typedef typename out_store::vertex_descriptor vertex_descriptor;
+ typedef typename OutStore::edge_properties edge_properties;
+ typedef typename OutStore::out_descriptor out_descriptor;
+
typedef typename out_store::const_iterator out_iterator;
typedef typename out_store::size_type out_size_type;
-
+
typedef typename in_store::const_iterator in_iterator;
typedef typename in_store::size_type in_size_type;
- inline directed_vertex();
- inline directed_vertex(vertex_properties const& vp);
+ typedef out_size_type incident_size_type;
+
+
+ /** @name Constructors */
+ //@{
+ inline directed_vertex()
+ : _props()
+ , _out()
+ , _in()
+ { }
+
+ inline directed_vertex(vertex_properties const& vp)
+ : _props(vp)
+ , _out()
+ , _in()
+ { }
+ //@}
+
+
+ std::pair<out_iterator, bool> allow(vertex_descriptor) const;
+
+ out_descriptor connect_to(vertex_descriptor, edge_properties const&);
+ void connect_from(vertex_descriptor, out_descriptor);
+
+ /** @name Property Accessors */
+ //@{
+ inline vertex_properties& properties()
+ { return _props; }
+
+ inline vertex_properties const& properties() const
+ { return _props; }
+ //@}
- inline vertex_properties& properties();
- inline vertex_properties const& properties() const;
/** @name Out Edges */
//@{
@@ -35,30 +66,38 @@
inline out_iterator end_out() const
{ return _out.end(); }
-
- inline out_size_type out_degree() const
- { return _out.size(); }
//@}
-
+
/** @name In Edges */
//@{
inline in_iterator begin_in() const
{ return _in.begin(); }
-
+
inline in_iterator end_in() const
{ return _in.end(); }
-
+ //@}
+
+
+ /** @name Degree */
+ //@{
+ inline out_size_type out_degree() const
+ { return _out.size(); }
+
inline in_size_type in_degree() const
{ return _in.size(); }
+
+ inline incident_size_type degree() const
+ { return out_degree() + in_degree(); }
//@}
-
+
+
/** @name Operators */
//@{
inline bool operator==(directed_vertex const& x) const
{ return _props == x._props; }
inline bool operator!=(directed_vertex const& x) const
- { return !this->operator==(x); }
+ { return !this->operator==(x); }
inline bool operator<(directed_vertex const& x) const
{ return _props < x._props; }
@@ -70,4 +109,42 @@
in_store _in;
};
+/**
+ * Determine if the connection from this vertex to the other should be allwed.
+ * This depends in part upon the structure of the out out edge store and the
+ * policies used to configure the graph. This function returns a pair containing
+ * an iterator to an existing edge and a bool, determining if the edge should
+ * be added anyways.
+ */
+template <typename V, typename O, typename I>
+std::pair<typename directed_vertex<V,O,I>::out_iterator, bool>
+directed_vertex<V,O,I>::allow(vertex_descriptor v) const
+{
+ return _out.allow(v);
+}
+
+/**
+ * Connect this vertex to the vertex v with the given properties. Return an out
+ * edge descriptor for the new edge.
+ */
+template <typename V, typename O, typename I>
+typename directed_vertex<V,O,I>::out_descriptor
+directed_vertex<V,O,I>::connect_to(vertex_descriptor v, edge_properties const& ep)
+{
+ return _out.add(std::make_pair(v, ep));
+}
+
+/**
+ * Add a incoming edge from the vertex v with out edge descriptor o.
+ *
+ * Unfortunately, we can't combine this operation with connet_to() because we
+ * don't actually have a descriptor for this vertex.
+ */
+template <typename V, typename O, typename I>
+void
+directed_vertex<V,O,I>::connect_from(vertex_descriptor v, out_descriptor o)
+{
+ return _in.add(std::make_pair(v, o));
+}
+
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -67,13 +67,12 @@
};
// The in store metafunction generates the type of vector used to store
- // incoming edges (actually just the referencing vertex) of directed graph.
- // In edges are partially represented by the referencing vertex and a
- // pointer to the properties.
- template <typename VertexDesc, typename Props>
+ // incoming edges of directed graph. In edges are represented by the
+ // referencing vertex and an out edge descriptor.
+ template <typename VertexDesc, typename OutDesc>
struct in_store
{
- typedef std::pair<VertexDesc, Props*> in_pair;
+ typedef std::pair<VertexDesc, OutDesc> in_pair;
typedef SecondAlloc<in_pair> in_allocator;
typedef in_vector<in_pair, in_allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -2,12 +2,49 @@
#ifndef IN_VECTOR_HPP
#define IN_VECTOR_HPP
-template <typename Edge, typename Allocator>
+#include <vector>
+
+/**
+ * The in-edge vector references incoming edges from other vertices. Each edge
+ * can be uniquely identified by its source vertex and property descriptor.
+ *
+ * @param Edge A pair describing a vertex descriptor and out edgedescriptor.
+ * @param Alloc The allocator for edge pairs.
+ */
+template <typename Edge, typename Alloc>
class in_vector
{
+ typedef std::vector<Edge, Alloc> store_type;
public:
- typedef none const_iterator;
- typedef std::size_t size_type;
+ typedef Edge in_pair;
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type edge_descriptor;
+
+ typedef typename store_type::const_iterator const_iterator;
+ typedef typename store_type::size_type size_type;
+
+ in_vector()
+ : _edges()
+ { }
+
+ void add(in_pair);
+
+ /** Get the number of incoming edges (in degree). */
+ size_type size() const
+ { return _edges.size(); }
+
+private:
+ store_type _edges;
};
+/**
+ * Add the given pair to the edge set.
+ */
+template <typename E, typename A>
+void
+in_vector<E,A>::add(in_pair e)
+{
+ _edges.push_back(e);
+}
+
#endif
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-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -27,9 +27,12 @@
typedef typename store_type::size_type size_type;
// Constructors
- incidence_vector();
+ inline incidence_vector()
+ : _edges()
+ { }
std::pair<const_iterator, bool> allow(vertex_descriptor) const;
+
void add(incidence_pair);
iterator find(incidence_pair);
const_iterator find(incidence_pair) const;
@@ -47,21 +50,6 @@
store_type _edges;
};
-#define BOOST_GRAPH_IV_PARAMS \
- typename E, typename A
-
-template <BOOST_GRAPH_IV_PARAMS>
-incidence_vector<E,A>::incidence_vector()
- : _edges()
-{ }
-
-template <BOOST_GRAPH_IV_PARAMS>
-void
-incidence_vector<E,A>::add(incidence_pair e)
-{
- _edges.push_back(e);
-}
-
/**
* Incidence vectors always allow the addition of edges, assuming that no
* policy conflicts exist. The first element of the return is the end() of the
@@ -69,7 +57,7 @@
*
* @complexity O(1)
*/
-template <BOOST_GRAPH_IV_PARAMS>
+template <typename E, typename A>
std::pair<typename incidence_vector<E,A>::const_iterator, bool>
incidence_vector<E,A>::allow(vertex_descriptor v) const
{
@@ -77,60 +65,14 @@
return make_pair(_edges.end(), true);
}
-
-#undef BOOST_GRAPH_IV_PARAMS
-
-#if 0
-
-// Functions
-
-template <typename E>
-vertex_edge_vector<E>::vertex_edge_vector()
- : base_type()
-{ }
-
-template <typename E>
-void
-vertex_edge_vector<E>::add(edge_descriptor e)
-{
- this->_store.push_back(e);
-}
-
-template <typename E>
-typename vertex_edge_vector<E>::iterator
-vertex_edge_vector<E>::find(edge_descriptor e)
-{
- return std::find(this->_store.begin(), this->_store.end(), e);
-}
-
-template <typename E>
-typename vertex_edge_vector<E>::const_iterator
-vertex_edge_vector<E>::find(edge_descriptor e) const
-{
- return std::find(this->_store.begin(), this->_store.end(), e);
-}
-
-template <typename E>
-void
-vertex_edge_vector<E>::remove(edge_descriptor e)
-{
- this->_store.erase(find(e));
-}
-
-template <typename E>
+/**
+ * Add the incidence pair to the vector.
+ */
+template <typename E, typename A>
void
-vertex_edge_vector<E>::clear()
-{
- this->_store.clear();
-}
-
-template <typename E>
-typename vertex_edge_vector<E>::size_type
-vertex_edge_vector<E>::size() const
+incidence_vector<E,A>::add(incidence_pair e)
{
- return this->_store.size();
+ _edges.push_back(e);
}
#endif
-
-#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -0,0 +1,53 @@
+
+#ifndef OUT_DESCRIPTOR_HPP
+#define OUT_DESCRIPTOR_HPP
+
+/**
+ * The out descriptor wraps an opaque reference to an out edge pair and
+ * provides some convenience functions for translating between the elements
+ * of the referenced pair and their "descriptors".
+ *
+ * @param OutPair The pair of vertex descriptor and edge property being
+ * described.
+ */
+template <typename OutPair>
+struct basic_out_descriptor
+{
+ typedef typename OutPair::first_type vertex_descriptor;
+ typedef typename OutPair::second_type edge_properties;
+
+ /** @name Constructors */
+ //@{
+ inline basic_out_descriptor()
+ : _d(0)
+ { }
+
+ inline basic_out_descriptor(basic_out_descriptor const& x)
+ : _d(x._d)
+ { }
+
+ inline basic_out_descriptor(OutPair& o)
+ : _d(&o)
+ { }
+
+ inline basic_out_descriptor(OutPair const& o)
+ : _d(&const_cast<OutPair&>(o))
+ { }
+ //@{
+
+ OutPair& pair() const
+ { return reinterpret_cast<OutPair*>(_d); }
+
+ vertex_descriptor target() const
+ { return pair().first; }
+
+ edge_properties& properties()
+ { return pair().second; }
+
+ edge_properties const& properties() const
+ { return pair().second; }
+
+ mutable void* _d;
+};
+
+#endif
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-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -4,14 +4,21 @@
#include <vector>
+#include "out_descriptor.hpp"
+
/**
* The out vector implements vector-based, out-edge storage for directed graphs.
- * As an out-edge store, this type stores an edge property with the descriptor
- * referencing the adjacenct vertex. Vector-based stores support fast inserts,
- * slow finds, and do not allow remove operations.
+ * out-edges are uniquely identified by their target vertex and property
+ * descriptor. As an out-edge store, this type stores an edge property with the
+ * target vertex descriptor. Vector-based stores support fast inserts, slow
+ * finds, and do not allow remove operations.
+ *
+ * The edge is required to be a pair containing a vertex descriptor and a edge
+ * property (not descriptor). This type defines the out_descriptor - an opaque
+ * reference to a target/property pair.
*
- * Here, the edge is required to be a pair containing a vertex descriptor and a
- * edge property.
+ * @param Edge A pair describing a vertex descriptor and the edge properties.
+ * @param Alloc The allocator for edge pairs.
*/
template <typename Edge, typename Alloc>
class out_vector
@@ -21,16 +28,71 @@
typedef Edge out_pair;
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type edge_properties;
-
+
typedef typename store_type::const_iterator const_iterator;
typedef typename store_type::size_type size_type;
+ typedef basic_out_descriptor<out_pair> out_descriptor;
+
inline out_vector()
- : _store()
+ : _edges()
{ }
+ std::pair<const_iterator, bool> allow(vertex_descriptor v) const;
+ out_descriptor add(out_pair);
+
+ vertex_descriptor vertex(out_descriptor) const;
+
+ /** @name Iterators and Size */
+ //@{
+ inline const_iterator begin() const
+ { return _edges.begin(); }
+
+ inline const_iterator end() const
+ { return _edges.end(); }
+
+ /** Get the number of outgoing edges. */
+ inline size_type size() const
+ { return _edges.size(); }
+ //@{
+
private:
- store_type _store;
+ store_type _edges;
};
+/**
+ * Out vectors always allow the insertion of new edges, unless configured by
+ * policy to do otherwise.
+ */
+template <typename E, typename A>
+std::pair<typename out_vector<E,A>::const_iterator, bool>
+out_vector<E,A>::allow(vertex_descriptor v) const
+{
+ return std::make_pair(_edges.end(), true);
+}
+
+/**
+ * Add the incident edge, returning the property descriptor of the added
+ * incidence pair.
+ */
+template <typename E, typename A>
+typename out_vector<E,A>::out_descriptor
+out_vector<E,A>::add(out_pair e)
+{
+ _edges.push_back(e);
+ return _edges.back();
+}
+
+/**
+ * Return the target vertex of the given edge property descriptor. Because each
+ * property descriptor references a unique edge, we can easily access the
+ * corresponding target vertex.
+ */
+template <typename E, typename A>
+typename out_vector<E,A>::vertex_descriptor
+out_vector<E,A>::vertex(out_descriptor p) const
+{
+ return p.target();
+}
+
#endif
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-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -4,22 +4,6 @@
#include "none.hpp"
-// Various issues...
-// * Undirected graphs have a global property store.
-// * Global property stores are lists (for node-based edge stores) and
-// vectors (for vector edge stores).
-// * Edge descriptors are a triple: an unordered pair consisting of
-// vertex descriptors, and an a property descriptor.
-// * The property descriptor provide access to the properties of the
-// given edge. This would best be described as the edge property
-// accessors.
-// * If there are no properties, then the property store doesn't really
-// need to exist. We can just pretend to allocate them and return
-// an integer "pseudo descriptor".
-
-// Note that the graph interface will fail to compile if a mapped graph is
-// requested whose key and property types are the same.
-
#include "descriptor.hpp"
#include "undirected_vertex.hpp"
@@ -233,13 +217,28 @@
, _verts()
{ }
+/**
+ * Add a vertex to the graph with no or default properties, and return a
+ * descriptor to the vertex. Although supported for all adjacency lists, this
+ * function should not be used with graphs that have LabeledUniqueVertices
+ * as it will always return the same default-propertied vertex iterator.
+ */
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
undirected_graph<VP,EP,VS,ES>::add_vertex()
{
+ // BOOST_STATIC_ASSERT(!LabeledUniqueVertices<this_type>);
return _verts.add();
}
+/**
+ * Add a vertex to the graph with the given properties, and return a descriptor
+ * to the added vertes. If the graph has LabeledUniqe vertices, and a vertex
+ * with the given properties already exists in the graph, then a new vertex
+ * is not added and returned descriptor refers to the existing vertex.
+ *
+ * @requires LabeledVertices<Graph>
+ */
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_properties const& vp)
@@ -251,7 +250,7 @@
* Add a new vertex with the given properties to the graph and map it to the
* given key.
*
- * @requires VertexMap<Graph>
+ * @requires MappedUniqueVertices<Graph>
*/
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
@@ -262,8 +261,6 @@
/**
* Find the vertex with the given properties, returning a descriptor to it.
- *
- * @requires LabeledUniqueVertex<Graph> ???
*/
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
@@ -275,8 +272,6 @@
/**
* Find the vertex with the given properties, returning a descriptor to it.
- *
- * @requires MappedUniqueVertex<Graph>
*/
template <BOOST_GRAPH_UG_PARAMS>
typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
@@ -317,10 +312,6 @@
/**
* Disconnect the vertex having the given properties from the graph.
- *
- * @requires UniqueLabeledVertex<Graph>
- *
- * @todo What does this do for multiset vertex stores.
*/
template <BOOST_GRAPH_UG_PARAMS>
void
@@ -332,10 +323,6 @@
/**
* Disconnect the vertex having the given key from the graph.
- *
- * @requires UniqueMappedVertex<Graph>
- *
- * @todo What does this do for multimap vertex stores.
*/
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-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -4,7 +4,6 @@
#include "incidence_iterator.hpp"
-
/**
* A vertex, at least for an undirected graph, is simply an repository
* for the vertex' properties and an interface for the its incidence
@@ -58,12 +57,12 @@
inline size_type degree() const
{ return _edges.size(); }
-
+
inline bool operator==(undirected_vertex const& x) const
{ return _props == x._props; }
inline bool operator!=(undirected_vertex const& x) const
- { return !this->operator==(x); }
+ { return !this->operator==(x); }
inline bool operator<(undirected_vertex const& x) const
{ return _props < x._props; }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-06-19 10:26:55 EDT (Thu, 19 Jun 2008)
@@ -31,11 +31,14 @@
struct store
{
typedef Vertex stored_vertex;
- typedef Alloc<stored_vertex> allocator_type;
- typedef vertex_vector_impl<stored_vertex, allocator_type> type;
+ typedef Alloc<stored_vertex> allocator;
+ typedef vertex_vector_impl<stored_vertex, allocator> type;
};
};
+/**
+ * The default vertex vector uses the standard allocator.
+ */
struct vertex_vector : basic_vertex_vector<std::allocator> { };
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