|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-06-17 20:03:16
Author: asutton
Date: 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
New Revision: 46466
URL: http://svn.boost.org/trac/boost/changeset/46466
Log:
Started building directed graph class.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (contents, props changed)
Properties modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/descriptor.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_iterator.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/none.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/ordered_pair.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/policy.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_index.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/traits.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/unordered_pair.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multimap.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multiset.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/demangle.hpp (props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test.cpp (props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 64 +++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp | 13 +++----
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp | 8 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp | 6 +++
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 4 +
6 files changed, 83 insertions(+), 13 deletions(-)
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,17 @@
+
+#ifndef DIRECTED_EDGE_HPP
+#define DIRECTED_EDGE_HPP
+
+#include "ordered_pair.hpp"
+
+/**
+ * A directed edge represents and edge within directed.
+ */
+template <typename SourceDesc, typename TargetDesc>
+class directed_edge
+{
+public:
+};
+
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,133 @@
+
+#ifndef DIRECTED_GRAPH_HPP
+#define DIRECTED_GRAPH_HPP
+
+// Notes on directed graphs... Unlike undirected 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.
+
+// To differentiate from the BGL, which separates the basic concepts of half
+// and fully directed graphs, this type implements a fully directed (or
+// bidirectional) graph. If you really want a half directed or semidirected
+// graph, you can roll your own. This is analagous to the list/slist data
+// structures in the std library.
+
+#include "none.hpp"
+
+#include "descriptor.hpp"
+
+#include "directed_vertex.hpp"
+#include "vertex_iterator.hpp"
+#include "vertex_vector.hpp"
+
+#include "directed_edge.hpp"
+#include "edge_vector.hpp"
+
+#include "adjacency_iterator.hpp"
+
+template <
+ typename VertexProps,
+ typename EdgeProps,
+ typename VertexStore,
+ typename EdgeStore>
+class directed_graph
+{
+ typedef directed_graph<VertexProps, EdgeProps, VertexStore, EdgeStore> this_type;
+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.
+ 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;
+
+ // Generate the vertex type over the vertex properties, and in/out stores.
+ // 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;
+
+ // 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.
+ */
+ //@{
+ vertex_descriptor add_vertex();
+ vertex_descriptor add_vertex(vertex_properties const&);
+ vertex_descriptor add_vertex(vertex_key const&, vertex_properties const&);
+ //@}
+
+private:
+ vertex_store _verts;
+};
+
+#define BOOST_GRAPH_DG_PARAMS \
+ typename VP, typename EP, typename VS, typename ES
+
+template <BOOST_GRAPH_DG_PARAMS>
+directed_graph<VP,EP,VS,ES>::directed_graph()
+ : _verts()
+{ }
+
+/**
+ * Add a vertex to the graph with no or default graph properties. Return a
+ * descriptor to the vertex being returned.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
+directed_graph<VP,EP,VS,ES>::add_vertex()
+{
+ 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
+ * added and the descriptor for the existing vertex is returned.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
+directed_graph<VP,EP,VS,ES>::add_vertex(vertex_properties const& vp)
+{
+ return _verts.add(vp);
+}
+
+/**
+ * Add a vertex to the graph that is identified by the given key and with the
+ * given properties. If the key identifies a vertex already in the graph, do
+ * not add a new vertex and return a descriptor to the existing one.
+ */
+template <BOOST_GRAPH_DG_PARAMS>
+typename directed_graph<VP,EP,VS,ES>::vertex_descriptor
+directed_graph<VP,EP,VS,ES>::add_vertex(vertex_key const& k, vertex_properties const& vp)
+{
+ return _verts.add(k, vp);
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,73 @@
+
+#ifndef DIRECTED_VERTEX_HPP
+#define DIRECTED_VERTEX_HPP
+
+/**
+ * A directed vertex provides storage for both outgoing edges and in edges.
+ * Each of these stores are parameterizable, although they should generally
+ * share the same underlying data structure (e.g., vector, list, or set).
+ */
+template <typename VertexProps, typename OutStore, typename InStore>
+class directed_vertex
+{
+ typedef OutStore out_store;
+ typedef InStore in_store;
+public:
+ typedef VertexProps vertex_properties;
+ typedef typename out_store::vertex_descriptor vertex_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);
+
+ inline vertex_properties& properties();
+ inline vertex_properties const& properties() const;
+
+ /** @name Out Edges */
+ //@{
+ inline out_iterator begin_out() const
+ { return _out.begin(); }
+
+ 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(); }
+
+ inline in_size_type in_degree() const
+ { return _in.size(); }
+ //@}
+
+ /** @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); }
+
+ inline bool operator<(directed_vertex const& x) const
+ { return _props < x._props; }
+ //@}
+
+private:
+ vertex_properties _props;
+ out_store _out;
+ in_store _in;
+};
+
+#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-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -4,6 +4,8 @@
#include "property_vector.hpp"
#include "incidence_vector.hpp"
+#include "out_vector.hpp"
+#include "in_vector.hpp"
// What's in an edge vector? Basically, an edge vector has to specify
// the type of property storage and the type of incidence storage. What
@@ -12,26 +14,86 @@
// 2. Allocator for the property store
// 3. Allocator for the incidence store
+// How does this generalize for directed graphs? Well... It would essentially
+// rely on variadic templates - or rather variadic template templates. The
+// goal would be to write something like: edge_vector<A, B, C> where A, B, and
+// C are actually interpreted by the callers of the metafunctions - it ain't
+// pretty, but it may actually work.
+
+namespace undirected
+{
+
+/**
+ * The basic_edge_vector is the outer part of the metafunctions that generate
+ * types for adjacency lists.
+ */
template <
template <typename> class IncAlloc,
template <typename> class PropAlloc>
struct basic_edge_vector
{
+ // The property store metafunction generates the type of vector used to
+ // store global properties for undirected graphs.
template <typename EdgeProps>
struct property_store
{
typedef property_vector<EdgeProps, PropAlloc<EdgeProps> > type;
};
+ // The incidence store metafunction generates the type of vector used to
+ // store edges incident to the an undirected vertex.
template <typename VertexDesc, typename PropDesc>
struct incidence_store
{
typedef std::pair<VertexDesc, PropDesc> incidence_pair;
- typedef incidence_vector<incidence_pair, IncAlloc<incidence_pair> > type;
+ typedef IncAlloc<incidence_pair> incidence_allocator;
+ typedef incidence_vector<incidence_pair, incidence_allocator> type;
+ };
+
+};
+
+/**
+ * The default edge vector is a basic edge vector that uses the standard
+ * allocators for both the property store and the incidence store.
+ */
+struct edge_vector : basic_edge_vector<std::allocator, std::allocator> { };
+
+} // namespace undirected
+
+namespace directed
+{
+
+template <
+ template <typename> class OutAlloc,
+ template <typename> class InAlloc>
+struct basic_edge_vector
+{
+ // The out store metafunction generates the type of vector used to store
+ // out edges of a vertex in a directed graph.
+ template <typename VertexDesc, typename Props>
+ struct out_store
+ {
+ typedef std::pair<VertexDesc, Props> out_pair;
+ typedef OutAlloc<out_pair> out_allocator;
+ typedef out_vector<out_pair, out_allocator> type;
+ };
+
+ // 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>
+ struct in_store
+ {
+ typedef std::pair<VertexDesc, Props*> in_pair;
+ typedef InAlloc<in_pair> in_allocator;
+ typedef in_vector<in_pair, in_allocator> type;
};
};
struct edge_vector : basic_edge_vector<std::allocator, std::allocator> { };
+} // namespace directed
+
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,13 @@
+
+#ifndef IN_VECTOR_HPP
+#define IN_VECTOR_HPP
+
+template <typename Edge, typename Allocator>
+class in_vector
+{
+public:
+ typedef none const_iterator;
+ typedef std::size_t size_type;
+};
+
+#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-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -13,14 +13,14 @@
* This type allows constant-time edge addition and a linear search. Removal
* is not supported.
*/
-template <typename IncEdge, typename Alloc>
+template <typename Edge, typename Alloc>
class incidence_vector
{
- typedef std::vector<IncEdge, Alloc> store_type;
+ typedef std::vector<Edge, Alloc> store_type;
public:
- typedef IncEdge incidence_pair;
- typedef typename IncEdge::first_type vertex_descriptor;
- typedef typename IncEdge::second_type property_descriptor;
+ typedef Edge incidence_pair;
+ typedef typename Edge::first_type vertex_descriptor;
+ typedef typename Edge::second_type property_descriptor;
typedef typename store_type::iterator iterator;
typedef typename store_type::const_iterator const_iterator;
@@ -29,9 +29,8 @@
// Constructors
incidence_vector();
- void add(incidence_pair);
-
std::pair<const_iterator, bool> allow(vertex_descriptor) const;
+ void add(incidence_pair);
iterator find(incidence_pair);
const_iterator find(incidence_pair) const;
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,36 @@
+
+#ifndef OUT_VECTOR_HPP
+#define OUT_VECTOR_HPP
+
+#include <vector>
+
+/**
+ * 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.
+ *
+ * Here, the edge is required to be a pair containing a vertex descriptor and a
+ * edge property.
+ */
+template <typename Edge, typename Alloc>
+class out_vector
+{
+ typedef std::vector<Edge, Alloc> store_type;
+public:
+ 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;
+
+ inline out_vector()
+ : _store()
+ { }
+
+private:
+ store_type _store;
+};
+
+#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-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -81,15 +81,15 @@
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 key_type;
// Because edges are "distributed" among vertices, the edge iterators are
// somewhat special.
typedef basic_edge_iterator<this_type> edge_iterator;
typedef std::pair<edge_iterator, edge_iterator> edge_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 key_type;
// Constructors
undirected_graph();
@@ -104,7 +104,7 @@
vertex_descriptor add_vertex(key_type const&, vertex_properties const&);
void disconnect_vertex(vertex_descriptor);
void remove_vertex(vertex_descriptor);
- //@{
+ //@}
/** @name Edge Set
* These functions operate on the edges of the graph. This functions
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-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -7,12 +7,18 @@
// Forward declarations
template <typename V, typename A> struct vertex_vector_impl;
+/**
+ *
+ */
template <template <typename> class Allocator>
struct basic_vertex_vector
{
typedef none key_type;
typedef std::size_t descriptor_type;
+ // The store metafunction generates the type used to store vertices in
+ // either a directed or undirected graph. This metafunction takes the
+ // fully configured vertex type as a type parameter.
template <typename Vertex>
struct store
{
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -1,2 +1,3 @@
exe un : un.cpp : <include>../../ <include>/usr/local/include ;
+exe di : di.cpp : <include>../../ <include>/usr/local/include ;
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -0,0 +1,16 @@
+
+#include <iostream>
+
+#include <boost/graphs/directed_graph.hpp>
+
+using namespace std;
+using namespace boost;
+namespace d = directed;
+
+int main()
+{
+ typedef directed_graph<int, int, vertex_vector, d::edge_vector> Graph;
+ Graph g;
+
+ return 0;
+}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp 2008-06-17 20:03:15 EDT (Tue, 17 Jun 2008)
@@ -11,6 +11,8 @@
using namespace std;
using namespace boost;
+namespace u = undirected;
+
typedef int City;
typedef int Road;
@@ -82,7 +84,7 @@
void vec_vec()
{
- typedef undirected_graph<City, Road, vertex_vector, edge_vector> Graph;
+ typedef undirected_graph<City, Road, vertex_vector, u::edge_vector> Graph;
test_add_vertices<Graph>();
test_make_simple_triangle<Graph>();
}
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