|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-09 12:51:15
Author: asutton
Date: 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
New Revision: 47271
URL: http://svn.boost.org/trac/boost/changeset/47271
Log:
Rewrote tons and tons of code to make the directed graph work with the directed
types class and the new iterators library. Doesn't really do anything just yet.
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/blob.hpp | 8 ++
sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp | 7 +
sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp | 15 ++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 147 +++++++++++++++++----------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 104 +++++++++------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp | 60 ++++++++++++++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 128 ++++------------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp | 69 +++++++-----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp | 3
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp | 67 +++++++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp | 23 ++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp | 18 ++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp | 23 ++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp | 18 ++++
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp | 3
sandbox/SOC/2008/graphs/trunk/boost/unordered_pair.hpp | 9 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/README | 12 ++
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 24 +++--
sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp | 6
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 4
sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp | 1
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 61 +++++++++++++---
30 files changed, 419 insertions(+), 407 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/blob.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/blob.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/blob.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -85,6 +85,14 @@
{ return std::memcmp(mem, x.mem, N) >= 0; }
//@}
+ inline void swap(blob& x)
+ {
+ unsigned char tmp[N];
+ std::memcpy(tmp, mem, N);
+ std::memcpy(mem, x.mem, N);
+ std::memcpy(x.mem, tmp, N);
+ }
+
mutable unsigned char mem[N];
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/index_descriptor.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -37,10 +37,10 @@
/** @name Equality Comparable */
//@{
- inline bool operator==(index_descriptor const& x)
+ inline bool operator==(index_descriptor const& x) const
{ return value == x.value; }
- inline bool operator!=(index_descriptor const& x)
+ inline bool operator!=(index_descriptor const& x) const
{ return value != x.value; }
//@}
@@ -59,6 +59,9 @@
{ return value >= x.value; }
//@}
+ inline void swap(index_descriptor& x)
+ { std::swap(value, x); }
+
template <typename Container>
inline typename Container::iterator get(Container& c) const
{ return std::next(c.begin(), value); }
Modified: sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/descriptors/node_descriptor.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -37,28 +37,31 @@
/** @name Equality Comparable */
//@{
- inline bool operator==(node_descriptor const& x)
+ inline bool operator==(node_descriptor const& x) const
{ return value == x.value; }
- inline bool operator!=(node_descriptor const& x)
+ inline bool operator!=(node_descriptor const& x) const
{ return value != x.value; }
//@}
/** @name Less Than Comparable */
//@{
- inline bool operator<(node_descriptor const& x)
+ inline bool operator<(node_descriptor const& x) const
{ return value < x.value; }
- inline bool operator>(node_descriptor const& x)
+ inline bool operator>(node_descriptor const& x) const
{ return value > x.value; }
- inline bool operator<=(node_descriptor const& x)
+ inline bool operator<=(node_descriptor const& x) const
{ return value <= x.value; }
- inline bool operator>=(node_descriptor const& x)
+ inline bool operator>=(node_descriptor const& x) const
{ return value >= x.value; }
//@}
+ inline void swap(node_descriptor& x)
+ { value.swap(x.value) ;}
+
template <typename Container>
inline typename Container::iterator get(Container& c) const
{ return value.get<typename Container::iterator>(); }
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -11,85 +11,68 @@
* @param VertexDesc A vertex descriptor
* @param OutDesc An out edge descriptor.
*/
-template <typename OutIter, typename InIter>
+template <typename VertexDesc, typename OutDesc>
class directed_edge
{
- template <typename O, typename I> friend bool operator==(directed_edge<O,I> const&, directed_edge<O,I> const&);
- template <typename O, typename I> friend bool operator<(directed_edge<O,I> const&, directed_edge<O,I> const&);
public:
- typedef OutIter out_iterator;
- typedef InIter in_iterator;
- typedef typename OutIter::value_type out_tuple;
- typedef typename out_tuple::first_type vertex_descriptor;
- typedef typename out_tuple::second_type edge_properties;
+ typedef VertexDesc vertex_descriptor;
+ typedef OutDesc out_descriptor;
+ typedef std::pair<vertex_descriptor, vertex_descriptor> edge_pair;
/** @name Constructors */
//@{
inline directed_edge()
- : _src()
- , _out()
+ : ends(), out()
{ }
- inline directed_edge(vertex_descriptor v, OutIter o)
- : _src(v)
- , _out(o)
+ inline directed_edge(vertex_descriptor u, vertex_descriptor v, out_descriptor o)
+ : ends(u, v), out(o)
{ }
- //@}
- /**
- * Return a value that uniquely describes the edge. This is basically going
- * to be the address of the property. Note that directed graphs can't use
- * indexed exterior edge properties because there's no method for maintaining
- * a global edge index.
- */
- inline edge_properties* get() const
- { return &properties(); }
+ inline directed_edge(std::pair<vertex_descriptor, vertex_descriptor> x, out_descriptor o)
+ : ends(x), out(o)
+ { }
+ //@}
- /** Return the source of the edge. */
+ /** Return the source vertex descriptor. */
inline vertex_descriptor source() const
- { return _src; }
+ { return ends.first; }
- /** Return the target of the edge. */
+ /** Return the target vertex descriptor. */
inline vertex_descriptor target() const
- { return _out->first; }
+ { return ends.second; }
- /** Return the iterator to the out edge. */
- inline OutIter out_edge() const
- { return _out; }
-
- inline InIter in_edge() const
- { return (*_out).third.template get<InIter>(); }
-
- /** @name Property Accessors
- * Return the properties associated with the edge.
- */
+ /** Return the descriptor to the out edge, where the property is stored. */
+ inline out_descriptor out_edge() const
+ { return out; }
+
+ /** @name Equality Comparable */
//@{
- inline edge_properties& properties()
- { return (*_out).second; }
+ inline bool operator==(directed_edge const& x) const
+ { return (ends == x.ends) && (out = x.out); }
- inline edge_properties const& properties() const
- { return (*_out).second; }
+ inline bool operator!=(directed_edge const& x) const
+ { return !operator==(x); }
//@}
-private:
- vertex_descriptor _src;
- OutIter _out;
-};
+ /** @name Less Than Comparable */
+ //@{
+ inline bool operator<(directed_edge const& x) const
+ { return std::make_pair(ends, out) < std::make_pair(x.ends < x.out); }
-template <typename O, typename I>
-inline bool
-operator==(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
-{ return (x._src == y._src) && (x._out == y._out); }
+ inline bool operator>(directed_edge const& x) const
+ { return x.operator<(*this); }
-template <typename O, typename I>
-inline bool
-operator!=(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
-{ return !(x == y); }
+ inline bool operator<=(directed_edge const& x) const
+ { return !x.operator<(*this); }
-template <typename O, typename I>
-inline bool
-operator<(directed_edge<O,I> const& x, directed_edge<O,I> const& y)
-{ return std::make_pair(x._src, x._out) < std::make_pair(y._src, y._out); }
+ inline bool operator>=(directed_edge const& x) const
+ { return !operator<(x); }
+ //@}
+
+ edge_pair ends;
+ out_descriptor out;
+};
template <typename O, typename I>
std::ostream& operator<<(std::ostream& os, const directed_edge<O,I>& e)
@@ -100,27 +83,28 @@
* edges of a directed graph. This is essenitally done by iterating over the
* out edges of each vertex in the order in which they were added to the graph.
*/
-template <typename Graph>
+template <typename VertexStore, typename Edge>
struct directed_edge_iterator
{
- typedef typename Graph::vertex_iterator vertex_iterator;
- typedef typename Graph::out_edge_iterator edge_iterator;
+ typedef VertexStore vertex_store;
+ typedef typename vertex_store::iterator vertex_iterator;
+ typedef typename vertex_store::vertex_type vertex_type;
+ typedef typename vertex_type::out_iterator edge_iterator;
typedef std::forward_iterator_tag iterator_category;
- typedef std::size_t difference_type;
-
- typedef typename Graph::edge_descriptor value_type;
+ typedef typename vertex_iterator::diffeerence_type difference_type;
+ typedef Edge value_type;
typedef value_type reference;
typedef value_type pointer;
// Used to construct the end iterator.
- directed_edge_iterator(Graph const& g, vertex_iterator v)
- : graph(g), vert(v), edge()
+ directed_edge_iterator(vertex_store& store)
+ : verts(&store), vert(store.end_vertices()), edge()
{ }
- // Typically used to construct the begin iterator.
- directed_edge_iterator(Graph const& g, vertex_iterator v, edge_iterator e)
- : graph(g), vert(v), edge(e)
+ // Used to cosntruct the begin iterator.
+ directed_edge_iterator(vertex_store& store, edge_iterator e)
+ : verts(&store), vert(store.begin_vertices()), edge(e)
{ }
inline directed_edge_iterator& operator++()
@@ -128,12 +112,12 @@
// If we're not done, increment the current edge. If that increment
// pushes the edge iterator off the vertex, move to the next vertex
// and reset the edge iterator.
- if(vert != graph.end_vertices()) {
+ if(vert != verts->end_vertices()) {
++edge;
- if(edge == graph.end_out_edges(*vert)) {
+ if(edge == verts->vertex(*vert).end_out()) {
++vert;
- if(vert != graph.end_vertices()) {
- edge = graph.begin_out_edges(*vert);
+ if(vert != verts->end_vertices()) {
+ edge = vert->vertex(*vert).begin_out();
}
else {
edge = edge_iterator();
@@ -143,22 +127,21 @@
return *this;
}
+ /** @name Equality Comparable */
+ //@{
+ inline bool operator==(directed_edge_iterator const& x)
+ { return edge == x.edge; }
+
+ inline bool operator!=(directed_edge_iterator const& x)
+ { return edge != x.edge; }
+ //@}
+
inline reference operator*() const
{ return *edge; }
- Graph const& graph;
+ vertex_store* verts;
vertex_iterator vert;
edge_iterator edge;
};
-template <typename Graph>
-inline bool
-operator==(directed_edge_iterator<Graph> const& a, directed_edge_iterator<Graph> const& b)
-{ return (a.vert == b.vert) && (a.edge == b.edge); }
-
-template <typename Graph>
-inline bool
-operator!=(directed_edge_iterator<Graph> const& a, directed_edge_iterator<Graph> const& b)
-{ return !(a == b); }
-
#endif
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -2,8 +2,6 @@
#ifndef DIRECTED_GRAPH_HPP
#define DIRECTED_GRAPH_HPP
-#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
@@ -30,23 +28,8 @@
// order to provide quick access to it "other half", it needs a reference to
// the out edge (which could be implemented as an iterator of some kind).
-#include "none.hpp"
-
-#include "directed_vertex.hpp"
-#include "vertex_vector.hpp"
-#include "vertex_list.hpp"
-#include "vertex_set.hpp"
-#include "vertex_map.hpp"
-
-#include "directed_edge.hpp"
-#include "edge_vector.hpp"
-#include "edge_list.hpp"
-#include "edge_set.hpp"
-
-#include "out_iterator.hpp"
-#include "in_iterator.hpp"
-
-#include "adjacency_iterator.hpp"
+#include <boost/none.hpp>
+#include <boost/graphs/directed_types.hpp>
template <
typename VertexProps,
@@ -55,6 +38,7 @@
typename EdgeStore>
class directed_graph
{
+ typedef directed_types<VertexProps, EdgeProps, VertexStore, EdgeStore> types;
typedef directed_graph<VertexProps, EdgeProps, VertexStore, EdgeStore> this_type;
public:
typedef VertexProps vertex_properties;
@@ -62,55 +46,39 @@
typedef VertexStore vertex_store_selector;
typedef EdgeStore edge_store_selector;
- // 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 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;
- typedef typename EdgeStore::template in_store<vertex_descriptor>::type in_edge_store;
-
- // We can now generate the edge descriptor.
- typedef directed_edge<typename out_edge_store::iterator, typename in_edge_store::iterator> edge_descriptor;
-
- // 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;
- 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;
-
- // Additional iterator types. I'm cheating here and using the edge
- // descriptor to piggyback type information to these iterators. It kinda
- // works.
- typedef directed_edge_iterator<this_type> edge_iterator;
- typedef std::pair<edge_iterator, edge_iterator> edge_range;
- typedef basic_out_iterator<edge_descriptor> out_edge_iterator;
- typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
- typedef basic_in_iterator<edge_descriptor> in_edge_iterator;
- typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
-
- // This just makes sense.
- typedef std::size_t edges_size_type;
-
- // 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;
+ // Underlying stores
+ typedef typename types::out_store out_store;
+ typedef typename types::in_store in_store;
+ typedef typename types::vertex_store vertex_store;
+ typedef typename types::vertex_key vertex_key;
+ typedef typename types::vertex_type vertex_type;
+
+ // Vertex/Property descriptors
+ typedef typename types::vertex_descriptor vertex_descriptor;
+ typedef typename types::edge_descriptor edge_descriptor;
+ typedef typename types::out_descriptor out_descriptor;
+ typedef typename types::in_descriptor in_descriptor;
+
+ // Iterators and ranges
+ typedef typename types::vertex_iterator vertex_iterator;
+ typedef typename types::vertex_range vertex_range;
+ typedef typename types::edge_iterator edge_iterator;
+ typedef typename types::edge_range edge_range;
+ typedef typename types::out_edge_iterator out_edge_iterator;
+ typedef typename types::out_edge_range out_edge_range;
+ typedef typename types::in_edge_iterator in_edge_iterator;
+ typedef typename types::in_edge_range in_edge_range;
+ typedef typename types::incident_edge_iterator incident_edge_iterator;
+ typedef typename types::incident_edge_range incident_edge_range;
+ typedef typename types::adjacent_vertex_iterator adjacent_vertex_iterator;
+ typedef typename types::adjacent_vertex_range adjacent_vertex_range;
+
+ // Sizes for vertices, and degree.
+ typedef typename types::vertices_size_type vertices_size_type;
+ typedef typename types::edges_size_type edges_size_type;
+ typedef typename types::out_edges_size_type out_edges_size_type;
+ typedef typename types::in_edges_size_type in_edges_size_type;
+ typedef typename types::incident_edges_size_type incident_edges_size_type;
// Constructors
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -2,6 +2,34 @@
#ifndef DIRECTED_TYPES_HPP
#define DIRECTED_TYPES_HPP
+// Vertex stores
+#include <boost/graphs/vertex_vector.hpp>
+#include <boost/graphs/vertex_list.hpp>
+#include <boost/graphs/vertex_set.hpp>
+#include <boost/graphs/vertex_map.hpp>
+
+// Edge stores
+#include <boost/graphs/edge_vector.hpp>
+#include <boost/graphs/edge_list.hpp>
+#include <boost/graphs/edge_set.hpp>
+
+// Edges store components
+#include <boost/graphs/out_vector.hpp>
+#include <boost/graphs/out_list.hpp>
+#include <boost/graphs/out_set.hpp>
+#include <boost/graphs/out_iterator.hpp>
+#include <boost/graphs/in_vector.hpp>
+#include <boost/graphs/in_list.hpp>
+#include <boost/graphs/in_set.hpp>
+#include <boost/graphs/in_iterator.hpp>
+
+// Vertex and Edge components
+#include <boost/graphs/directed_vertex.hpp>
+#include <boost/graphs/directed_edge.hpp>
+
+// Adjacency components
+#include <boost/graphs/adjacency_iterator.hpp>
+
/**
* This class is a metafunction that generates all of the types needed to
* implement a directed graph.
@@ -9,6 +37,38 @@
template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
class directed_types
{
+ // Start by generating all of the descriptors.
+ typedef typename VertexStore::vertex_descriptor vertex_descriptor;
+ typedef typename EdgeStore::out_descriptor out_descriptor;
+ typedef typename EdgeStore::in_descriptor in_descriptor;
+
+ // Generate edges. Iterators are last.
+ typedef directed_edge<out_descriptor, in_descriptor> edge_descriptor;
+
+ // Generate the out store and related types
+ typedef typename EdgeStore::template out_store<vertex_descriptor, EdgeProps> out_store;
+ typedef typename out_store::size_type out_edges_size_type;
+ typedef typename out_store::size_type edges_size_type;
+ typedef basic_out_iterator<out_store, edge_descriptor> out_edge_iterator;
+ typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
+
+ // Generate the in store and related types
+ typedef typename EdgeStore::template in_store<vertex_descriptor> in_store;
+ typedef typename in_store::size_type in_edge_size_type;
+ typedef basic_in_iterator<typename in_store::iterator, edge_descriptor> in_edge_iterator;
+ typedef std::pair<in_edge_iterator, in_edge_iterator> in_edge_range;
+
+ // Generate the vertex, its store, and related types.
+ typedef directed_vertex<VertexProps, out_store, in_store> vertex_type;
+ 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;
+ typedef typename vertex_store::vertex_key vertex_key;
+
+ // Generate the edge iterators as far back as possible...
+ typedef directed_edge_iterator<vertex_store, edge_descriptor> edge_iterator;
+ typedef std::pair<edge_iterator, edge_iterator> edge_range;
};
#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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -2,9 +2,6 @@
#ifndef DIRECTED_VERTEX_HPP
#define DIRECTED_VERTEX_HPP
-#include "placeholder.hpp"
-#include "directed_edge.hpp"
-
/**
* A directed vertex provides storage for both outgoing edges and in edges.
* Each of these stores are parameterizable, although they should generally
@@ -17,46 +14,43 @@
typedef InStore in_store;
public:
typedef VertexProps vertex_properties;
- typedef typename out_store::vertex_descriptor vertex_descriptor;
-
- typedef typename OutStore::edge_properties edge_properties;
+ typedef typename out_store::vertex_descriptor vertex_descriptor;
+ typedef typename out_store::edge_properties edge_properties;
+ typedef typename out_store::out_descriptor out_descriptor;
typedef typename out_store::iterator out_iterator;
typedef typename out_store::size_type out_size_type;
+ typedef typename in_store::in_descriptor in_descriptor;
typedef typename in_store::iterator in_iterator;
typedef typename in_store::size_type in_size_type;
typedef out_size_type incident_size_type;
- typedef directed_edge<out_iterator, in_iterator> edge_descriptor;
-
/** @name Constructors */
//@{
inline directed_vertex()
- : _props()
- , _out()
- , _in()
+ : _props(), _out(), _in()
{ }
inline directed_vertex(vertex_properties const& vp)
- : _props(vp)
- , _out()
- , _in()
+ : _props(vp), _out(), _in()
{ }
//@}
- std::pair<out_iterator, bool> allow(vertex_descriptor) const;
-
- out_iterator connect_target(vertex_descriptor, edge_properties const&);
- in_iterator connect_source(vertex_descriptor);
- static edge_descriptor bind_connection(out_iterator, in_iterator);
+ /** @name Edge Connection and Disconnection
+ * These functions provide an interface to the in and out stores of the
+ * vertex.
+ */
+ //@{
+ insertion_result<out_descriptor> connect_target(vertex_descriptor v, edge_properties const& ep)
+ { return _out.add(v, ep); }
- void disconnect_target(edge_descriptor);
- void disconnect_source(edge_descriptor);
+ insertion_result<in_descriptor> connect_source(vertex_descriptor v, out_descriptor o)
+ { return _in.add(v, o); }
- out_iterator disconnect_target(out_iterator);
- in_iterator disconnect_source(in_iterator);
+ void bind_target(out_descriptor o, in_descriptor i)
+ { _out.bind(o, i); }
/** @name Property Accessors */
//@{
@@ -130,93 +124,5 @@
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_iterator
-directed_vertex<V,O,I>::connect_target(vertex_descriptor v, edge_properties const& ep)
-{
- return _out.add(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>
-typename directed_vertex<V,O,I>::in_iterator
-directed_vertex<V,O,I>::connect_source(vertex_descriptor v)
-{
- return _in.add(v);
-}
-
-/**
- * Having added the edge stubs, bind them together and return a descriptor over
- * the edge. This is a static method because it doesn't pertain to single
- * object.
- */
-template <typename V, typename O, typename I>
-typename directed_vertex<V,O,I>::edge_descriptor
-directed_vertex<V,O,I>::bind_connection(out_iterator i, in_iterator j)
-{
- i->third.put(j);
- j->second.put(i);
- return edge_descriptor(j->first, i);
-}
-
-/**
- * Disconnect this vertex from its target, removing the outgoing edge.
- */
-template <typename V, typename O, typename I>
-void
-directed_vertex<V,O,I>::disconnect_target(edge_descriptor e)
-{
- _out.remove(e.out_edge());
-}
-
-/**
- * Disconnect this vertex from its source, removing the incoming edge.
- */
-template <typename V, typename O, typename I>
-void
-directed_vertex<V,O,I>::disconnect_source(edge_descriptor e)
-{
- // Get the input iterator from the edge.
- out_iterator o = e.out_edge();
- in_iterator i = (*o).third.template get<in_iterator>();
- _in.remove(i);
-}
-
-template <typename V, typename O, typename I>
-typename directed_vertex<V,O,I>::out_iterator
-directed_vertex<V,O,I>::disconnect_target(out_iterator i)
-{
- return _out.remove(i);
-}
-
-template <typename V, typename O, typename I>
-typename directed_vertex<V,O,I>::in_iterator
-directed_vertex<V,O,I>::disconnect_source(in_iterator i)
-{
- return _in.remove(i);
-}
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -66,7 +66,7 @@
template <typename VertexDesc, typename EdgeProps>
struct out_store
{
- typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
+ typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
typedef FirstAlloc<edge> allocator;
typedef out_list<edge, allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -74,7 +74,7 @@
template <typename VertexDesc, typename EdgeProps>
struct out_store
{
- typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
+ typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
typedef Compare<VertexDesc> compare;
typedef FirstAlloc<edge> allocator;
typedef out_set<edge, compare, allocator> type;
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -80,7 +80,7 @@
template <typename VertexDesc, typename EdgeProps>
struct out_store
{
- typedef triple<VertexDesc, EdgeProps, in_descriptor> edge;
+ typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
typedef FirstAlloc<edge> allocator;
typedef out_vector<edge, allocator> type;
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -9,74 +9,57 @@
* of the out edge iterator since in edges contain placeheld references to
* out edges.
*/
-template <typename Edge>
+template <typename Iter, typename Edge>
class basic_in_iterator
{
- typedef typename Edge::in_iterator base_iterator;
- typedef typename Edge::out_iterator out_iterator;
- typedef typename out_iterator::value_type out_tuple;
public:
- typedef typename out_tuple::first_type vertex_descriptor;
- typedef typename out_tuple::second_type edge_properties;
-
- // This is a little misleading. This iterator can be either bidi or random.
- // Clearly, we're going to be constraining members using some concept stuff
- // when it becomes available.
- typedef typename base_iterator::iterator_category iterator_category;
- typedef typename base_iterator::difference_type difference_type;
+ typedef Iter iterator;
+ typedef typename Iter::value_type base_value_type;
+ typedef typename base_value_type::first_type vertex_descriptor;
+ typedef typename base_value_type::second_type out_descriptor;
+ typedef typename iterator::iterator_category iterator_category;
+ typedef typename iterator::difference_type difference_type;
typedef Edge value_type;
typedef value_type reference;
typedef value_type pointer;
+ /** @name Constructors */
+ //@{
inline basic_in_iterator()
- : _base(), _iter()
- { }
-
- inline basic_in_iterator(basic_in_iterator const& x)
- : _base(x._base), _iter(x._iter)
+ : tgt(), iter()
{ }
- inline basic_in_iterator(vertex_descriptor v, base_iterator const& x)
- : _base(v), _iter(x)
+ inline basic_in_iterator(vertex_descriptor v, iterator x)
+ : tgt(v), iter(x)
{ }
+ //@}
- /**
- * Extended iterator functionality. Return the source vertex of the
- * iterator. This is the vertex for which the iterator was originally
- * created.
- */
+ /** Return the source vertex of the iterated edge. */
vertex_descriptor source() const
- { return _base; }
+ { return iter->first; }
- /**
- * Extended iterator functionality. Return the opposite vertex of the
- * edge indicated by the iterator. This is mostly provided for use by
- * the adjacency iterator.
- */
- vertex_descriptor opposite() const
- { return _iter->first; }
+ /** Return the target vertex of the iterated edge. */
+ vertex_descriptor target() const
+ { return tgt; }
inline basic_in_iterator& operator++()
- { ++_iter; return *this; }
+ { ++iter; return *this; }
inline basic_in_iterator& operator--()
- { --_iter; return *this; }
+ { --iter; return *this; }
inline bool operator==(basic_in_iterator const& x) const
- { return (_base == x._base) && (_iter == x._iter); }
+ { return iter == x.iter; }
inline bool operator!=(basic_in_iterator const& x) const
- { return !this->operator==(x); }
+ { return iter != x.iter; }
inline reference operator*() const
- {
- return reference(_iter->first, _iter->second.template get<out_iterator>());
- }
-
-private:
- vertex_descriptor _base;
- base_iterator _iter;
+ { return Edge(source(), target(), iter->second()); }
+
+ vertex_descriptor tgt;
+ iterator iter;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -12,7 +12,7 @@
* The in-edge list 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 Edge A pair describing a vertex descriptor and out edge descriptor.
* @param Alloc The allocator for edge pairs.
*/
template <typename Edge, typename Alloc>
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -12,7 +12,7 @@
* 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 Edge A pair describing a vertex descriptor and out edge descriptor.
* @param Alloc The allocator for edge pairs.
*/
template <typename Edge, typename Alloc>
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -34,8 +34,7 @@
: base(v), iter(x)
{ }
-
- /**
+ /**
* Extended iterator functionality. Return the source vertex of the
* iterator. This is the vertex for which the iterator was originally
* created.
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -7,72 +7,63 @@
* dereferenced will return an edge descriptor. The properties of the iterator
* are taken from the underlying store.
*/
-template <typename Edge>
+template <typename Store, typename Edge>
class basic_out_iterator
{
- typedef typename Edge::out_iterator base_iterator;
-public:
- typedef typename base_iterator::value_type out_tuple;
- typedef typename out_tuple::first_type vertex_descriptor;
- typedef typename out_tuple::second_type edge_properties;
+ typedef Store store_type;
+ typedef typename Store::iterator iterator;
+ typedef typename iterator::value_type base_value_type;
+ typedef typename base_value_type::first_type vertex_descriptor;
+ typedef typename base_value_type::second_type edge_pair;
+ typedef typename edge_pair::first_type edge_properties;
+ typedef typename edge_pair::second_type in_descriptor;
// This is a little misleading. This iterator can be either bidi or random.
// Clearly, we're going to be constraining members using some concept stuff
// when it becomes available.
- typedef typename base_iterator::iterator_category iterator_category;
- typedef typename base_iterator::difference_type difference_type;
-
+ typedef typename iterator::iterator_category iterator_category;
+ typedef typename iterator::difference_type difference_type;
typedef Edge value_type;
typedef value_type reference;
typedef value_type pointer;
inline basic_out_iterator()
- : _base(), _iter()
- { }
-
- inline basic_out_iterator(basic_out_iterator const& x)
- : _base(x._base), _iter(x._iter)
+ : src(), iter(), outs(0)
{ }
- inline basic_out_iterator(vertex_descriptor v, base_iterator const& x)
- : _base(v), _iter(x)
+ inline basic_out_iterator(vertex_descriptor v, iterator x, store_type& store)
+ : src(v), iter(x), outs(&store)
{ }
- /**
- * Extended iterator functionality. Return the source vertex of the
- * iterator. This is the vertex for which the iterator was originally
- * created.
- */
+ /** Return the source vertex of the iterated edge. */
vertex_descriptor source() const
- { return _base; }
+ { return src; }
- /**
- * Extended iterator functionality. Return the opposite vertex of the
- * edge indicated by the iterator. This is mostly provided for use by
- * the adjacency iterator.
- */
- vertex_descriptor opposite() const
- { return _iter->first; }
+ /** Return the target vertex of the iterated edge. */
+ vertex_descriptor target() const
+ { return iter->first; }
inline basic_out_iterator& operator++()
- { ++_iter; return *this; }
+ { ++iter; return *this; }
inline basic_out_iterator& operator--()
- { --_iter; return *this; }
+ { --iter; return *this; }
- // Iterators are equivalent if they reference the same edge.
+ /** @name Equality Comparable */
+ //@{
inline bool operator==(basic_out_iterator const& x) const
- { return operator*() == *x; }
+ { return iter == x.iter; }
inline bool operator!=(basic_out_iterator const& x) const
- { return !this->operator==(x); }
+ { return iter != x.iter; }
+ //@}
inline reference operator*() const
- { return reference(_base, _iter); }
+ { return Edge(source(), target(), outs->edge(iter)); }
-private:
- vertex_descriptor _base;
- base_iterator _iter;
+ vertex_descriptor src;
+ iterator iter;
+ store_type* outs;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -24,8 +24,9 @@
{
public:
typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type edge_properties;
- typedef typename Edge::third_type in_descriptor;
+ typedef typename Edge::second_type edge_pair;
+ typedef typename edge_pair::first_type edge_properties;
+ typedef typename edge_pair::second_type in_descriptor;
typedef std::list<Edge, Alloc> store_type;
typedef typename store_type::iterator iterator;
@@ -44,7 +45,7 @@
insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
{
++_size;
- iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
+ iterator i = _edges.insert(_edges.end(), std::make_pair(v, std::make_pair(ep, in_descriptor())));
return make_result(make_descriptor(_edges, i));
}
@@ -96,11 +97,23 @@
/** Bind the edge to the corresponding in edge descriptor. */
inline void bind(out_descriptor o, in_descriptor i)
- { make_iterator(_edges, o)->third = i; }
+ { make_iterator(_edges, o)->second.second = i; }
+
+ /** Return the target vertex of this edge. */
+ inline vertex_descriptor target(out_descriptor o) const
+ { return make_iterator(_edges, o)->first; }
/** Return the properties stored with this edge. */
inline edge_properties const& properties(out_descriptor o) const
- { return make_iterator(_edges, o)->second; }
+ { return make_iterator(_edges, o)->second.first; }
+
+ /** Return the in edge descriptor bound to this edge. */
+ inline in_descriptor reverse(out_descriptor o) const
+ { return make_iterator(_edges, o)->second.second; }
+
+ /** Return an out descriptor for the given iterator. */
+ inline out_descriptor edge(iterator i)
+ { return make_descriptor(_edges, i); }
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -29,11 +29,12 @@
{
public:
typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type edge_properties;
- typedef typename Edge::third_type in_descriptor;
+ typedef typename Edge::second_type edge_pair;
+ typedef typename edge_pair::first_type edge_properties;
+ typedef typename edge_pair::second_type in_descriptor;
// Reconstruct the edge triple into a key/value type thing for the map.
- typedef std::map<vertex_descriptor, std::pair<edge_properties, in_descriptor>, Compare, Alloc> store_type;
+ typedef std::map<vertex_descriptor, edge_pair, Compare, Alloc> store_type;
typedef typename store_type::iterator iterator;
typedef typename store_type::size_type size_type;
@@ -93,10 +94,21 @@
inline void bind(out_descriptor o, in_descriptor i)
{ make_iterator(_edges, o)->second.second = i; }
+ /** Return the target vertex of this edge. */
+ inline vertex_descriptor target(out_descriptor o) const
+ { return make_iterator(_edges, o)->first; }
+
/** Return the properties stored with this edge. */
inline edge_properties const& properties(out_descriptor o) const
{ return make_iterator(_edges, o)->second.first; }
+ /** Return the in edge descriptor bound to this edge. */
+ inline in_descriptor reverse(out_descriptor o) const
+ { return make_iterator(_edges, o)->second.second; }
+
+ /** Return an out descriptor for the given iterator. */
+ inline out_descriptor edge(iterator i)
+ { return make_descriptor(_edges, i); }
private:
mutable store_type _edges;
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -22,8 +22,9 @@
{
public:
typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type edge_properties;
- typedef typename Edge::third_type in_descriptor;
+ typedef typename Edge::second_type edge_pair;
+ typedef typename edge_pair::first_type edge_properties;
+ typedef typename edge_pair::second_type in_descriptor;
typedef std::vector<Edge, Alloc> store_type;
typedef typename store_type::iterator iterator;
@@ -42,7 +43,7 @@
*/
insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
{
- iterator i = _edges.insert(_edges.end(), make_triple(v, ep, in_descriptor()));
+ iterator i = _edges.insert(_edges.end(), std::make_pair(v, std::make_pair(ep, in_descriptor())));
return make_result(make_descriptor(_edges, i));
}
@@ -72,11 +73,23 @@
/** Bind the edge to the corresponding in edge descriptor. */
inline void bind(out_descriptor o, in_descriptor i)
- { make_iterator(_edges, o)->third = i; }
+ { make_iterator(_edges, o)->second.second = i; }
+
+ /** Return the target vertex of this edge. */
+ inline vertex_descriptor target(out_descriptor o) const
+ { return make_iterator(_edges, o)->first; }
/** Return the properties stored with this edge. */
inline edge_properties const& properties(out_descriptor o) const
- { return make_iterator(_edges, o)->second; }
+ { return make_iterator(_edges, o)->second.first; }
+
+ /** Return the in edge descriptor bound to this edge. */
+ inline in_descriptor reverse(out_descriptor o) const
+ { return make_iterator(_edges, o)->second.second; }
+
+ /** Return an out descriptor for the given iterator. */
+ inline out_descriptor edge(iterator i)
+ { return make_descriptor(_edges, i); }
private:
mutable store_type _edges;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -20,6 +20,8 @@
typedef PropDesc property_descriptor;
typedef unordered_pair<vertex_descriptor> edge_pair;
+ /** @name Constructors */
+ //@{
inline undirected_edge()
: ends(), prop()
{ }
@@ -35,6 +37,7 @@
inline undirected_edge(unordered_pair<vertex_descriptor, vertex_descriptor> const& e, property_descriptor p)
: ends(e), prop(p)
{ }
+ //@{
/** @name Descriptor-like Functions
* These allow you to treat the edge descriptor like a typical descriptor.
@@ -69,15 +72,30 @@
{ return make_unordered_pair(u, v) == ends; }
+ /** @name Equality Comparable */
+ //@{
inline bool operator==(undirected_edge const& x) const
{ return (ends == x.ends) && (prop == x.prop); }
inline bool operator!=(undirected_edge const& x) const
{ return !operator==(x); }
+ //@}
+ /** @name Less Than Comparable */
+ //@{
inline bool operator<(undirected_edge const& x) const
{ return std::make_pair(ends, prop) < std::make_pair(x.ends < x.prop); }
+ inline bool operator>(undirected_edge const& x) const
+ { return x.operator<(*this); }
+
+ inline bool operator<=(undirected_edge const& x) const
+ { return !x.operator<(*this); }
+
+ inline bool operator>=(undirected_edge const& x) const
+ { return !operator<(x); }
+ //@}
+
edge_pair ends;
property_descriptor prop;
};
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -42,8 +42,7 @@
/** @name Edge Connection and Disconnection
* These functions control how edges are added to and removed from the
- * vertex. The allow() function determines whether or not the edge
- * connection is allowed and/or already existing.
+ * vertex.
*/
//@{
inline insertion_result<incidence_descriptor> connect(vertex_descriptor v)
Modified: sandbox/SOC/2008/graphs/trunk/boost/unordered_pair.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/unordered_pair.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/unordered_pair.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -154,13 +154,14 @@
{ return unordered_pair<T>(f, s); }
/**
- * A swap-like sort function that will "unorder" two objects.
+ * A swap-like sort function that will "unorder" two objects using the given
+ * comparator, which defaults to std::less.
*/
-template <typename T>
+template <typename T, typename Comp = std::less<T>>
void
-reorder(T& a, T& b)
+reorder(T& a, T& b, Comp = Comp())
{
- unordered_pair<T> p(a, b);
+ unordered_pair<T, Comp> p(a, b);
a = p.first();
b = p.second();
}
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -9,7 +9,6 @@
;
-# exe di : di.cpp : <include>../../ <include>/usr/local/include ;
# exe set : set.cpp : <include>../../ <include>/usr/local/include ;
# exe map : map.cpp : <include>../../ <include>/usr/local/include ;
# exe props : props.cpp : <include>../../ <include>/usr/local/include ;
@@ -24,3 +23,4 @@
exe test_es : test_es.cpp : <include>../../ ;
exe un : un.cpp : <include>../../ ;
+exe di : di.cpp : <include>../../ ;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/README
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/README (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/README 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -1,4 +1,3 @@
-
Notes...
@@ -44,3 +43,14 @@
Probably for specific instances of templates, but probably not generically...
But then again. Who knows?
+Q: Why does the out store store values as a pair of pairs? Why not a triple or
+tuple?
+Easy... So the iterators, when dereferenced will always return a pair whose
+first value is a vertex descriptor and whose second value is another pair that
+contains an edge property and an in descriptor in its first and second slots.
+This is an artifact of using maps in the out set.
+
+Q: Why does the out iterator need a pointer back to the out store?
+Because you can't translate between the wrapped iterator and a descriptor to
+the wrapped iterator without a reference to the container. If descritpors were
+self-translating, this wouldn't be a problem...
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -3,11 +3,9 @@
#include <set>
#include <boost/assert.hpp>
-#include <boost/utility.hpp>
#include <boost/graphs/directed_graph.hpp>
-#include <boost/graphs/traits.hpp>
-#include "demangle.hpp"
+#include "typestr.hpp"
using namespace std;
using namespace boost;
@@ -22,11 +20,13 @@
template <typename Graph>
void print_types(const Graph&)
{
+ /*
cout << demangle(typeid(typename Graph::property_descriptor).name()) << endl;
cout << demangle(typeid(typename Graph::vertex_descriptor).name()) << endl;
cout << demangle(typeid(typename Graph::edge_descriptor).name()) << endl;
cout << demangle(typeid(typename Graph::property_store).name()) << endl;
cout << demangle(typeid(typename Graph::vertex_store).name()) << endl;
+ */
}
template <typename Graph>
@@ -255,17 +255,20 @@
void vec_vec()
{
cout << "---- vec/vec ----" << endl;
+ /*
typedef directed_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
test_add_multi_edges<Graph>();
- // test_incidence_iterator<Graph>();
- // test_adjacency_iterator<Graph>();
+ test_incidence_iterator<Graph>();
+ test_adjacency_iterator<Graph>();
+ */
}
void list_list()
{
cout << "---- list/list ----" << endl;
+ /*
typedef directed_graph<City, Road, vertex_list<>, edge_list<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
@@ -273,24 +276,25 @@
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
- // test_incidence_iterator<Graph>();
- // test_adjacency_iterator<Graph>();
+ test_incidence_iterator<Graph>();
+ test_adjacency_iterator<Graph>();
+ */
}
void set_set()
{
cout << "---- set/set ----" << endl;
+ /*
typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
- /*
test_disconnect_vertex<Graph>();
test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
test_remove_multi_edges<Graph>();
- // test_incidence_iterator<Graph>();
- // test_adjacency_iterator<Graph>();
+ test_incidence_iterator<Graph>();
+ test_adjacency_iterator<Graph>();
*/
}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/incidence_traits.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -2,9 +2,9 @@
#ifndef INCIDENCE_TRAITS_HPP
#define INCIDENCE_TRAITS_HPP
-struct incidence_vector_tag : sequence_tag, unstable_remove_tag { };
-struct incidence_list_tag : sequence_tag, stable_mutators_tag { };
-struct incidence_set_tag : associative_container_tag, stable_mutators_tag { };
+struct incidence_vector_tag : virtual vector_tag, virtual unstable_remove_tag { };
+struct incidence_list_tag : virtual list_tag, virtual stable_mutators_tag { };
+struct incidence_set_tag : virtual unique_associative_container_tag, virtual stable_mutators_tag { };
template <typename IncStore>
struct incidence_traits
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -148,7 +148,7 @@
// Instantiate data structures related to the storage of edges and their
// properties.
- typedef typename EdgeStore::template property_store<EdgeProps, VertexDesc>::type PropStore;
+ typedef typename EdgeStore::template property_store<EdgeProps>::type PropStore;
typedef typename EdgeStore::template incidence_store<VertexDesc>::type IncStore;
PropStore props;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -15,7 +15,7 @@
typedef index_descriptor<size_t> VertexDesc;
typedef index_descriptor<size_t> InDesc;
typedef int EdgeProps;
-typedef triple<VertexDesc, EdgeProps, InDesc> OutEdge;
+typedef pair<VertexDesc, pair<EdgeProps, InDesc>> OutEdge;
typedef allocator<OutEdge> Alloc;
typedef less<VertexDesc> Compare;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -81,8 +81,8 @@
{
test<vertex_vector<>>();
test<vertex_list<>>();
- // test<vertex_set<>>();
- // test<vertex_map<int>>();
+ test<vertex_set<>>();
+ test<vertex_map<int>>();
return 0;
}
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/typestr.hpp 2008-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -3,6 +3,7 @@
#define DEMANGLE_HPP
#include <string>
+#include <cstring>
#include <typeinfo>
#include <cxxabi.h>
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-07-09 12:51:12 EDT (Wed, 09 Jul 2008)
@@ -6,6 +6,7 @@
#include <boost/graphs/undirected_graph.hpp>
#include "typestr.hpp"
+#include "incidence_traits.hpp"
using namespace std;
using namespace boost;
@@ -17,6 +18,25 @@
void vec_vec();
void set_set();
+namespace dispatch
+{
+ bool allows_parallel_edges(unique_associative_container_tag)
+ { return false; }
+
+ bool allows_parallel_edges(multiple_associative_container_tag)
+ { return false; }
+
+ bool allows_parallel_edges(sequence_tag)
+ { return true; }
+}
+
+template <typename Graph>
+bool allows_parallel_edges(Graph const& g)
+{
+ typedef typename Graph::incidence_store Store;
+ return dispatch::allows_parallel_edges(typename incidence_traits<Store>::category());
+}
+
template <typename Graph>
void print_types(const Graph&)
{
@@ -31,6 +51,7 @@
template <typename Graph>
void test_add_vertices()
{
+ cout << " * add verts" << endl;
Graph g;
list<typename Graph::vertex_descriptor> V;
for(int i = 0; i < 5; ++i) {
@@ -41,12 +62,15 @@
template <typename Graph>
void test_add_remove_vertices()
{
+ cout << " * add verts" << endl;
Graph g;
list<typename Graph::vertex_descriptor> V;
for(int i = 0; i < 5; ++i) {
V.push_back(g.add_vertex(i));
}
BOOST_ASSERT(g.num_vertices() == 5);
+
+ cout << " * remove verts" << endl;
while(!V.empty()) {
g.remove_vertex(V.front());
V.pop_front();
@@ -57,6 +81,7 @@
template <typename Graph>
void test_add_edges()
{
+ cout << " * add edges" << endl;
Graph g;
vector<typename Graph::vertex_descriptor> V;
for(int i = 0; i < 3; ++i) {
@@ -67,12 +92,15 @@
g.add_edge(V[2], V[0]);
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ BOOST_ASSERT(g.degree(V[0]) == 2);
}
template <typename Graph>
void test_add_remove_edges()
{
Graph g;
+
+ cout << " * add edges" << endl;
vector<typename Graph::vertex_descriptor> V;
list<typename Graph::edge_descriptor> E;
for(int i = 0; i < 3; ++i) {
@@ -84,6 +112,7 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ cout << " * remove edges" << endl;
g.remove_edge(E.front());
BOOST_ASSERT(g.num_edges() == 2);
BOOST_ASSERT(g.degree(V[1]) == 1);
@@ -109,6 +138,7 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ cout << " * disconnecting vertex" << std::endl;
g.remove_edges(V[1]);
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.degree(V[1]) == 0);
@@ -133,6 +163,7 @@
BOOST_ASSERT(g.num_vertices() == 3);
BOOST_ASSERT(g.num_edges() == 3);
+ cout << " * removing conntected vertex" << endl;
g.remove_vertex(V[1]);
BOOST_ASSERT(g.num_vertices() == 2);
BOOST_ASSERT(g.degree(V[0]) == 1);
@@ -143,6 +174,8 @@
void test_add_multi_edges()
{
Graph g;
+
+ cout << " * adding parallel edges" << endl;
typename Graph::vertex_descriptor u = g.add_vertex(1);
typename Graph::vertex_descriptor v = g.add_vertex(2);
g.add_edge(u, v);
@@ -151,11 +184,13 @@
g.add_edge(v, u);
BOOST_ASSERT(g.num_vertices() == 2);
+
+ // If there are no parallel edges, then there should only be one edge.
if(allows_parallel_edges(g)) {
- BOOST_ASSERT(g.num_edges() == 1);
+ BOOST_ASSERT(g.num_edges() == 4);
}
else {
- BOOST_ASSERT(g.num_edges() == 4);
+ BOOST_ASSERT(g.num_edges() == 1);
}
}
@@ -170,8 +205,11 @@
g.add_edge(u, v);
g.add_edge(v, u);
+ cout << " * removing parallel edges" << endl;
g.remove_edges(u, v);
BOOST_ASSERT(g.num_edges() == 0);
+ BOOST_ASSERT(g.degree(u) == 0);
+ BOOST_ASSERT(g.degree(v) == 0);
}
template <typename Graph>
@@ -185,10 +223,11 @@
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
+ cout << " * incidence iterator" << endl;
typename Graph::incident_edge_range x = g.incident_edges(v);
typename Graph::incident_edge_iterator i = x.first;
for(typename Graph::incident_edge_iterator i = x.first; i != x.second; ++i) {
- // cout << *i << endl;
+ BOOST_ASSERT(*i);
}
}
@@ -203,9 +242,11 @@
g.add_edge(u, v, 3);
g.add_edge(v, u, 4);
- typename Graph::adjacent_vertex_range x = g.adjacent_vertices(v);
+ cout << " * adjacency iterator" << endl;
+ typename Graph::adjacent_vertex_range x = g.adjacent_vertices(u);
for( ; x.first != x.second; ++x.first) {
- // cout << "test: " << g[*x.first] << endl;
+ typename Graph::vertex_descriptor o = *x.first;
+ BOOST_ASSERT(o == v);
}
}
@@ -224,9 +265,9 @@
typedef undirected_graph<City, Road, vertex_vector<>, edge_vector<> > Graph;
test_add_vertices<Graph>();
test_add_edges<Graph>();
- // test_add_multi_edges<Graph>();
- // test_incidence_iterator<Graph>();
- // test_adjacency_iterator<Graph>();
+ test_add_multi_edges<Graph>();
+ test_incidence_iterator<Graph>();
+ test_adjacency_iterator<Graph>();
}
void list_list()
@@ -234,7 +275,6 @@
cout << "---- list/list ----" << endl;
typedef undirected_graph<City, Road, vertex_list<>, edge_list<> > Graph;
test_add_remove_vertices<Graph>();
- /*
test_add_remove_edges<Graph>();
test_disconnect_vertex<Graph>();
test_implicit_disconnect_vertex<Graph>();
@@ -242,7 +282,6 @@
test_remove_multi_edges<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<Graph>();
- */
}
@@ -251,7 +290,6 @@
cout << "---- set/set ----" << endl;
typedef undirected_graph<City, Road, vertex_set<>, edge_set<> > Graph;
test_add_remove_vertices<Graph>();
- /*
test_add_remove_edges<Graph>();
test_disconnect_vertex<Graph>();
test_implicit_disconnect_vertex<Graph>();
@@ -259,6 +297,5 @@
test_remove_multi_edges<Graph>();
test_incidence_iterator<Graph>();
test_adjacency_iterator<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