|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-08-08 10:21:13
Author: asutton
Date: 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
New Revision: 48030
URL: http://svn.boost.org/trac/boost/changeset/48030
Log:
Moving the adjacency list implementation into its own compartment.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/adjacency_iterator.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/compressed_edges.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_edges.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/compressed_vertices.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_vertices.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_edge.hpp
- copied unchanged from r48029, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_graph.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_types.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_vertex.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directional_edge.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_multiset.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_set.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/in_iterator.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/in_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/in_multiset.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/in_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/in_set.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/in_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/incidence_iterator.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/incidence_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/incidence_multiset.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/incidence_set.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/incidence_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_iterator.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_multiset.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/out_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_set.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/property_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/property_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_edge.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_graph.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_types.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_vertex.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_iterator.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_map.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_multimap.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multimap.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_multiset.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_set.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp
- copied unchanged from r47907, /sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first/
Removed:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_edges.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_vertices.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multimap.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multiset.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp | 5 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp | 63 ++++++++++++++++++++++++++++++++++++++++
2 files changed, 65 insertions(+), 3 deletions(-)
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_iterator.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,67 +0,0 @@
-
-#ifndef ADJACENCY_ITERATOR_HPP
-#define ADJACENCY_ITERATOR_HPP
-
-#include <iterator>
-
-/**
- * The adjacency iterator is an abstraction over incidence iterators. The
- * adjacency iterator actually provides the same functionality as the incidence
- * iterator, but simply provides access to the other vertices rather than the
- * edges.
- */
-template <typename Iterator>
-class adjacency_iterator
-{
-public:
- typedef Iterator iterator;
- typedef typename Iterator::vertex_descriptor vertex_descriptor;
-
- typedef typename iterator::iterator_category iterator_category;
- typedef typename iterator::difference_type difference_type;
- typedef vertex_descriptor value_type;
- typedef vertex_descriptor reference;
- typedef vertex_descriptor pointer;
-
- // Constructors
- inline adjacency_iterator()
- : _iter()
- { }
-
- inline adjacency_iterator(Iterator iter)
- : _iter(iter)
- { }
-
- inline adjacency_iterator& operator=(adjacency_iterator const& x)
- { _iter = x._iter; return *this; }
-
- inline adjacency_iterator& operator++()
- { ++_iter; return *this; }
-
- inline adjacency_iterator& operator--()
- { --_iter; return *this; }
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(adjacency_iterator const& x) const
- { return _iter == x._iter; }
-
- inline bool operator!=(adjacency_iterator const& x) const
- { return _iter != x._iter; }
- //@}
-
- reference operator*() const
- {
- // Return the opposite vertex referenced by the underlying iterator.
- // This lets us get away without having to store the source vertex
- // multiple types in the layered iterator.
- return _iter.opposite();
- }
-
-private:
- iterator _iter;
-};
-
-
-#endif
-
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first/algorithm.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
@@ -2,6 +2,8 @@
#ifndef BREADTH_FIRST_ALGORITHM_HPP
#define BREADTH_FIRST_ALGORITHM_HPP
+#include <queue>
+
// Contents:
//
// breadth_first_visit_edge - Visits a single edge.
@@ -66,8 +68,6 @@
{
typedef color_traits<typename ColorMap::value_type> ColorTraits;
typedef typename Graph::vertex_descriptor Vertex;
- typedef typename Graph::edge_descriptor Edge;
- typedef typename Graph::incident_edge_range EdgeRange;
// Run the walk on the vertices attached to start.
while(!queue.empty()) {
@@ -91,7 +91,6 @@
Queue queue = Queue())
{
typedef color_traits<typename ColorMap::value_type> ColorTraits;
- typedef typename Graph::vertex_descriptor Vertex;
detail::optional_prop_init(g, color, ColorTraits::white());
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
@@ -0,0 +1,63 @@
+
+#ifndef ALGORITHMS_DEPTH_FIRST_HPP
+#define ALGORITHMS_DEPTH_FIRST_HPP
+
+#include <boost/graphs/properties.hpp>
+#include <boost/graphs/colors.hpp>
+#include <boost/graphs/directional_edge.hpp>
+
+#include <boost/graphs/algorithms/utility.hpp>
+#include <boost/graphs/algorithms/iterator.hpp>
+
+struct dfs_visitor
+{
+ // Called when the vertex is popped from the stack. Not all examined
+ // vertices are discovered (e.g., a start vertex). Use this event to
+ // record the depth-first ordering of vertices.
+ template <typename Graph, typename Vertex>
+ inline void examine_vertex(Graph const& g, Vertex v)
+ { }
+
+ // Called when a vertex is encountered for the first time. Discovered
+ // vertices are examined unless the algorithm terminates before they are
+ // popped from the stack.
+ template <typename Graph, typename Vertex>
+ inline void discover_vertex(Graph const& g, Vertex v)
+ { }
+
+ // Called when all of the incident edges of the vertex have been examined.
+ template <typename Graph, typename Vertex>
+ inline void finish_vertex(Graph const& g, Vertex v)
+ { }
+
+ // Called for every incident edge of a vertex being examined. Examined
+ // edges are classified by the color of their targets at the time of
+ // investigation.
+ template <typename Graph, typename Edge>
+ inline void examine_edge(Graph const& g, Edge e)
+ { }
+
+ // Called for each examined edge that becomes part of the search tree. A
+ // tree edge is one whose source is being examined and whose target is
+ // discovered.
+ template <typename Graph, typename Edge>
+ inline void tree_edge(Graph const& g, Edge e)
+ { }
+
+ // Called for each examined edge whose target is in the search buffer. Back
+ // edges, cross edges, and forward edges are nontree edges.
+ template <typename Graph, typename Edge>
+ inline void back_edge(Graph const& g, Edge e)
+ { }
+
+ // Called for each examined edge whose target has already been removed from
+ // the search buffer. Technically, this is either a cross edge or a forward
+ // edge, but there's no way to easily distinguish them.
+ template <typename Graph, typename Edge>
+ inline void cross_edge(Graph const& g, Edge e)
+ { }
+};
+
+#include <boost/graphs/algorithms/depth_first/algorithm.hpp>
+
+#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_edges.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/compressed_vertices.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,232 +0,0 @@
-#ifndef DIRECTED_EDGE_HPP
-#define DIRECTED_EDGE_HPP
-
-#include <iosfwd>
-#include <iterator>
-
-#include <boost/graphs/directional_edge.hpp>
-
-/**
- * A directed edge represents an edge in a directed graph. A directed edge is
- * uniquely identified by its source and target vertices the descriptor into
- * the source vertex's out edge list, which also happens to uniquely describe
- * the edge property, if applicable.
- *
- * @param VertexDesc A vertex descriptor
- * @param OutDesc An out edge descriptor.
- */
-template <typename VertexDesc, typename OutDesc>
-class directed_edge
-{
-public:
- typedef VertexDesc vertex_descriptor;
- typedef OutDesc out_descriptor;
- typedef std::pair<vertex_descriptor, vertex_descriptor> edge_pair;
-
- /** @name Constructors */
- //@{
- inline directed_edge()
- : ends(), out()
- { }
-
- inline directed_edge(vertex_descriptor u, vertex_descriptor v, out_descriptor o)
- : ends(u, v), out(o)
- { }
-
- inline directed_edge(std::pair<vertex_descriptor, vertex_descriptor> x, out_descriptor o)
- : ends(x), out(o)
- { }
- //@}
-
- /** @name Descriptor-like Functions. */
- //@{
- inline bool is_null() const
- { return out.is_null(); }
-
- inline operator bool() const
- { return !is_null(); }
- //@}
-
- /** @name End Points
- * Provide access to the source and target of the directed edge. The
- * opposite member provides parity with undirected edge type. The first and
- * second accessors provide direction-free semantics, but return the source
- * and target() directly.
- */
- //@{
- inline vertex_descriptor source() const
- { return ends.first; }
-
- inline vertex_descriptor target() const
- { return ends.second; }
-
- inline vertex_descriptor first() const
- { return ends.first; }
-
- inline vertex_descriptor second() const
- { return ends.second; }
-
- inline vertex_descriptor opposite(vertex_descriptor v) const
- { return v == source() ? target() : source(); }
- //@}
-
- /** Return the descriptor to the out edge, where the property is stored. */
- inline out_descriptor out_edge() const
- { return out; }
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(directed_edge const& x) const
- { return (ends == x.ends) && (out == x.out); }
-
- inline bool operator!=(directed_edge const& x) const
- { return !operator==(x); }
- //@}
-
- /** @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); }
-
- inline bool operator>(directed_edge const& x) const
- { return x.operator<(*this); }
-
- inline bool operator<=(directed_edge const& x) const
- { return !x.operator<(*this); }
-
- 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)
-{ return os << "(" << e.source() << " " << e.target() << ")"; }
-
-/**
- * This is gonna be a little funky.
- */
-template <typename O, typename I>
-std::size_t hash_value(directed_edge<O,I> const& e)
-{
- using boost::hash;
- return hash_value(e.out);
-}
-
-/**
- * The directed edge iterator provides functionality for iterating over the
- * 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 VertexStore, typename Edge>
-struct directed_edge_iterator
-{
- typedef VertexStore vertex_store;
- typedef typename vertex_store::vertex_type vertex_type;
- typedef typename vertex_store::vertex_iterator vertex_iterator;
-
- typedef typename vertex_type::vertex_descriptor vertex_descriptor;
- typedef typename vertex_type::out_iterator edge_iterator;
- typedef typename vertex_type::out_descriptor out_descriptor;
-
- typedef std::forward_iterator_tag iterator_category;
- typedef typename vertex_iterator::difference_type difference_type;
- typedef Edge value_type;
- typedef value_type reference;
- typedef value_type pointer;
-
- directed_edge_iterator()
- : store(0), vert(), edge()
- { }
-
- directed_edge_iterator(vertex_store& s)
- : store(&s), vert(store->end_vertices()), edge()
- { }
-
- directed_edge_iterator(vertex_store& s, vertex_iterator i)
- : store(&s)
- , vert(i)
- , edge(next(vertex().begin_out(), true))
- { }
-
- /** Locate the next valid edge iterator, skipping the update on init. */
- inline edge_iterator next(edge_iterator e, bool first = false)
- {
- if(vert == store->end_vertices()) {
- // If we're at the end already, don't do anything, Just return the same
- // iterator that we got.
- return e;
- }
- else {
- if(e != vertex().end_out() && !first) {
- ++e;
- }
-
- // If after incrementing, we reach the end of the vertices, then
- // we have to skip to the next non-empty vertex or the end of the
- // sequence, whichever comes first.
- while(vert != store->end_vertices() && e == vertex().end_out())
- {
- ++vert;
- e = vertex().begin_out();
- }
- return vert != store->end_vertices() ? e : edge_iterator();
- }
- }
-
- /** Return the vertex, given the descriptor. */
- inline vertex_type& vertex()
- { return store->vertex(*vert); }
-
- /** Return the vertex, given the descriptor. */
- inline vertex_type const& vertex() const
- { return store->vertex(*vert); }
-
- /** Return the source vertex of the current edge. */
- inline vertex_descriptor source() const
- { return *vert; }
-
- /** Return the target vertex of the current edge. */
- inline vertex_descriptor target() const
- { return edge->first; }
-
- /**
- * Return the current out edge by translating the current iterator to a
- * descriptor
- */
- inline out_descriptor out_edge() const
- { return vertex().out_edge(edge); }
-
- inline directed_edge_iterator& operator++()
- {
- if(vert != store->end_vertices()) {
- edge = next(edge);
- }
- return *this;
- }
-
- inline directed_edge_iterator operator++(int)
- { directed_edge_iterator x(*this); operator++(); return x; }
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(directed_edge_iterator const& x) const
- { return (vert == x.vert) && (edge == x.edge); }
-
- inline bool operator!=(directed_edge_iterator const& x) const
- { return !operator==(x); }
- //@}
-
- inline reference operator*() const
- { return Edge(source(), target(), out_edge()); }
-
- vertex_store* store;
- vertex_iterator vert;
- edge_iterator edge;
-};
-
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,946 +0,0 @@
-
-#ifndef DIRECTED_GRAPH_HPP
-#define DIRECTED_GRAPH_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.
-
-// 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.
-
-// Note that directed graphs maintain an independent edge count since the actual
-// count would basically require a search.
-
-// Apparently directed graphs can be challenging - especially when you're
-// talking about in and out edges. Let's start with the basics - out edges. Each
-// out edge of a vertex references a target vertex descriptor and the properties
-// of that edge. However, there is an additional in edge that needs to be
-// accounted for (in another vertex no less). We could augment each out edge
-// with an iterator to its corresponding in edge.
-//
-// Each in edge is similarly defined. Minimally, this could contain only the
-// source vertex and a reference to the properties that define that edge. In
-// 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 <boost/none.hpp>
-#include <boost/graphs/directed_types.hpp>
-
-template <
- typename VertexProps,
- typename EdgeProps,
- typename VertexStore,
- 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;
- typedef EdgeProps edge_properties;
- typedef VertexStore vertex_store_selector;
- typedef EdgeStore edge_store_selector;
-
- // 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
- directed_graph();
-
- /** @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();
- vertex_descriptor add_vertex(vertex_properties const&);
- 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 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 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 Add Edge
- * Add an edge, connecting two vertices, to the graph. There are a number of
- * variations of this function, depending on the type of vertex store and
- * whether or not the edges are labeled. Convenience functions are provided
- * for graphs with UniqueVertices. Graphs with LabeledEdges can be added
- * with edge properties. Convenience functions are equivalent to the
- * expression add_edge(find_vertex(x), find_vertex(y), p) with x and y
- * eithe vertex proeprties or vertex keys and p optional edge properties.
- *
- * ExtendableEdgeSet add_edge(vertex_descriptor, vertex_descriptor)
- * && LabeledEdges add_edge(vertex_descriptor, vertex_descriptor, edge_properties)
- *
- * LabeledUniqueVertices add_edge(vertex_properties, vertex_properties)
- * && LabeledEdges add_edge(vertex_properties, vertex_properties, edge_properties)
- *
- * MappedUniqueVertices add_edge(vertex_key, vertex_key)
- * & LabeledEdges add_edge(vertex_key, vertex_key, edge_properties)
- */
- //@{
- 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 Test Edge
- * Determine if the edge, given by two vertices exists. This function a few
- * convenience overloads that depend on the type of vertex store.
- */
- //@{
- edge_descriptor edge(vertex_descriptor, vertex_descriptor) const;
- edge_descriptor edge(vertex_properties const&, vertex_properties const&) const;
- edge_descriptor edge(vertex_key const&, vertex_key const&) const;
- //@}
-
- /** @name Remove Edge(s)
- * Remove one or more edges from the graph. The function taking a single
- * edge descriptor removes exactly that edge. The fucntion(s) taking
- * a single vertex descriptor remove all edges incident to (both in and
- * out edges) that vertex. The function(s) taking two vertices remove all
- * edges connecting the two vertices. The so-called half-remove functions
- * remove only the outgoing and incoming edges from the given vertex.
- */
- //@{
- void remove_edge(edge_descriptor e);
-
- void remove_edges(vertex_descriptor);
- void remove_edges(vertex_properties const&);
- void remove_edges(vertex_key const&);
-
- void remove_out_edges(vertex_descriptor);
- void remove_out_edges(vertex_properties const&);
- void remove_out_edges(vertex_key const&);
-
- void remove_in_edges(vertex_descriptor);
- void remove_in_edges(vertex_properties const&);
- void remove_in_edges(vertex_key const&);
-
- void remove_edges(vertex_descriptor, vertex_descriptor);
- void remove_edges(vertex_properties const&, vertex_properties const&);
- void remove_edges(vertex_key const&, vertex_key const&);
- //@}
-
- /** @name Size and Degree
- * Return the in/out or cumulative degree of the given vertex.
- */
- //@{
- vertices_size_type num_vertices() const;
- edges_size_type num_edges() const;
- 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 Iterators */
- //@{
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
- vertex_range vertices() const;
-
- edge_iterator begin_edges() const;
- edge_iterator end_edges() const;
- edge_range edges() const;
-
- out_edge_iterator begin_out_edges(vertex_descriptor) const;
- out_edge_iterator end_out_edges(vertex_descriptor) const;
- out_edge_range out_edges(vertex_descriptor) const;
-
- in_edge_iterator begin_in_edges(vertex_descriptor) const;
- in_edge_iterator end_in_edges(vertex_descriptor) const;
- in_edge_range in_edges(vertex_descriptor) const;
-
- incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
- incident_edge_iterator end_incident_edges(vertex_descriptor) const;
- incident_edge_range incident_edges(vertex_descriptor) const;
-
- adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
- //@}
-
- /** @name Property Accessors
- * Access the properties of the given vertex or edge.
- */
- //@{
- vertex_properties& operator[](vertex_descriptor);
- vertex_properties const& operator[](vertex_descriptor) const;
- edge_properties& operator[](edge_descriptor);
- edge_properties const& operator[](edge_descriptor) const;
- //@}
-
-private:
- mutable vertex_store _verts;
- edges_size_type _edges;
-};
-
-#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()
- , _edges(0)
-{ }
-
-/**
- * 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
- * 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);
-}
-
-/**
- * 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);
-}
-
-/**
- * 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)
-{
- remove_edges(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);
- remove_edges(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)
-{
- remove_edges(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);
-
- insertion_result<out_descriptor> first = src.connect_target(v, ep);
- if(first.succeeded()) {
- insertion_result<in_descriptor> second = tgt.connect_source(u, first.value);
- BOOST_ASSERT(second.succeeded());
-
- // Bind the out edge to the in edge and return the edge (incrementing
- // the locally stored number of edges also).
- src.bind_target(first.value, second.value);
- ++_edges;
- return edge_descriptor(u, v, first.value);
- }
- else if(first.retained()) {
- // Return an edge over the existing values.
- return edge_descriptor(u, v, first.value);
- }
- else {
- return edge_descriptor();
- }
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given properties. The edge is either unlabeled or has default properties.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
- vertex_properties const& v)
-{
- return add_edge(u, v, edge_properties());
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given properties and has the given edge properties.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
- vertex_properties const& v,
- edge_properties const& ep)
-{
- return add_edge(find_vertex(u), find_vertex(v), ep);
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given keys. The edge is either unlabeled or has default properties.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v)
-{
- return add_edge(u, v, edge_properties());
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given keys and has the given edge properties.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v,
- edge_properties const& ep)
-{
- return add_edge(find_vertex(u), find_vertex(v), ep);
-}
-
-/**
- * Remove the edge connecting the two vertices. This removes only the given
- * edge. Other edges connecting the two vertices remain.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
-{
- // Grab the vertices in question
- vertex_type& src = _verts.vertex(e.source());
- vertex_type& tgt = _verts.vertex(e.target());
-
- // Grab the in and out descriptors corresponding to the out edge and its
- // reverse in edge.
- out_descriptor o = e.out_edge();
- in_descriptor i = src.in_edge(o);
-
- // And disconnect them.
- src.disconnect_target(o);
- tgt.disconnect_source(i);
-}
-
-/**
- * Remove all edges incident to this vertex. This will remove all edges in
- * which the given vertex appears as either a source or target, effectively
- * disconnecting the vertex from the graph. This is equivalent to calling
- * remove_out_edges(v) and removing_in_edges(v).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
-{
- remove_in_edges(v);
- remove_out_edges(v);
-}
-
-/**
- * Remove all edges incident to the vertex identified by the given properties.
- * This is equivalent to remove_edges(find_vertex(vp));
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- remove_edges(find_vertex(vp));
-}
-
-/**
- * Remove all edges incident to the vertex identified by the given key. This is
- * equivalent to remove_edges(find_vertex(k)).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& k)
-{
- remove_edges(find_vertex(k));
-}
-
-/**
- * Remove all out edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_descriptor v)
-{
- vertex_type& src = _verts.vertex(v);
-
- // Iterate over the out edges of v and remove all of the incoming parts of
- // each out edge and decrement the edge count.
- out_edge_range rng = out_edges(v);
- for( ; rng.first != rng.second; ++rng.first) {
- edge_descriptor e = *rng.first;
- out_descriptor o = e.out_edge();
- in_descriptor i = src.in_edge(o);
-
- // Disconnect the vertices.
- vertex_type& tgt = _verts.vertex(e.target());
- tgt.disconnect_source(i);
- }
-
- // Clear the out edges.
- _edges -= src.out_degree();
- src.clear_out();
-}
-
-/**
- * Remove all out edges of the vertex identified by the given properties. This
- * is equivalent to remove_out_edges(find_vertex(vp));
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- remove_out_edges(find_vertex(vp));
-}
-
-/**
- * Remove all out edges incident to the vertex identified by the given key. This
- * is equivalent to remove_out_edges(find_vertex(k)).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_out_edges(vertex_key const& k)
-{
- remove_out_edges(find_vertex(k));
-}
-
-/**
- * Remove all in edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_descriptor v)
-{
- vertex_type& tgt = _verts.vertex(v);
-
- // Remove all in edges from v, making v a source vertex (all out, no in).
- // The edge is actually removed from the source of the in edges of this
- // vertex.
- in_edge_range rng = in_edges(v);
- for( ; rng.first != rng.second; ++rng.first) {
- edge_descriptor e = *rng.first;
- vertex_type& src = _verts.vertex(e.source());
- src.disconnect_target(e.out_edge());
- }
-
- // Clear out the vertices lists.
- _edges -= tgt.in_degree();
- tgt.clear_in();
-}
-
-/**
- * Remove all in edges of the vertex identified by the given properties. This
- * is equivalent to remove_in_edges(find_vertex(vp));
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- remove_in_edges(find_vertex(vp));
-}
-
-/**
- * Remove all out edges incident to the vertex identified by the given key. This
- * is equivalent to remove_in_edges(find_vertex(k)).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_in_edges(vertex_key const& k)
-{
- remove_in_edges(find_vertex(k));
-}
-
-/**
- * Remove all edges connecting the vertex u to v. This function only removes
- * the edges with u as a source and v as a target.
- *
- * To remove all edges interconnecting u and v, first call remove_edges(u, v)
- * followed by remove_edges(v, u).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u, vertex_descriptor v)
-{
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Iterate over the out edges of the source, storing out edges for
- // subsequent removal and actually removing in edges.
- std::vector<out_descriptor> outs;
- out_edge_range rng = out_edges(u);
- for(out_edge_iterator i = rng.first ; i != rng.second; ++i) {
- // If the target vertex is one that we want to remove, remove the in
- // edge from the target and stash the out edge for subsequent removal
- // in a second pass.
- edge_descriptor e = *i;
- if(e.target() == v) {
- out_descriptor o = e.out_edge();
- in_descriptor i = src.in_edge(e.out_edge());
- tgt.disconnect_source(i);
- outs.push_back(o);
- }
- }
-
- // Second pass: remove all the out edge descriptors and decrement the count.
- typename std::vector<out_descriptor>::iterator i, end = outs.end();
- for(i = outs.begin(); i != end; ++i) {
- src.disconnect_target(*i);
- --_edges;
- }
-}
-
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& u,
- vertex_properties const& v)
-{
- remove_vertices(find_vertex(u), find_vertex(v));
-}
-
-template <BOOST_GRAPH_DG_PARAMS>
-void
-directed_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& u,
- vertex_key const& v)
-{
- remove_vertices(find_vertex(u), find_vertex(v));
-}
-
-
-/**
- * Test to see if the given edge exists. Return a pair containing the edge
- * descriptor (if it exists), and a boolean value indicating whether it actually
- * exists or not.
- *
- * @todo Consider making descriptors "self-invalidating".
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
-{
- vertex_type& src = _verts.vertex(u);
- out_descriptor o = src.find_target(v);
- return o ? edge_descriptor(u, v, o) : edge_descriptor();
-}
-
-/**
- * Test to see if at least one edge connects the two vertices identified by
- * the given properties. Return a pair containing a descriptor to the first such
- * edge (if it exists), and a boolean value indicating whether it actually
- * exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
- vertex_properties const& v) const
-{
- return edge(find_vertex(u), find_vertex(v));
-}
-/**
- * Test to see if at least one edge connects the two vertices identified by
- * the given key. Return a pair containing a descriptor to the first such
- * edge (if it exists), and a boolean value indicating whether it actually
- * exists or not. This is equivalent to edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_descriptor
-directed_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
- vertex_key const& v) const
-{
- return edge(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Return the number of vertices in the graph.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::vertices_size_type
-directed_graph<VP,EP,VS,ES>::num_vertices() const
-{
- return _verts.size();
-}
-
-/**
- * Return the number of edges in the graph.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edges_size_type
-directed_graph<VP,EP,VS,ES>::num_edges() const
-{
- return _edges;
-}
-
-
-/**
- * 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 an iterator to the first vertex. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::vertex_iterator
-directed_graph<VP,EP,VS,ES>::begin_vertices() const
-{ return _verts.begin_vertices(); }
-
-/** Return an iterator past the end of the vertices. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::vertex_iterator
-directed_graph<VP,EP,VS,ES>::end_vertices() const
-{ return _verts.end_vertices(); }
-
-/** Return an iterator range over the vertices in the graph. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::vertex_range
-directed_graph<VP,EP,VS,ES>::vertices() const
-{ return _verts.vertices(); }
-
-/** Return an iterator to the first edge. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_iterator
-directed_graph<VP,EP,VS,ES>::begin_edges() const
-{ return edge_iterator(_verts, _verts.begin_vertices()); }
-
-/** Return an iterator past the end of the edges. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_iterator
-directed_graph<VP,EP,VS,ES>::end_edges() const
-{ return edge_iterator(_verts); }
-
-/** Return an iterator range over the edges in the graph. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_range
-directed_graph<VP,EP,VS,ES>::edges() const
-{ return std::make_pair(begin_edges(), end_edges()); }
-
-/** Return an iterator to the first out edge of the given vertex. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
-directed_graph<VP,EP,VS,ES>::begin_out_edges(vertex_descriptor v) const
-{
- vertex_type& vert = _verts.vertex(v);
- return out_edge_iterator(vert, v, vert.begin_out());
-}
-
-/**
- * Return an iterator past the end of then out edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::out_edge_iterator
-directed_graph<VP,EP,VS,ES>::end_out_edges(vertex_descriptor v) const
-{
- vertex_type& vert = _verts.vertex(v);
- return out_edge_iterator(vert, v, vert.end_out());
-}
-
-/**
- * Return awn iterator range over the out edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::out_edge_range
-directed_graph<VP,EP,VS,ES>::out_edges(vertex_descriptor v) const
-{
- return std::make_pair(begin_out_edges(v), end_out_edges(v));
-}
-
-/**
- * Return an iterator to the first in edge of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::in_edge_iterator
-directed_graph<VP,EP,VS,ES>::begin_in_edges(vertex_descriptor v) const
-{
- return in_edge_iterator(v, _verts.vertex(v).begin_in());
-}
-
-/**
- * Return an iterator past the end of then in edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::in_edge_iterator
-directed_graph<VP,EP,VS,ES>::end_in_edges(vertex_descriptor v) const
-{ return in_edge_iterator(v, _verts.vertex(v).end_in()); }
-
-/**
- * Return an iterator range over the in edges of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::in_edge_range
-directed_graph<VP,EP,VS,ES>::in_edges(vertex_descriptor v) const
-{ return std::make_pair(begin_in_edges(v), end_in_edges(v)); }
-
-/**
- * Return an iterator to the first incident edge of the given vertex. This is
- * an alias for begin_out_edges(v).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::incident_edge_iterator
-directed_graph<VP,EP,VS,ES>::begin_incident_edges(vertex_descriptor v) const
-{ return begin_out_edges(v); }
-
-/**
- * Return an iterator past the end of the incident edges of the given vertex.
- * This is an alias for end_out_edges(v).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::incident_edge_iterator
-directed_graph<VP,EP,VS,ES>::end_incident_edges(vertex_descriptor v) const
-{ return end_out_edges(v); }
-
-/**
- * Return an iterator range over the incident edges of the given vertex. This
- * is an alias for out_edges(v).
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::incident_edge_range
-directed_graph<VP,EP,VS,ES>::incident_edges(vertex_descriptor v) const
-{ return out_edges(v); }
-
-/**
- * Return an iterator to the first adjacent vertex of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-directed_graph<VP,EP,VS,ES>::begin_adjacent_vertices(vertex_descriptor v) const
-{ return adjacent_vertex_iterator(begin_incident_edges(v)); }
-
-/**
- * Return an iterator past the end of the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-directed_graph<VP,EP,VS,ES>::end_adjacent_vertices(vertex_descriptor v) const
-{ return adjacent_vertex_iterator(end_incident_edges(v)); }
-
-/**
- * Return an iterator range over the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::adjacent_vertex_range
-directed_graph<VP,EP,VS,ES>::adjacent_vertices(vertex_descriptor v) const
-{ return std::make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v)); }
-
-/** 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 vertex. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::vertex_properties const&
-directed_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v) const
-{ 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 _verts.vertex(e.source()).get_edge_properties(e.out_edge()); }
-
-/** Return the properties for the given edge. */
-template <BOOST_GRAPH_DG_PARAMS>
-typename directed_graph<VP,EP,VS,ES>::edge_properties const&
-directed_graph<VP,EP,VS,ES>::operator[](edge_descriptor e) const
-{ return _verts.vertex(e.source()).get_edge_properties(e.out_edge()); }
-
-#undef BOOST_GRAPH_DG_PARAMS
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_types.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,87 +0,0 @@
-
-#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.
- */
-template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
-struct 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>::type out_store;
- typedef typename out_store::size_type out_edges_size_type;
- typedef typename out_store::size_type edges_size_type;
-
- // Generate the in store and related types
- typedef typename EdgeStore::template in_store<vertex_descriptor>::type in_store;
- typedef typename in_store::size_type in_edges_size_type;
-
- // Generate the incident edge size type. It should be the larger of the two,
- // but for now it's just the out edges.
- typedef out_edges_size_type incident_edges_size_type;
-
- // 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 VertexStore::key_type vertex_key;
-
- // Generate a bunch of iterators
- typedef basic_out_iterator<vertex_type, edge_descriptor> out_edge_iterator;
- typedef std::pair<out_edge_iterator, out_edge_iterator> out_edge_range;
- 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;
- typedef directed_edge_iterator<vertex_store, edge_descriptor> edge_iterator;
- typedef std::pair<edge_iterator, edge_iterator> edge_range;
-
- // Generate incident edge iterators as out edge iterators - not a
- // combination of in and out edges.
- typedef out_edge_iterator incident_edge_iterator;
- typedef out_edge_range incident_edge_range;
-
- // Generate adjacent vertx iterators over the incidence iterator
- typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
- typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,166 +0,0 @@
-
-#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::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;
-
- /** @name Constructors */
- //@{
- inline directed_vertex()
- : _props(), _out(), _in()
- { }
-
- inline directed_vertex(vertex_properties const& vp)
- : _props(vp), _out(), _in()
- { }
- //@}
-
- /** @name Edge Connection and Disconnection
- * These functions provide an interface to the in and out stores of the
- * vertex. The connection of this vertex to a target is a two-phase
- * operation. First, the connection is made to the target and vice-versa
- * from the source. Then, the target is bound with the in edge descriptor
- * of the source.
- */
- //@{
- insertion_result<out_descriptor> connect_target(vertex_descriptor v, edge_properties const& ep)
- { return _out.add(v, ep); }
-
- insertion_result<in_descriptor> connect_source(vertex_descriptor v, out_descriptor o)
- { return _in.add(v, o); }
-
- void bind_target(out_descriptor o, in_descriptor i)
- { _out.bind(o, i); }
-
- void disconnect_target(out_descriptor o)
- { _out.remove(o); }
-
- void disconnect_source(in_descriptor i)
- { _in.remove(i); }
-
- /** Find the (at least one?) out edge connected to the given vertex. */
- out_descriptor find_target(vertex_descriptor v)
- { return _out.find(v); }
- //@}
-
- /** @name Vertex Property Accessors */
- //@{
- inline vertex_properties& properties()
- { return _props; }
-
- inline vertex_properties const& properties() const
- { return _props; }
-
- // Return the edge properties for the given out edge descriptor.
- inline edge_properties& get_edge_properties(out_descriptor o)
- { return _out.properties(o); }
-
- inline edge_properties const& get_edge_properties(out_descriptor o) const
- { return _out.properties(o); }
- //@}
-
- /** Return the reverse out descriptor for the given in edge. */
- inline out_descriptor out_edge(in_descriptor i) const
- { return _in.out_edge(i); }
-
- /** Return the reverse in descriptor for the given out edge. */
- inline in_descriptor in_edge(out_descriptor o) const
- { return _out.in_edge(o); }
-
-
- /** Return a descriptor for the iterator into the underlying container. */
- inline out_descriptor out_edge(out_iterator o) const
- { return _out.out_edge(o) ;}
-
- /** Return a descriptor for the iterator into the underlying container */
- inline in_descriptor in_edge(in_iterator i) const
- { return _in.in_edge(i); }
-
-
- /** @name Out Edges */
- //@{
- inline out_iterator begin_out() const
- { return _out.begin(); }
-
- inline out_iterator end_out() const
- { return _out.end(); }
-
- inline out_iterator find_out(vertex_descriptor v) const
- { return _out.find(v); }
-
- inline void clear_out()
- { _out.clear(); }
- //@}
-
- /** @name In Edges */
- //@{
- inline in_iterator begin_in() const
- { return _in.begin(); }
-
- inline in_iterator end_in() const
- { return _in.end(); }
-
- inline in_iterator find_in(vertex_descriptor v) const
- { return _in.find(v); }
-
- inline void clear_in()
- { return _in.clear(); }
- //@}
-
-
- /** @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); }
-
- inline bool operator<(directed_vertex const& x) const
- { return _props < x._props; }
- //@}
-
-private:
- vertex_properties _props;
- out_store _out;
- in_store _in;
-};
-
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,63 +0,0 @@
-
-#ifndef DIRECTIONAL_EDGE_HPP
-#define DIRECTIONAL_EDGE_HPP
-
-// This basically wraps a concept called DirectionalEdge. A DirectionalEdge
-// is one that has directionality being imposed on it. Specializations of
-// these edge should be found with the graph types.
-
-namespace detail
-{
- // By default, we assume that the edge is directed.
- template <typename Edge>
- struct directional_edge_adapter : Edge
- {
- typedef typename Edge::vertex_descriptor Vertex;
-
- inline directional_edge_adapter()
- : Edge()
- { }
-
- inline directional_edge_adapter(Edge e, Vertex)
- : Edge(e)
- { }
-
- inline directional_edge_adapter(Vertex s, Vertex t)
- : Edge(s, t)
- { }
- };
-}
-
-/**
- * The diretional edge type forces directionality onto the given edge structure
- * even when non exists. That this is not the same as a directed edge, which has
- * a distinct direction to it. This simply imposes a direction over the edge
- * with respect to the a source vertex. For directed graphs, this essentially
- * does nothing. For undirected graphs, the source vertex is used to compute
- * the opposite end (target).
- *
- * Directional edges are intended for use in algorithms that walk the graph
- * structure. The act of walking from one vertex to another adds an implicit
- * directionality to the edge. This class embodies that directionality for both
- * directed and undirected graphs.
- *
- * Directional edge descriptors can be used interchangeably with normal edge
- * descriptors.
- */
-template <typename Edge>
-struct directional_edge
- : detail::directional_edge_adapter<Edge>
-{
- typedef Edge edge_descriptor;
- typedef typename Edge::vertex_descriptor vertex_descriptor;
-
- inline directional_edge()
- : detail::directional_edge_adapter<Edge>()
- { }
-
- inline directional_edge(edge_descriptor e, vertex_descriptor v)
- : detail::directional_edge_adapter<Edge>(e, v)
- { }
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,87 +0,0 @@
-
-#ifndef EDGE_LIST_HPP
-#define EDGE_LIST_HPP
-
-#include <list>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-// Forward declarations
-template <typename, typename> class property_list;
-template <typename, typename> class incidence_list;
-template <typename, typename> class out_list;
-template <typename, typename> class in_list;
-
-// The edge list does two things. First, it indicates that edges will
-// be stored in an incidence list (as opposed to a vector or set).
-// Second, this will indicate the use of a global property list.
-// Again, as opposed to a vector.
-
-/**
- * The basic_edge_list is the outer part of the metafunctions that generate
- * types for adjacency lists.
- */
-template <
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_list
-{
- // A couple of dummy vectors used to build descriptors.
- typedef std::list<int, FirstAlloc<int>> first_dummy;
- typedef std::list<int, SecondAlloc<int>> second_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
-
- // The property store metafunction generates the underlying global store
- // type for edge properties in undirected graphs.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_list<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the per-vertex storage type
- // for undirected vertices.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, property_descriptor> incidence_pair;
- typedef FirstAlloc<incidence_pair> allocator;
- typedef incidence_list<incidence_pair, allocator > type;
- };
-
-
-
- // Descriptor types for directed graphs
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // The out store metafunction generates the type of list used to store
- // out edges of a vertex in a directed graph.
- template <typename VertexDesc, typename EdgeProps>
- struct out_store
- {
- typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
- typedef FirstAlloc<edge> allocator;
- typedef out_list<edge, allocator> type;
- };
-
- // The in store metafunction generates the type of list used to store
- // incoming edges of directed graph. In edges are represented by the
- // referencing vertex and an out edge descriptor.
- template <typename VertexDesc>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef SecondAlloc<edge> allocator;
- typedef in_list<edge, allocator> type;
- };
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,98 +0,0 @@
-
-#ifndef EDGE_SET_HPP
-#define EDGE_SET_HPP
-
-#include <list>
-#include <map>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-// Forward declarations
-template <typename, typename> class property_list;
-template <typename, typename, typename> class incidence_set;
-template <typename, typename, typename> class out_set;
-template <typename, typename, typename> class in_set;
-
-/**
- * The edge set metafunction defines the basic facets of set-based edge
- * storage. Edge sets are best used to implement simple graphs (that do not
- * allow multiple edges).
- *
- * @param Compare - A unary template class that compares vertex descriptors.
- * @param FirstAlloc - An allocator template for either incident edges or out edges.
- * @param SecondAlloc - An allocator template for either global properties or in edges.
- */
-template <
- template <typename> class Compare = std::less,
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_set
-{
- // Several dummy containers used to build descriptors. This looks really
- // weird since we're expecting a set type somewhere around here. However,
- // there isn't actually a real "set" used in these stores. The property
- // store only needs to be a list, and the incidence/in/out stores are
- // actually all maps (vertex to something).
- typedef std::map<int, int, Compare<int>, FirstAlloc<int>> first_dummy;
- typedef std::map<int, int, Compare<int>, SecondAlloc<int>> second_dummy;
- typedef std::list<int, SecondAlloc<int>> prop_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<prop_dummy>::descriptor_type property_descriptor;
-
- // The property store metafunnction generates the global store type for
- // undirected graphs. The property list only needs to be a list, not a set.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_list<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the per-vertex stores for
- // incident edges.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, property_descriptor> value;
- typedef Compare<VertexDesc> compare;
- typedef FirstAlloc<value> allocator;
- typedef incidence_set<value, compare, allocator> type;
- };
-
-
-
- // Descriptor types for directed graphs
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // The out store metafunction generates the type of set used to store out
- // edges of a vertex in a directed graph.
- template <typename VertexDesc, typename EdgeProps>
- struct out_store
- {
- 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;
- };
-
- // The in store metafunction generates the type of list used to store
- // incoming edges of directed graph. In edges are represented by the
- // referencing vertex and an out edge descriptor.
- template <typename VertexDesc>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef Compare<VertexDesc> compare;
- typedef SecondAlloc<edge> allocator;
- typedef in_set<edge, compare, allocator> type;
- };
-};
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,101 +0,0 @@
-
-#ifndef EDGE_VECTOR_HPP
-#define EDGE_VECTOR_HPP
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-// Forward declarations
-template <typename, typename> class property_vector;
-template <typename, typename> class incidence_vector;
-template <typename, typename> class out_vector;
-template <typename, typename> class in_vector;
-
-// 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
-// are the possible parameters to edge storage?
-// 1. The edge properties
-// 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.
-
-/**
- * The basic_edge_vector is the outer part of the metafunctions that generate
- * types for adjacency lists.
- *
- * This is not the prettiest solution, but it does reuse the same outer
- * metafunction for both directed and undirected graphs. The meaning of the
- * first and second allocator differ depending on the type of graph. For
- * undirected graphs, FirstAlloc is the allocator for the per-vertex incidence
- * store and the SecondAlloc is the allocator for properties. For directed
- * graphs, FirstAlloc and SecondAlloc are the per-vertex allocators for
- * out- and in-edge stores respectively.
- */
-template <
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_vector
-{
- // A couple of dummy vectors used to build descriptors.
- typedef std::vector<int, FirstAlloc<int>> first_dummy;
- typedef std::vector<int, SecondAlloc<int>> second_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type property_descriptor;
-
- // The property store metafunction generates the type of vector used to
- // store global properties for undirected graphs.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_vector<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the type of vector used to
- // store edges incident to the an undirected vertex.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, property_descriptor> incidence_pair;
- typedef FirstAlloc<incidence_pair> incidence_allocator;
- typedef incidence_vector<incidence_pair, incidence_allocator> type;
- };
-
-
-
- // Descriptor types for directed graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // 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 EdgeProps>
- struct out_store
- {
- typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
- typedef FirstAlloc<edge> allocator;
- typedef out_vector<edge, allocator> type;
- };
-
- // The in store metafunction generates the type of vector used to store
- // incoming edges of directed graph. In edges are represented by the
- // referencing vertex and an out edge descriptor.
- template <typename VertexDesc>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef SecondAlloc<edge> allocator;
- typedef in_vector<edge, allocator> type;
- };
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,65 +0,0 @@
-
-#ifndef IN_ITERATOR_HPP
-#define IN_ITERATOR_HPP
-
-/**
- * The in edge iterator is a wrapper around out store iterators that, when
- * dereferenced will return an edge descriptor. The iterator category is taken
- * from the base iterator. The in edge iterator also needs to know the type
- * of the out edge iterator since in edges contain placeheld references to
- * out edges.
- */
-template <typename Iter, typename Edge>
-class basic_in_iterator
-{
-public:
- 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()
- : tgt(), iter()
- { }
-
- inline basic_in_iterator(vertex_descriptor v, iterator x)
- : tgt(v), iter(x)
- { }
- //@}
-
- /** Return the source vertex of the iterated edge. */
- vertex_descriptor source() 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; }
-
- inline basic_in_iterator& operator--()
- { --iter; return *this; }
-
- inline bool operator==(basic_in_iterator const& x) const
- { return iter == x.iter; }
-
- inline bool operator!=(basic_in_iterator const& x) const
- { return iter != x.iter; }
-
- inline reference operator*() const
- { return Edge(source(), target(), iter->second); }
-
- vertex_descriptor tgt;
- iterator iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,108 +0,0 @@
-
-#ifndef IN_LIST_HPP
-#define IN_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * 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 edge descriptor.
- * @param Alloc The allocator for edge pairs.
- */
-template <typename Edge, typename Alloc>
-class in_list
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type out_descriptor;
-
- typedef std::list<Edge, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
-
- // Constructor
- inline in_list()
- : _edges(), _size(0)
- { }
-
- /**
- * Add the edge to list.
- * @complexity O(1)
- */
- insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
- {
- ++_size;
- iterator i = _edges.insert(_edges.end(), std::make_pair(v, o));
- return make_result(make_descriptor(_edges, i));
- }
-
- /**
- * Find the edge whose source originates at the given vertex descriptor.
- * @complexity O(d)
- */
- in_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /**
- * Remove the edge referenced by the given iterator.
- * @complexity O(1)
- */
- void remove(in_descriptor d)
- {
- _edges.erase(make_iterator(_edges, d));
- --_size;
- }
-
- /** Remove all incoming edges from the list, resetting the size to 0. */
- inline void clear()
- {
- _size = 0;
- _edges.clear();
- }
-
- /** Get the number of incoming edges (in degree). */
- inline size_type size() const
- { return _size; }
-
- /** Returns true if there are no in edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Return the source vertex of the in edge. */
- inline vertex_descriptor source(in_descriptor i) const
- { return make_iterator(_edges, i)->first; }
-
- /** Return the reverse edge descriptor bound to the in edge. */
- inline out_descriptor out_edge(in_descriptor i) const
- { return make_iterator(_edges, i)->second; }
-
- /** Return a desecriptor for an iterator into this object. */
- inline in_descriptor in_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
- size_type _size;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,95 +0,0 @@
-
-#ifndef IN_SET_HPP
-#define IN_SET_HPP
-
-#include <map>
-
-#include <boost/descriptors.hpp>
-
-/**
- * The in-edge set 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 edge descriptor.
- * @param Alloc The allocator for edge pairs.
- */
-template <typename Edge, typename Compare, typename Alloc>
-class in_set
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type out_descriptor;
-
- typedef std::map<vertex_descriptor, out_descriptor, Compare, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
-
- // Constructor
- inline in_set()
- : _edges()
- { }
-
- /**
- * Try to add the given vertex to the result set.
- * @complexity O(lg(d))
- */
- insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
- {
- std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, o));
- return make_result(_edges, i);
- }
-
- /**
- * Find the edge whose source originates at the given vertex descriptor.
- * @complexity O(lg(d))
- */
- in_descriptor find(vertex_descriptor v) const
- { return make_descriptor(_edges, _edges.find(v)); }
-
- /**
- * Remove the edge with the given descriptor.
- * @complexity O(lg(d))
- */
- void remove(in_descriptor d)
- { _edges.erase(make_iterator(_edges, d)); }
-
- /** Remove all edges. */
- inline void clear()
- { _edges.clear(); }
-
- /** Get the number of incoming edges (in degree). */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Return true if there are no in edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Return the source vertex of the in edge. */
- inline vertex_descriptor source(in_descriptor i) const
- { return make_iterator(_edges, i)->first; }
-
- /** Return the reverse edge descriptor bound to the in edge. */
- inline out_descriptor out_edge(in_descriptor i) const
- { return make_iterator(_edges, i)->second; }
-
- /** Return a desecriptor for an iterator into this object. */
- inline in_descriptor in_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,89 +0,0 @@
-
-#ifndef IN_VECTOR_HPP
-#define IN_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * 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 edge descriptor.
- * @param Alloc The allocator for edge pairs.
- */
-template <typename Edge, typename Alloc>
-class in_vector
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type out_descriptor;
-
- typedef std::vector<Edge, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type in_descriptor;
-
- // Constructor
- inline in_vector()
- : _edges()
- { }
-
- /**
- * Add the edge to the vector, returning an iterator to the added element.
- * @complexity O(1)
- */
- insertion_result<in_descriptor> add(vertex_descriptor v, out_descriptor o)
- {
- iterator i = _edges.insert(_edges.end(), std::make_pair(v, o));
- return make_result(make_descriptor(_edges, i));
- }
-
- /**
- * Find the edge whose source originates at the given vertex descriptor.
- * @complexity O(d)
- */
- inline in_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /** Get the number of incoming edges (in degree). */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Returns true if there are no in edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Return the source vertex of the in edge. */
- inline vertex_descriptor source(in_descriptor i) const
- { return make_iterator(_edges, i)->first; }
-
- /** Return the reverse edge descriptor bound to the in edge. */
- inline out_descriptor out_edge(in_descriptor i) const
- { return make_iterator(_edges, i)->second; }
-
- /** Return a desecriptor for an iterator into this object. */
- inline in_descriptor in_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_iterator.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,85 +0,0 @@
-
-#ifndef INCIDENCE_ITERATOR_HPP
-#define INCIDENCE_ITERATOR_HPP
-
-/**
- * The incidence iterator is an abstraction over the incidence iterators of
- * a vertice's incidence store. Specifically when dereferenced, these iterators
- * will result in edge descriptors.
- */
-template <typename Iter, typename Edge>
-class incidence_iterator
-{
-public:
- typedef Iter iterator;
- typedef typename iterator::value_type base_value_type;
- typedef typename boost::remove_const<typename base_value_type::first_type>::type vertex_descriptor;
- typedef typename base_value_type::second_type property_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 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 incidence_iterator()
- : base(), iter()
- { }
-
- inline incidence_iterator(vertex_descriptor v, iterator x)
- : 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.
- */
- inline vertex_descriptor source() const
- { return base; }
-
- /**
- * Extended iterator functionality. Return the opposite vertex of the edge
- * indicated by the iterator. This is mostly provided for use by the
- * adjacency iterator.
- */
- inline vertex_descriptor opposite() const
- { return iter->first; }
-
- inline incidence_iterator& operator=(incidence_iterator const& x)
- { base = x.base; iter = x.iter; return *this; }
-
- inline incidence_iterator& operator++()
- { ++iter; return *this; }
-
- inline incidence_iterator operator++(int)
- { incidence_iterator tmp(*this); ++iter; return tmp; }
-
- inline incidence_iterator& operator--()
- { --iter; return *this; }
-
- inline incidence_iterator operator--(int)
- { incidence_iterator tmp(*this); --iter; return tmp; }
-
- // Incidence iterators are equivalent if they have the same source and are
- // reference the same incident edge.
- inline bool operator==(incidence_iterator const& x) const
- { return (base == x.base) && (iter == x.iter); }
-
- inline bool operator!=(incidence_iterator const& x) const
- { return !this->operator==(x); }
-
- // This can access invalid memory if the iterator is at the end.
- inline reference operator*() const
- { return Edge(base, iter->first, iter->second); }
-
- vertex_descriptor base;
- iterator iter;
-};
-
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,114 +0,0 @@
-
-#ifndef INCIDENCE_LIST_HPP
-#define INCIDENCE_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/graphs/utility.hpp>
-
-/**
- * The incidence vector stores incident "edges" of a vertex. In actuality,
- * this stores pairs containing an adjacent vertex descriptor and a property
- * descriptor, that points to the edges global properties. This pair uniquely
- * identifies incident edges of the vertex.
- *
- * This type allows constant time insertions, and linear search and remove.
- */
-template <typename Edge, typename Alloc>
-class incidence_list
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type property_descriptor;
-
- typedef std::list<Edge, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
-
- // Constructors
- incidence_list()
- : _edges(), _size(0)
- { }
-
- /** @name Add Vertex
- * Add a vertex to the list. The first version adds a stub that must be
- * bound to a property descriptor in the second phase.
- * @complexity O(1)
- */
- //@{
- inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
- { return add(v, property_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
- {
- ++_size;
- iterator i = _edges.insert(_edges.end(), make_pair(v, p));
- return make_result(make_descriptor(_edges, i));
- }
- //@}
-
- /**
- * Find the given incidence pair in the vertex.
- * @complexity O(1)
- */
- incidence_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /**
- * Remove the given incidence pair in this vertex.
- * @complexity O(deg(v))
- */
- void remove(incidence_descriptor d)
- {
- _edges.erase(make_iterator(_edges, d));
- --_size;
- }
-
- /** Remove all edges from the vertex. */
- void clear()
- {
- _size = 0;
- _edges.clear();
- }
-
- /** Return the number of edges in this store. */
- inline size_type size() const
- { return _size; }
-
- /** Return true if this is empty. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind this incident edge to the given property descriptor. */
- inline void bind(incidence_descriptor d, property_descriptor p)
- { make_iterator(_edges, d)->second = p; }
-
- /** Return the connected vertex referenced by this edge. */
- inline vertex_descriptor vertex(incidence_descriptor d) const
- { return make_iterator(_edges, d)->first; }
-
- /** Return the property referenced by this edge. */
- inline property_descriptor properties(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
- size_type _size;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_set.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,114 +0,0 @@
-
-#ifndef INCIDENCE_SET_HPP
-#define INCICENCE_SET_HPP
-
-#include <map>
-
-#include <boost/descriptors.hpp>
-
-/**
- * The incidence vector stores incident "edges" of a vertex. In actuality,
- * this stores pairs containing an adjacent vertex descriptor and a property
- * descriptor, that points to the edges global properties. This pair uniquely
- * identifies incident edges of the vertex.
- *
- * This type allows logarithmic time insertions, searches, and removals.
- */
-template <typename Edge, typename Compare, typename Alloc>
-class incidence_set
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type property_descriptor;
-
- // Actually, the incident set, as it fundamentally implements a simple
- // graph is based on a map keyed on the adjacenct vertex and mapped to the
- // edge properties that describe it. We're basically undwinding and
- // rebuilding the edge pair for this map.
- // NOTE: This can impose some difficulties since the vertex (key type) will
- // be made const in this map. That means we may have to cast out the const
- // aspect of the key at times, but changing that value would be absolutely
- // catastrophic.
- typedef std::map<vertex_descriptor, property_descriptor, Compare, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
-
- // Constructors
- inline incidence_set()
- : _edges()
- { }
-
- /** @name Add Incident Edge.
- * Try adding the incident edge to the vertex. The first version is used in
- * a two-step edge addition where the property descriptor is bound in the
- * second phase of the insertion.
- * @complexity O(lg(d))
- */
- //@{
- inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
- { return add(v, property_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
- {
- std::pair<iterator, bool> i = _edges.insert(make_pair(v, p));
- return make_result(_edges, i);
- }
- //@}
-
- /**
- * Find the incident edge whose opposite end is v.
- * @complexity O(lg(d))
- */
- incidence_descriptor find(vertex_descriptor v) const
- { return make_descriptor(_edges, _edges.find(v)); }
-
- /**
- * Remove the edge whose opposite end is v.
- * @complexity O(lg(d))
- */
- void remove(incidence_descriptor d)
- { _edges.erase(make_iterator(_edges, d)); }
-
- /** Remove all edges incident to this vertex. */
- void clear()
- { _edges.clear(); }
-
- /** Return the number of edges incident to this vertex. */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Return true if this is empty. */
- inline bool empty() const
- { return _edges.empty(); }
-
- inline bool valid(incidence_descriptor d)
- { return make_iterator(_edges, d) != _edges.end(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind this incident edge to the given property. */
- inline void bind(incidence_descriptor d, property_descriptor p)
- { make_iterator(_edges, d)->second = p; }
-
- /** Return the vertex connected by this edge. */
- inline vertex_descriptor vertex(incidence_descriptor d) const
- { return make_iterator(_edges, d)->first; }
-
- /** Return the properties connected by this edge. */
- inline property_descriptor properties(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/incidence_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,94 +0,0 @@
-
-#ifndef INCIDENCE_VECTOR
-#define INCIDENCE_VECTOR
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * The incidence vector stores incident "edges" of a vertex. In actuality,
- * this stores pairs containing an adjacent vertex descriptor and a property
- * descriptor, that points to the edges global properties. This pair uniquely
- * identifies incident edges of the vertex.
- *
- * This type allows constant-time edge addition and a linear search. Removal
- * is not supported.
- */
-template <typename Edge, typename Alloc>
-class incidence_vector
-{
-public:
- typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type property_descriptor;
-
- typedef std::vector<Edge, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type incidence_descriptor;
-
- // Constructors
- inline incidence_vector()
- : _edges()
- { }
-
- /** @name Add Edge
- * Add the incidence pair to the vector. The first version is responsible
- * for adding a "stub" that is completed later by binding a property
- * descriptor into the edge.
- */
- //@{
- inline insertion_result<incidence_descriptor> add(vertex_descriptor v)
- { return add(v, property_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, property_descriptor p)
- {
- iterator i = _edges.insert(_edges.end(), std::make_pair(v, p));
- return make_result(make_descriptor(_edges, i));
- }
- //@}
-
- /** Find the edge with the given vertex. */
- incidence_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /** Return the number of edges in this store. */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Return true if this is empty. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind this edge to the given property. */
- inline void bind(incidence_descriptor d, property_descriptor p)
- { make_iterator(_edges, d)->second = p; }
-
- /** Return the vertex connected by this edge. */
- inline vertex_descriptor vertex(incidence_descriptor d) const
- { return make_iterator(_edges, d)->first; }
-
- /** Return the properties of this edge. */
- inline property_descriptor properties(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_descriptor.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,47 +0,0 @@
-
-#ifndef OUT_DESCRIPTOR_HPP
-#define OUT_DESCRIPTOR_HPP
-
-/**
- * The out descriptor wraps an iterator into the out vector. This is primarily
- * provided to help decouple the directed edge from the underlying reference
- * to the out edge list.
- *
- * @param OutIter The pair of vertex descriptor and edge property being
- * described.
- */
-template <typename OutIter>
-struct basic_out_descriptor
-{
- typedef typename OutIter::value_type out_pair;
- typedef typename out_pair::first_type vertex_descriptor;
- typedef typename out_pair::second_type edge_properties;
-
- /** @name Constructors */
- //@{
- inline basic_out_descriptor()
- : iter()
- { }
-
- inline basic_out_descriptor(basic_out_descriptor const& x)
- : iter(x.iter)
- { }
-
- inline basic_out_descriptor(OutIter const& iter)
- : iter(iter)
- { }
- //@}
-
- inline vertex_descriptor target() const
- { return iter->first; }
-
- inline edge_properties& properties()
- { return iter->second; }
-
- inline edge_properties const& properties() const
- { return iter->second; }
-
- OutIter iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_iterator.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,88 +0,0 @@
-
-#ifndef OUT_ITERATOR_HPP
-#define OUT_ITERATOR_HPP
-
-/**
- * The out edge iterator is a wrapper around out store iterators that, when
- * dereferenced will return an edge descriptor.
- *
- * @note This is unfortunately parameterized over the entire vertex type. Why?
- * Basically because we can't tranlstate between the underlying iterator and
- * its own descriptor without access to its store. Unfortunately, the store
- * that defines the underlying iterator is buried beneath the vertex, preventing
- * easy construction from the outer graph class. Why o' why do I not have self-
- * transflating descriptors? It could greatly simplify some aspects of these
- * implementations.
- */
-template <typename Vertex, typename Edge>
-class basic_out_iterator
-{
-public:
- // Decode some type information from the wrapped out iterator.
- typedef Vertex vertex_type;
- typedef typename Vertex::out_iterator iterator;
- typedef typename iterator::value_type base_value_type;
- typedef typename boost::remove_const<typename base_value_type::first_type>::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 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()
- : vert(0), src(), iter()
- { }
-
- inline basic_out_iterator(vertex_type& vert, vertex_descriptor v, iterator x)
- : vert(&vert), src(v), iter(x)
- { }
-
- /** Return the source vertex of the iterated edge. */
- inline vertex_descriptor source() const
- { return src; }
-
- /** Return the target vertex of the iterated edge. */
- inline vertex_descriptor target() const
- { return iter->first; }
-
- /**
- * Return the "opposite" (target) vertex of the iterated edge. This is
- * provided to work with the adjacency iterator.
- */
- inline vertex_descriptor opposite() const
- { return target(); }
-
- inline basic_out_iterator& operator=(basic_out_iterator const& x)
- { vert = x.vert; src = x.src; iter = x.iter; return *this; }
-
- inline basic_out_iterator& operator++()
- { ++iter; return *this; }
-
- inline basic_out_iterator& operator--()
- { --iter; return *this; }
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(basic_out_iterator const& x) const
- { return iter == x.iter; }
-
- inline bool operator!=(basic_out_iterator const& x) const
- { return iter != x.iter; }
- //@}
-
- inline reference operator*() const
- { return Edge(source(), target(), vert->out_edge(iter)); }
-
- vertex_type* vert;
- vertex_descriptor src;
- iterator iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,126 +0,0 @@
-
-#ifndef OUT_LIST_HPP
-#define OUT_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * The out list implements list-based, out-edge storage for directed graphs.
- * out-edges are uniquely identified by their target vertex and property
- * descriptor. List-based stores support fast inserts, slow finds, but do allow
- * removals.
- *
-
- * @param Edge A tuple describing a vertex descriptor and the edge properties.
- * @param Alloc The allocator for edge pairs.
- */
-template <typename Edge, typename Alloc>
-class out_list
-{
-public:
- typedef typename Edge::first_type vertex_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;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
-
- inline out_list()
- : _edges(), _size(0)
- { }
-
- /**
- * Add the edge to the list.
- * @complexity O(1)
- */
- insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
- {
- ++_size;
- iterator i = _edges.insert(_edges.end(), std::make_pair(v, std::make_pair(ep, in_descriptor())));
- return make_result(make_descriptor(_edges, i));
- }
-
- /**
- * Remove the edge with the given vertex. Return the next iterator in
- * the sequence.
- * @complexity O(1)
- */
- iterator remove(out_descriptor d)
- {
- --_size;
- return _edges.erase(make_iterator(_edges, d));
- }
-
- /**
- * Find the edge with the given vertex.
- * @complexity O(d)
- */
- out_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /** Remove all incoming edges from the list, resetting the size to 0. */
- void clear()
- {
- _size = 0;
- _edges.clear();
- }
-
- /** Get the number of outgoing edges. */
- inline size_type size() const
- { return _size; }
-
- /** Returns true if there are not out edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
-
- /** @name Iterators and Size */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind the edge to the corresponding in edge descriptor. */
- 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& properties(out_descriptor o)
- { return make_iterator(_edges, o)->second.first; }
-
- 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 in_edge(out_descriptor o) const
- { return make_iterator(_edges, o)->second.second; }
-
- /** Return an out descriptor for the given iterator. */
- inline out_descriptor out_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
- size_type _size;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,120 +0,0 @@
-
-#ifndef OUT_SET_HPP
-#define OUT_SET_HPP
-
-#include <map>
-#include <memory>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-/**
- * The out set implements set-based, out-edge storage for directed graphs.
- * out-edges are uniquely identified by their target vertex and property
- * descriptor. List-based stores support medium inserts, mediam finds, and allow
- * removals.
- *
- * 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.
- *
- * The out edge set is actually implemented as a mapping from vertex descriptor
- * to stored 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 Compare, typename Alloc>
-class out_set
-{
-public:
- typedef typename Edge::first_type vertex_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, edge_pair, Compare, Alloc> store_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
-
- // Constructor
- inline out_set()
- : _edges()
- { }
-
- /**
- * Try to add the given edge to the set.
- * @complexity O(log(deg(v)))
- */
- insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
- {
- std::pair<iterator, bool> i = _edges.insert(std::make_pair(v, std::make_pair(ep, in_descriptor())));
- return make_result(_edges, i);
- }
-
- /**
- * Find the edge with the given vertex descriptor.
- * @complexity O(log(deg(v)))
- */
- out_descriptor find(vertex_descriptor v) const
- { return make_descriptor(_edges, _edges.find(v)); }
-
- /**
- * Remove the edge with the given vertex descriptor.
- * @complexity O(log(deg(u)))
- */
- void remove(out_descriptor d)
- { _edges.erase(make_iterator(_edges, d)); }
-
- /** Remove all edges. */
- void clear()
- { _edges.clear(); }
-
- /** Get the number of outgoing edges. */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Returns true if there are no out edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind the edge to the corresponding in edge descriptor. */
- 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& properties(out_descriptor o)
- { return make_iterator(_edges, o)->second.first; }
-
- 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 in_edge(out_descriptor o) const
- { return make_iterator(_edges, o)->second.second; }
-
- /** Return an out descriptor for the given iterator. */
- inline out_descriptor out_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,103 +0,0 @@
-
-#ifndef OUT_VECTOR_HPP
-#define OUT_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * The in/out vector implements vector-based, edge storage for directed graphs.
- * Each out edge is capable of referencing its corresponding in edge in another
- * vertex and vice-versa.
- *
- * @param Edge A tuple describing the out edge type.
- * @param Alloc The allocator for edge pairs.
- */
-template <typename Edge, typename Alloc>
-class out_vector
-{
-public:
- typedef typename Edge::first_type vertex_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;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type out_descriptor;
-
- // Constructor
- inline out_vector()
- : _edges()
- { }
-
- /**
- * Add the edge to the vector.
- * @complexity O(1)
- */
- insertion_result<out_descriptor> add(vertex_descriptor v, edge_properties const& ep)
- {
- iterator i = _edges.insert(_edges.end(), std::make_pair(v, std::make_pair(ep, in_descriptor())));
- return make_result(make_descriptor(_edges, i));
- }
-
- /** Find the edge with the given vertex. */
- out_descriptor find(vertex_descriptor v) const
- {
- iterator i = std::find_if(_edges.begin(), _edges.end(), find_first(v));
- return make_descriptor(_edges, i);
- }
-
- /** Get the number of outgoing edges. */
- inline size_type size() const
- { return _edges.size(); }
-
- /** Return true if there are no out edges. */
- inline bool empty() const
- { return _edges.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- /** Bind the edge to the corresponding in edge descriptor. */
- 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& properties(out_descriptor o)
- { return make_iterator(_edges, o)->second.first; }
-
- 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 in_edge(out_descriptor o) const
- { return make_iterator(_edges, o)->second.second; }
-
- /** Return an out descriptor for the given iterator. */
- inline out_descriptor out_edge(iterator i) const
- { return make_descriptor(_edges, i); }
-
-private:
- mutable store_type _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,139 +0,0 @@
-
-#ifndef PROPERTY_LIST_HPP
-#define PROPERTY_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * The property list implements global list of properties for node-based edge
- * storage. Note that we can get away with only a list because the edge
- * addition logic is implemented by the incidence list.
- *
- * The property store actually maintains the number of elements internally.
- * Because this store is built over a list, but only allows the insertion and
- * removal of one element at a time, we do this to optimize calls to the size()
- * function (which is used for the number of edges).
- *
- * Note that the edge pair is actually a set of descriptors into the incidence
- * lists of the vertices that reference this edge property.
- */
-template <typename Edge, typename Alloc>
-class property_list
-{
-public:
- typedef std::list<Edge, Alloc> store_type;
-
- typedef Edge edge_type;
- typedef typename Edge::first_type edge_properties;
- typedef typename Edge::second_type end_pair;
- typedef typename end_pair::first_type end_type; // same as second_type
- typedef typename end_type::first_type vertex_descriptor;
- typedef typename end_type::second_type incidence_descriptor;
-
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type property_descriptor;
-
- // Constructors.
- inline property_list()
- : _props(), _size(0)
- { }
-
- /** @name Add Property
- * Add a property tot the global set, leaving the incidence descriptors
- * empty for the time being.
- */
- //@{
- inline property_descriptor add()
- { return add(edge_properties()); }
-
- inline property_descriptor add(edge_properties const& ep)
- {
- ++_size;
- iterator i = _props.insert(_props.end(), make_pair(ep, end_pair()));
- return make_descriptor(_props, i);
- }
- //@}
-
- /**
- * Find the edge with the given properties. Finding an edge by its
- * properties is guaranteed to be O(E).
- */
- inline property_descriptor find(edge_properties const& ep) const
- {
- iterator i = std::find_if(_props.begin(), _props.end(), find_first(ep));
- return make_descriptor(_props, i);
- }
-
- /** Remove the described property from the property set. */
- inline void remove(property_descriptor d)
- {
- _props.erase(make_iterator(_props, d));
- --_size;
- }
-
- /** Return the number of properties. */
- inline size_type size() const
- { return _size; }
-
- /** Return true if this is empty. */
- inline bool empty() const
- { return _props.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _props.begin(); }
-
- inline iterator end() const
- { return _props.end(); }
- //@}
-
- /**
- * Bind vertex descriptors into the incidence lists into the global
- * property. This is the last step of edge creation for undirected graphs.
- */
- void bind(property_descriptor d, end_pair const& p)
- { make_iterator(_props, d)->second = p; }
-
- /** Return the incidence descriptors bound to the property. */
- inline end_pair const& ends(property_descriptor d) const
- { return make_iterator(_props, d)->second; }
-
- /** Return the properties referenced by the given descriptor. */
- inline edge_properties& properties(property_descriptor d)
- { return make_iterator(_props, d)->first; }
-
- /** Return the first vertex of the edge. */
- inline vertex_descriptor first_vertex(property_descriptor d) const
- { return make_iterator(_props, d)->second.first.first; }
-
- /** Return the second vertex of the edge. */
- inline vertex_descriptor second_vertex(property_descriptor d) const
- { return make_iterator(_props, d)->second.second.first; }
-
- /** Return the first incidence descriptor of the edge. */
- inline incidence_descriptor first_edge(property_descriptor d) const
- { return make_iterator(_props, d)->second.first.second; }
-
- /** Return the second incidence descriptor of the edge. */
- inline incidence_descriptor second_edge(property_descriptor d) const
- { return make_iterator(_props, d)->second.second.second; }
-
-
- /** Return a descriptor for the iterator. */
- inline property_descriptor describe(iterator i) const
- { return make_descriptor(_props, i); }
-
-private:
- mutable store_type _props;
- size_type _size;
-};
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/property_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,122 +0,0 @@
-
-#ifndef PROPERTY_VECTOR_HPP
-#define PROPERTY_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-/**
- * The property vector implements a vector-based global property store for
- * vector-based edge storage. Assuming, of course, that there are actually edge
- * properties.
- */
-template <typename Edge, typename Alloc>
-class property_vector
-{
-public:
- typedef std::vector<Edge, Alloc> store_type;
-
- typedef Edge edge_type;
- typedef typename Edge::first_type edge_properties;
- typedef typename Edge::second_type end_pair;
- typedef typename end_pair::first_type end_type; // same as second_type
- typedef typename end_type::first_type vertex_descriptor;
- typedef typename end_type::second_type incidence_descriptor;
-
- typedef typename store_type::iterator iterator;
- typedef typename store_type::size_type size_type;
-
- typedef typename descriptor_traits<store_type>::descriptor_type property_descriptor;
-
- // Constructor
- inline property_vector()
- : _props()
- { }
-
- /** @name Add Property
- * Add a property tot the global set, leaving the incidence descriptors
- * empty for the time being.
- */
- //@{
- property_descriptor add()
- { return add(edge_properties()); }
-
- property_descriptor add(edge_properties const& ep)
- {
- iterator i = _props.insert(_props.end(), make_pair(ep, end_pair()));
- return make_descriptor(_props, i);
- }
- //@}
-
- /**
- * Find the edge with the given properties. This function is guaranteed to
- * run in O(E) time.
- */
- property_descriptor find(edge_properties const& ep) const
- {
- iterator i = std::find_if(_props.begin(), _props.end(), find_first(ep));
- return make_descriptor(_props, i);
- }
-
- /** Return the number of properties in the store. */
- inline size_type size() const
- { return _props.size(); }
-
- /** Return true if this is empty. */
- inline bool empty() const
- { return _props.empty(); }
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _props.begin(); }
-
- inline iterator end() const
- { return _props.end(); }
- //@}
-
- /**
- * Bind vertex descriptors into the incidence lists into the global
- * property. This is the last step of edge creation for undirected graphs.
- */
- void bind(property_descriptor d, end_pair const& p)
- { make_iterator(_props, d)->second = p; }
-
- /** Return the properties referenced by the given descriptor. */
- inline edge_properties& properties(property_descriptor d)
- { return make_iterator(_props, d)->first; }
-
- /** Return the ends referened by the given descriptor. */
- inline end_pair const& ends(property_descriptor d) const
- { return make_iterator(_props, d)->second; }
-
- /** Return the first vertex of the edge. */
- inline vertex_descriptor first_vertex(property_descriptor d) const
- { return ends(d).first.first; }
-
- /** Return the second vertex of the edge. */
- inline vertex_descriptor second_vertex(property_descriptor d) const
- { return ends(d).second.first; }
-
- /** Return the first incidence descriptor of the edge. */
- inline incidence_descriptor first_edge(property_descriptor d) const
- { return ends(d).first.second; }
-
- /** Return the second incidence descriptor of the edge. */
- inline incidence_descriptor second_edge(property_descriptor d) const
- { return ends(d).second.second; }
-
-
- /** Return a descriptor for the iterator. */
- inline property_descriptor describe(iterator i) const
- { return make_descriptor(_props, i); }
-
-private:
- mutable store_type _props;
-};
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_edge.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,229 +0,0 @@
-
-#ifndef UNDIRECTED_EDGE_HPP
-#define UNDIRECTED_EDGE_HPP
-
-#include <iosfwd>
-
-#include <boost/unordered_pair.hpp>
-#include <boost/graphs/directional_edge.hpp>
-
-/**
- * This structure implements an unordered edge - sort of. Because the undirected
- * adjacency list class doesn't ever store a concrete edge type, this edge
- * type simply aggregates descriptors in such a way that it defines an edge.
- * This means that this class can also act (and does) as a descriptor itself.
- */
-template <typename VertexDesc, typename PropDesc>
-class undirected_edge
-{
-public:
- typedef VertexDesc vertex_descriptor;
- typedef PropDesc property_descriptor;
- typedef unordered_pair<vertex_descriptor> edge_pair;
-
- /** @name Constructors */
- //@{
- inline undirected_edge()
- : ends(), prop()
- { }
-
- inline undirected_edge(vertex_descriptor u, vertex_descriptor v, property_descriptor p)
- : ends(u, v), prop(p)
- { }
-
- inline undirected_edge(std::pair<vertex_descriptor, vertex_descriptor> const& e, property_descriptor p)
- : ends(e.first, e.second), prop(p)
- { }
-
- 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.
- * That is, it can be tested for null status (which defers to the property
- * descriptor).
- */
- //@{
- inline bool is_null() const
- { return prop.is_null(); }
-
- inline operator bool() const
- { return !is_null(); }
- //@}
-
- inline property_descriptor properties() const
- { return prop; }
-
- inline edge_pair const& edge() const
- { return ends; }
-
- /** @name End Points
- * Provide access to the end points of the undirected edge. Because the
- * ends of this edge are unordered, they do not provide a source and target
- * interface. See the rooted_undirected_edge class for a variant of this
- * type that imposes a source/target interface on these edges.
- */
- //@{
- inline vertex_descriptor first() const
- { return ends.first(); }
-
- inline vertex_descriptor second() const
- { return ends.second(); }
-
- inline vertex_descriptor opposite(vertex_descriptor v) const
- { return v == first() ? second() : first(); }
- //@}
-
- /** Return true if the edge connects the two vertices. */
- inline bool connects(vertex_descriptor u, vertex_descriptor v) const
- { 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;
-};
-
-template <typename V, typename P>
-std::ostream& operator<<(std::ostream& os, undirected_edge<V,P> const& e)
-{ return os << "{" << e.first() << " " << e.second() << "}"; }
-
-/**
- * The hash value of edges can be computed over the hash value of the property
- * descriptors. This is because the property descriptor provides a global
- * context for the edge.
- */
-template <typename V, typename P>
-inline std::size_t
-hash_value(undirected_edge<V,P> const& e)
-{
- using boost::hash;
- return hash_value(e.prop);
-}
-
-namespace detail
-{
- // Provide an implementation of directionality for undirected edges.
- template <typename Vert, typename Prop>
- struct directional_edge_adapter<undirected_edge<Vert,Prop>>
- : undirected_edge<Vert,Prop>
- {
- inline directional_edge_adapter()
- : undirected_edge<Vert, Prop>(), src()
- { }
-
- inline directional_edge_adapter(undirected_edge<Vert,Prop> e, Vert s)
- : undirected_edge<Vert,Prop>(e), src(s)
- { }
-
- inline directional_edge_adapter(Vert s, Vert t)
- : undirected_edge<Vert,Prop>(s, t), src(s)
- { }
-
- inline Vert source() const
- { return src; }
-
- inline Vert target() const
- { return this->opposite(src); }
-
- Vert src;
- };
-}
-
-/**
- * The undirected edge iterator simply wraps the iterator over the global edge
- * property store of undirected graphs.
- */
-template <typename Store, typename Edge>
-struct undirected_edge_iterator
-{
- typedef typename Store::iterator iterator;
- typedef typename Store::vertex_descriptor vertex_descriptor;
- typedef typename Store::incidence_descriptor incidence_descriptor;
- typedef typename Store::property_descriptor property_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;
-
- undirected_edge_iterator()
- : store(0), iter()
- { }
-
- undirected_edge_iterator(undirected_edge_iterator const& x)
- : store(x.store), iter(x.iter)
- { }
-
- undirected_edge_iterator(Store& store, iterator i)
- : store(&store), iter(i)
- { }
-
- inline undirected_edge_iterator& operator++()
- { ++iter; return *this; }
-
- inline undirected_edge_iterator& operator--()
- { --iter; return *this; }
-
- inline undirected_edge_iterator operator++(int)
- { undirected_edge_iterator x(*this); operator++(); return x; }
-
- inline undirected_edge_iterator operator--(int)
- { undirected_edge_iterator x(*this); operator--(); return x; }
-
- inline undirected_edge_iterator& operator+=(difference_type n)
- { iter += n; return *this; }
-
- inline undirected_edge_iterator& operator-=(difference_type n)
- { iter -= n; return *this; }
-
- /** @name Equality Comparable */
- //@{
- inline bool operator==(undirected_edge_iterator const& x) const
- { return iter == x.iter; }
-
- inline bool operator!=(undirected_edge_iterator const& x) const
- { return iter != x.iter; }
- //@{
-
- inline difference_type operator-(undirected_edge_iterator x) const
- { return iter - x.iter; }
-
- inline reference operator*() const
- {
- property_descriptor p = store->describe(iter);
- return Edge(store->first_vertex(p), store->second_vertex(p), p);
- }
-
-
- Store* store;
- iterator iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_graph.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,756 +0,0 @@
-
-#ifndef UNDIRECTED_GRAPH_HPP
-#define UNDIRECTED_GRAPH_HPP
-
-#include <boost/assert.hpp>
-#include <boost/none.hpp>
-
-#include <boost/graphs/undirected_types.hpp>
-#include <boost/graphs/adjacency_iterator.hpp>
-
-template <
- typename VertexProps,
- typename EdgeProps,
- typename VertexStore,
- typename EdgeStore>
-class undirected_graph
-{
- typedef undirected_types<VertexProps, EdgeProps, VertexStore, EdgeStore> types;
- typedef undirected_graph<VertexProps, EdgeProps, VertexStore, EdgeStore> this_type;
-public:
- typedef VertexProps vertex_properties;
- typedef EdgeProps edge_properties;
- typedef VertexStore vertex_store_selector;
- typedef EdgeStore edge_store_selector;
-
- // Underlying stores
- typedef typename types::property_store property_store;
- typedef typename types::incidence_store incidence_store;
- typedef typename types::vertex_store vertex_store;
- typedef typename types::vertex_key vertex_key;
- typedef typename types::vertex_type vertex_type;
-
- // Vertex/Property/Edge descriptors
- typedef typename types::vertex_descriptor vertex_descriptor;
- typedef typename types::edge_descriptor edge_descriptor;
- typedef typename types::property_descriptor property_descriptor;
- typedef typename types::incidence_descriptor incidence_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::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, edges, and degree.
- typedef typename types::vertices_size_type vertices_size_type;
- typedef typename types::edges_size_type edges_size_type;
- typedef typename types::incident_edges_size_type incident_edges_size_type;
-
-
- // Constructors
- undirected_graph();
-
- /** @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();
- vertex_descriptor add_vertex(vertex_properties const&);
- 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 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 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 Add Edge
- * Add an edge, connecting two vertices, to the graph. There are a number of
- * variations of this function, depending on the type of vertex store and
- * whether or not the edges are labeled. Convenience functions are provided
- * for graphs with UniqueVertices. Graphs with LabeledEdges can be added
- * with edge properties. Convenience functions are equivalent to the
- * expression add_edge(find_vertex(x), find_vertex(y), p) with x and y
- * eithe vertex proeprties or vertex keys and p optional edge properties.
- *
- * ExtendableEdgeSet add_edge(vertex_descriptor, vertex_descriptor)
- * && LabeledEdges add_edge(vertex_descriptor, vertex_descriptor, edge_properties)
- *
- * LabeledUniqueVertices add_edge(vertex_properties, vertex_properties)
- * && LabeledEdges add_edge(vertex_properties, vertex_properties, edge_properties)
- *
- * MappedUniqueVertices add_edge(vertex_key, vertex_key)
- * & LabeledEdges add_edge(vertex_key, vertex_key, edge_properties)
- */
- //@{
- // Unlabeled edge adders.
- 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&);
-
- // Labeled edge adders.
- 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 Test Edge
- * Determine if the edge, given by two vertices exists. This function a few
- * convenience overloads that depend on the type of vertex store.
- */
- //@{
- edge_descriptor edge(vertex_descriptor, vertex_descriptor) const;
- edge_descriptor edge(vertex_properties const&, vertex_properties const&) const;
- edge_descriptor edge(vertex_key const&, vertex_key const&) const;
- //@}
-
- /** @name Remove Edge(s)
- * Remove one or more edges from the graph. The function taking a single
- * edge descriptor removes exactly that edge. The fucntion(s) taking
- * a single vertex descriptor remove all edges incident to that vertex. The
- * function(s) taking two vertices remove all edges connecting the two
- * vertices.
- */
- //@{
- void remove_edge(edge_descriptor);
-
- void remove_edges(vertex_descriptor);
- void remove_edges(vertex_properties const&);
- void remove_edges(vertex_key const&);
-
- void remove_edges(vertex_descriptor, vertex_descriptor);
- void remove_edges(vertex_properties const&, vertex_properties const&);
- void remove_edges(vertex_key const&, vertex_key const&);
- //@}
-
- /** @name Size and Degree */
- //@{
- vertices_size_type num_vertices() const;
- edges_size_type num_edges() const;
- incident_edges_size_type degree(vertex_descriptor) const;
- //@}
-
- /** @name Iterators */
- //@{
- vertex_range vertices() const;
- vertex_iterator begin_vertices() const;
- vertex_iterator end_vertices() const;
-
- edge_range edges() const;
- edge_iterator begin_edges() const;
- edge_iterator end_edges() const;
-
- incident_edge_iterator begin_incident_edges(vertex_descriptor) const;
- incident_edge_iterator end_incident_edges(vertex_descriptor) const;
- incident_edge_range incident_edges(vertex_descriptor) const;
-
- adjacent_vertex_iterator begin_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_iterator end_adjacent_vertices(vertex_descriptor) const;
- adjacent_vertex_range adjacent_vertices(vertex_descriptor) const;
- //@}
-
- /** @name Property Accessors
- * Access the properties of the given vertex or edge.
- */
- //@{
- vertex_properties& operator[](vertex_descriptor);
- vertex_properties const& operator[](vertex_descriptor) const;
- edge_properties& operator[](edge_descriptor);
- edge_properties const& operator[](edge_descriptor) const;
- //@}
-
- mutable property_store _props;
- mutable vertex_store _verts;
-};
-
-#define BOOST_GRAPH_UG_PARAMS \
- typename VP, typename EP, typename VS, typename ES
-
-template <BOOST_GRAPH_UG_PARAMS>
-undirected_graph<VP,EP,VS,ES>::undirected_graph()
- : _props()
- , _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()
-{
- 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)
-{
- return _verts.add(vp);
-}
-
-/**
- * Add a new vertex with the given properties to the graph and map it to the
- * given key.
- *
- * @requires MappedUniqueVertices<Graph>
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::add_vertex(vertex_key const& k, vertex_properties const& vp)
-{
- return _verts.add(k, vp);
-}
-
-/**
- * Find the vertex with the given properties, returning a descriptor to it.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_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_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_descriptor
-undirected_graph<VP,EP,VS,ES>::find_vertex(vertex_key const& k) const
-{
- return _verts.find(k);
-}
-
-/**
- * Remove the vertex from the graph. This will disconnect the vertex from the
- * graph prior to remove.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_descriptor v)
-{
- remove_edges(v);
- _verts.remove(v);
-}
-
-/**
- * Remove the vertex from the graph identified by the given properties.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- remove_edges(vp);
- _verts.remove(vp);
-}
-
-/**
- * Remove the vertex from the graph identified by the given key.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_vertex(vertex_key const& k)
-{
- remove_edges(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_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_key const&
-undirected_graph<VP,EP,VS,ES>::key(vertex_descriptor v) const
-{
- return _verts.key(v);
-}
-
-
-/**
- * Create an edge, connecting the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
- vertex_descriptor v)
-{
- return add_edge(u, v, edge_properties());
-}
-
-/**
- * Create an edge with the given properties that connects the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_descriptor u,
- vertex_descriptor v,
- edge_properties const& ep)
-{
- // Get vertices for the descriptors
- reorder(u, v);
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Insert algorithm: Try to stub out the edge locally first. If it succeeds,
- // then add the global property, and finally bind the incidence and property
- // descitpros into their respective "slots".
- insertion_result<incidence_descriptor> first = src.connect(v);
- if(first.succeeded()) {
- // Stub the incident edge on the other vertex. Logically speaking, if
- // an edge (u, v) can be added, then (v,u) must not exist.
- insertion_result<incidence_descriptor> second = tgt.connect(u);
- BOOST_ASSERT(second.succeeded());
-
- // Add the property and bind everything together.
- property_descriptor p = _props.add(ep);
- src.bind(first.value, p);
- tgt.bind(second.value, p);
- _props.bind(p,make_pair(make_pair(u, first.value), make_pair(v, second.value)));
- return edge_descriptor(u, v, p);
- }
- else if(first.retained()) {
- property_descriptor p = src.properties(first.value);
- return edge_descriptor(u, v, p);
- }
- else {
- return edge_descriptor();
- }
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given properties. The edge is either unlabeled or has default properties.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
- vertex_properties const& v)
-{
- return add_edge(u, v, edge_properties());
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given properties and has the given edge properties.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_properties const& u,
- vertex_properties const& v,
- edge_properties const& ep)
-{
- return add_edge(find_vertex(u), find_vertex(v), ep);
-}
-
-/**
- * Add an edge to the graph that connects the two vertices identified by the
- * given keys. The edge is either unlabeled or has default properties.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::add_edge(vertex_key const& u,
- vertex_key const& v)
-{
- return add_edge(u, v, edge_properties());
-}
-
-/**
- * Determine if any edge exists connecting the vertices u and v. Return a
- * pair containing the edge descriptor (if it exists) and a bool determing
- * whether or not the edge did exist.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_descriptor u, vertex_descriptor v) const
-{
- reorder(u, v);
- vertex_type const& src = _verts.vertex(u);
- incidence_descriptor i = src.find(v);
- return i ? edge_descriptor(u, v, src.properties(i)) : edge_descriptor();
-}
-
-/**
- * Determine if any edge exists connecting the vertices identified by the given
- * properties. Return a pair containing the edge descriptor (if it exists) and
- * a bool determining whether or not the edge did exist. This is equivalent to
- * edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_properties const& u,
- vertex_properties const& v) const
-{
- return edge(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Determine if any edge exists connecting the vertices identified by the given
- * keys. Return a pair containing the edge descriptor (if it exists) and a bool
- * determining whether or not the edge did exist. This is equivalent to the
- * expression edge(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_descriptor
-undirected_graph<VP,EP,VS,ES>::edge(vertex_key const& u,
- vertex_key const& v) const
-{
- return edge(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Remove only the given edge from graph. This disconnects both vertices in
- * the edge and removes the property from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edge(edge_descriptor e)
-{
- // Grab descriptors out of the edge.
- property_descriptor p = e.properties();
- vertex_descriptor u = e.first(), v = e.second();
- vertex_type &src = _verts.vertex(u), &tgt = _verts.vertex(v);
-
- // Get incidence iterators from the property and arranging them to match
- // their owning vertices.
- incidence_descriptor i = _props.first_edge(p), j = _props.second_edge(p);
- if(src.opposite(i) == v) {
- i.swap(j);
- }
-
- // Disconnect the incidence ends and then remove the property from the
- // global property store.
- src.disconnect(j);
- tgt.disconnect(i);
- _props.remove(p);
-}
-
-/**
- * Remove all edges incident to the given vertex, effectively disconnecting
- * it from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
-{
- vertex_type& src = _verts.vertex(v);
-
- // Start by disconnecting all of the incident edges from adjacent vertices.
- incident_edge_range rng = incident_edges(v);
- for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
- edge_descriptor e = *i;
- vertex_type& tgt = _verts.vertex(e.opposite(v));
-
- // Get an incidence descriptor into the target into tgt's edge store,
- // so we can remove the edge record and the properties of the removed
- // edge.
- property_descriptor p = e.properties();
- std::pair<incidence_descriptor, incidence_descriptor> x =
- std::make_pair(_props.first_edge(p), _props.second_edge(p));
- if(src.opposite(x.first) != v) {
- x.first.swap(x.second);
- }
- tgt.disconnect(x.first);
- _props.remove(e.properties());
- }
-
- // Clear the incident edge set of the vertex. We can't do this in the
- // previous loop because it will invalidate the our iterators.
- src.clear();
-}
-
-/**
- * Disconnect the vertex having the given properties from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& vp)
-{
- BOOST_STATIC_ASSERT(is_not_none<vertex_properties>::value);
- remove_edges(find_vertex(vp));
-}
-
-/**
- * Disconnect the vertex having the given key from the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& k)
-{
- remove_edges(find_vertex(k));
-}
-
-/**
- * Remove all edges connecting the vertices u and v.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor u,
- vertex_descriptor v)
-{
- // Canonicalize the ordering of vertices first and the get the vertices.
- reorder(u, v);
- vertex_type& src = _verts.vertex(u);
- vertex_type& tgt = _verts.vertex(v);
-
- // Iterate over the incident edges of the source vertex. If we the edge
- // (u, *i) is the same as (u, v), then we need to remove that edge. We
- // also have to cache these iterators and remove them in a second pass.
- std::vector<incidence_descriptor> iters;
- incident_edge_range rng = incident_edges(u);
- for(incident_edge_iterator i = rng.first ; i != rng.second; ++i) {
- edge_descriptor e = *i;
- vertex_descriptor o = e.opposite(u);
- if(o == v) {
- // Grab descriptors to the property and the incident edge on the
- // target vertex and remove them,
- property_descriptor p = e.properties();
- pair<incidence_descriptor, incidence_descriptor> x =
- make_pair(_props.first_edge(p), _props.second_edge(p));
- if(src.opposite(x.first) == v) {
- x.first.swap(x.second);
- }
- tgt.disconnect(x.first);
- _props.remove(p);
-
- // Stash the iterator for the second pass.
- iters.push_back(x.second);
- }
- }
-
- // Second pass: disconnect all of the incident edges from src.
- typename std::vector<incidence_descriptor>::iterator i, end = iters.end();
- for(i = iters.begin(); i != end; ++i) {
- src.disconnect(*i);
- }
-}
-
-/**
- * Remove all edges connecting the vertices identified by the given properties.
- * This is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_properties const& u,
- vertex_properties const& v)
-{
- return remove_edges(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Remove all edges connecting the vertices identified by the given keys. This
- * is equivalent to remove_edges(find_vertex(u), find_vertex(v)).
- */
-template <BOOST_GRAPH_UG_PARAMS>
-void
-undirected_graph<VP,EP,VS,ES>::remove_edges(vertex_key const& u,
- vertex_key const& v)
-{
- return remove_edges(find_vertex(u), find_vertex(v));
-}
-
-/**
- * Return an iterator range over the vertices of the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_range
-undirected_graph<VP,EP,VS,ES>::vertices() const
-{
- return _verts.vertices();
-}
-
-/**
- * Return an iterator to the first iterator in the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
-undirected_graph<VP,EP,VS,ES>::begin_vertices() const
-{
- return _verts.begin_vertices();
-}
-
-/**
- * Return an iterator past the end of the vertices in the graph.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_iterator
-undirected_graph<VP,EP,VS,ES>::end_vertices() const
-{
- return _verts.end_vertices();
-}
-
-/** Return an iterator to the first edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_iterator
-undirected_graph<VP,EP,VS,ES>::begin_edges() const
-{ return edge_iterator(_props, _props.begin()); }
-
-/** Return an iterator past the end of the edges. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_iterator
-undirected_graph<VP,EP,VS,ES>::end_edges() const
-{ return edge_iterator(_props, _props.end()); }
-
-/** Return an iterator range over the edges in the graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_range
-undirected_graph<VP,EP,VS,ES>::edges() const
-{ return std::make_pair(begin_edges(), end_edges()); }
-
-/** Return the number of iterators in this graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertices_size_type
-undirected_graph<VP,EP,VS,ES>::num_vertices() const
-{ return _verts.size(); }
-
-/** Return the number of edges in this graph. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edges_size_type
-undirected_graph<VP,EP,VS,ES>::num_edges() const
-{ return _props.size(); }
-
-/** Return an iterator to the first incident edge of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
-undirected_graph<VP,EP,VS,ES>::begin_incident_edges(vertex_descriptor v) const
-{ return incident_edge_iterator(v, _verts.vertex(v).begin()); }
-
-/** Return an iterator past the end of the incident edges of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_iterator
-undirected_graph<VP,EP,VS,ES>::end_incident_edges(vertex_descriptor v) const
-{ return incident_edge_iterator(v, _verts.vertex(v).end()); }
-
-/** Return an iterator range over the incident edges of the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edge_range
-undirected_graph<VP,EP,VS,ES>::incident_edges(vertex_descriptor v) const
-{ return make_pair(begin_incident_edges(v), end_incident_edges(v)); }
-
-/**
- * Return an iterator to the first adjacent vertex of the the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-undirected_graph<VP,EP,VS,ES>::begin_adjacent_vertices(vertex_descriptor v) const
-{
- return begin_incident_edges(v);
-}
-
-/**
- * Return an iterator past the end of the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_iterator
-undirected_graph<VP,EP,VS,ES>::end_adjacent_vertices(vertex_descriptor v) const
-{
- return end_incident_edges(v);
-}
-
-/**
- * Return an iterator range over the adjacent vertices of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::adjacent_vertex_range
-undirected_graph<VP,EP,VS,ES>::adjacent_vertices(vertex_descriptor v) const
-{
- return std::make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v));
-}
-
-
-/**
- * Return the degree (number of incdent edges) of the given vertex.
- */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::incident_edges_size_type
-undirected_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_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_properties&
-undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v)
-{ return _verts.properties(v); }
-
-/** Return the properties for the given vertex. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::vertex_properties const&
-undirected_graph<VP,EP,VS,ES>::operator[](vertex_descriptor v) const
-{ return _verts.properties(v); }
-
-/** Return the properties for the given edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_properties&
-undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e)
-{ return _props.properties(e.properties()); }
-
-/** Return the properties for the given edge. */
-template <BOOST_GRAPH_UG_PARAMS>
-typename undirected_graph<VP,EP,VS,ES>::edge_properties const&
-undirected_graph<VP,EP,VS,ES>::operator[](edge_descriptor e) const
-{ return _props.properties(e.properties()); }
-
-#undef BOOST_GRAPH_UG_PARAMS
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_types.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,74 +0,0 @@
-
-#ifndef UNDIRECTED_TYPES_HPP
-#define UNDIRECTED_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/property_vector.hpp>
-#include <boost/graphs/property_list.hpp>
-#include <boost/graphs/incidence_vector.hpp>
-#include <boost/graphs/incidence_list.hpp>
-#include <boost/graphs/incidence_set.hpp>
-#include <boost/graphs/incidence_iterator.hpp>
-
-// Vertex and Edge components
-#include <boost/graphs/undirected_vertex.hpp>
-#include <boost/graphs/undirected_edge.hpp>
-
-// Adjacency components
-#include <boost/graphs/adjacency_iterator.hpp>
-
-using namespace std;
-
-/**
- * This class is a giant metafunction that generates the types required to
- * implement an undirected gaph.
- */
-template <typename VertexProps, typename EdgeProps, typename VertexStore, typename EdgeStore>
-struct undirected_types
-{
- // Generate descriptors.
- typedef typename VertexStore::vertex_descriptor vertex_descriptor;
- typedef typename EdgeStore::property_descriptor property_descriptor;
- typedef typename EdgeStore::incidence_descriptor incidence_descriptor;
-
- // Generate the property store and related types.
- typedef typename EdgeStore::template property_store<vertex_descriptor, EdgeProps>::type property_store;
- typedef typename property_store::size_type edges_size_type;
-
- // Generate stuff related to edges
- typedef undirected_edge<vertex_descriptor, property_descriptor> edge_descriptor;
- typedef undirected_edge_iterator<property_store, edge_descriptor> edge_iterator;
- typedef std::pair<edge_iterator, edge_iterator> edge_range;
-
- // Generate the incidence store type.
- typedef typename EdgeStore::template incidence_store<vertex_descriptor>::type incidence_store;
- typedef typename incidence_store::size_type incident_edges_size_type;
- typedef incidence_iterator<typename incidence_store::iterator, edge_descriptor> incident_edge_iterator;
- typedef std::pair<incident_edge_iterator, incident_edge_iterator> incident_edge_range;
-
- // Generate the vertex type and its store and key type.
- typedef undirected_vertex<VertexProps, incidence_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 VertexStore::key_type vertex_key;
-
- // Generate the adjacency iterator
- typedef adjacency_iterator<incident_edge_iterator> adjacent_vertex_iterator;
- typedef std::pair<adjacent_vertex_iterator, adjacent_vertex_iterator> adjacent_vertex_range;
-
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/undirected_vertex.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,108 +0,0 @@
-
-#ifndef UNDIRECTED_VERTEX_HPP
-#define UNDIRECTED_VERTEX_HPP
-
-#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
- * list.
- *
- * For directed graphs, it's basically the same, but has an out edge
- * list and/or an in edge list, and the edge properties are stored on
- * the out edge list.
- * The default comparison of vertices always delegates the comparison to the
- * stored vertex properties. This allows developers to express custom
- * comparitors with respect to the properties and have the vertex sets or other
- * vertex ordering operations work as they might expect.
- *
- * @requires LessThanComparable<vertex_properties>.
- */
-template <typename VertexProps, typename IncStore>
-class undirected_vertex
-{
-public:
- typedef VertexProps vertex_properties;
-
- typedef IncStore incidence_store;
- typedef typename incidence_store::incidence_descriptor incidence_descriptor;
- typedef typename incidence_store::vertex_descriptor vertex_descriptor;
- typedef typename incidence_store::property_descriptor property_descriptor;
- typedef typename incidence_store::iterator iterator;
- typedef typename incidence_store::size_type size_type;
-
- inline undirected_vertex()
- : _props(), _edges()
- { }
-
- inline undirected_vertex(vertex_properties const& vp)
- : _props(vp), _edges()
- { }
-
- /** @name Edge Connection and Disconnection
- * These functions control how edges are added to and removed from the
- * vertex.
- */
- //@{
- inline insertion_result<incidence_descriptor> connect(vertex_descriptor v)
- { return _edges.add(v); }
-
- inline void bind(incidence_descriptor i, property_descriptor p)
- { _edges.bind(i, p); }
-
- inline void disconnect(incidence_descriptor i)
- { _edges.remove(i); }
-
- /** Find an incident edge connecting this to the given vertex. */
- inline incidence_descriptor find(vertex_descriptor v) const
- { return _edges.find(v); }
- //@}
-
- /** Return the properties of the given incident edge. */
- inline property_descriptor properties(incidence_descriptor i) const
- { return _edges.properties(i); }
-
- inline vertex_descriptor opposite(incidence_descriptor i) const
- { return _edges.vertex(i) ;}
-
-
- /** @name Property Accessors */
- //@{
- inline vertex_properties& properties()
- { return _props; }
-
- inline vertex_properties const& properties() const
- { return _props; }
- //@}
-
- /** @name Iterators */
- //@{
- inline iterator begin() const
- { return _edges.begin(); }
-
- inline iterator end() const
- { return _edges.end(); }
- //@}
-
- inline void clear()
- { _edges.clear(); }
-
- 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); }
-
- inline bool operator<(undirected_vertex const& x) const
- { return _props < x._props; }
-
-private:
- vertex_properties _props;
- incidence_store _edges;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_iterator.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,76 +0,0 @@
-
-#ifndef VERTEX_ITERATOR_HPP
-#define VERTEX_ITERATOR_HPP
-
-#include <boost/descriptors.hpp>
-
-/**
- * A simple vertex iterator for any underlying store. These iterators must
- * cache references to the originating container because these dereference to
- * descriptors.
- */
-template <typename Container>
-class basic_vertex_iterator
-{
-public:
- typedef typename Container::iterator iterator;
- typedef typename Container::value_type vertex_type;
- typedef typename descriptor_traits<Container>::descriptor_type vertex_descriptor;
-
- typedef typename iterator::iterator_category iterator_category;
- typedef typename iterator::difference_type difference_type;
- typedef vertex_descriptor value_type;
- typedef vertex_descriptor reference;
- typedef vertex_descriptor pointer;
-
- inline basic_vertex_iterator()
- : cont(0), iter()
- { }
-
- inline basic_vertex_iterator(Container& c, iterator x)
- : cont(&c), iter(x)
- { }
-
- // Assignment and increment
- inline basic_vertex_iterator& operator+=(difference_type n)
- { iter += n; return *this; }
-
- inline basic_vertex_iterator& operator-=(difference_type n)
- { iter -= n; return *this; }
-
- inline basic_vertex_iterator& operator++()
- { ++iter; return *this; }
-
- inline basic_vertex_iterator& operator--()
- { --iter; return *this; }
-
- inline basic_vertex_iterator operator++(int)
- { basic_vertex_iterator x(*this); ++iter; return x; }
-
- inline basic_vertex_iterator operator--(int)
- { basic_vertex_iterator x(*this); --iter; return x; }
-
- inline basic_vertex_iterator operator+(difference_type n) const
- { return indexed_basic_vertex_iterator(cont, iter + n); }
-
- inline basic_vertex_iterator operator-(difference_type n) const
- { return indexed_basic_vertex_iterator(cont, iter -n); }
-
- inline difference_type operator-(basic_vertex_iterator const& x) const
- { return iter - x.iter; }
-
- inline reference operator*() const
- { return make_descriptor(*cont, iter); }
-
- inline bool operator==(basic_vertex_iterator const& x) const
- { return iter == x.iter; }
-
- inline bool operator!=(basic_vertex_iterator const& x) const
- { return iter != x.iter; }
-
-private:
- Container* cont;
- iterator iter;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_list.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,149 +0,0 @@
-
-#ifndef VERTEX_LIST_HPP
-#define VERTEX_LIST_HPP
-
-#include <list>
-
-#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
-
-#include <boost/graphs/vertex_iterator.hpp>
-
-// Forward declarations
-template <typename, typename> class vertices_list;
-
-/**
- * This metafunction defines the basic elements of a vertex list.
- */
-template <template <typename> class Alloc = std::allocator>
-struct vertex_list
-{
- typedef unused key_type;
-
- typedef std::list<int, Alloc<int>> dummy;
- typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
-
- template <typename Vertex>
- struct store
- {
- typedef vertices_list<Vertex, Alloc<Vertex>> type;
- };
-};
-
-/**
- * The implementation of the vertex list.
- *
- * @param Vertex The type of stored vertex.
- * @param Alloc The allocator for stored vertices.
- */
-template <typename Vertex, typename Alloc>
-class vertices_list
-{
-public:
- typedef std::list<Vertex, Alloc> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_properties vertex_properties;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- // Constructors
- inline vertices_list()
- : _verts(), _size(0)
- { }
-
- /** @name Add Vertex
- * Add a vertex to the store with the given properties (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- //@{
- inline vertex_descriptor add()
- { return add(vertex_properties()); }
-
- inline vertex_descriptor add(vertex_properties const& vp)
- {
- ++_size;
- iterator i = insert(_verts, vertex_type(vp));
- return make_descriptor(_verts, i);
- }
- //@}
-
- /** Find the vertex with the given properties. */
- inline vertex_descriptor find(vertex_properties const& vp)
- {
- iterator i = std::find_if(_verts.begin(), _verts.end(), find_properties(vp));
- return make_descriptor(_verts, i);
- }
-
- /** @name Remove Vertex
- * Remove the given vertex from the vertex store. This will probably break
- * if the descriptor is invalid.
- */
- //@{
- inline void remove(vertex_descriptor v)
- {
- erase(_verts, make_iterator(_verts, v));
- --_size;
- }
-
- inline void remove(vertex_properties const& vp)
- { remove(find(vp)); }
- //@}
-
- /** Return the number of vertices in the set. */
- inline size_type size() const
- { return _size; }
-
- /** @name Vertex Iterators
- * There are two sets of iterators here: those that provide iterators that
- * dereference as descriptors and those that dereference as vertices.
- */
- //@{
- inline vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- inline vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- inline vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return *make_iterator(_verts, v); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Vertex Properties */
- //@{
- vertex_properties& properties(vertex_descriptor v)
- { return vertex(v).properties(); }
-
- vertex_properties const& properties(vertex_descriptor v) const
- { return vertex(v).properties(); }
- //@}
-
-private:
- mutable store_type _verts;
- size_type _size;
-};
-
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_map.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,155 +0,0 @@
-
-#ifndef VERTEX_MAP_HPP
-#define VERTEX_MAP_HPP
-
-#include <map>
-
-#include <boost/descriptors.hpp>
-
-#include <boost/graphs/vertex_iterator.hpp>
-
-// Forward declarations
-template <typename, typename, typename, typename> class vertices_map;
-
-/**
- * This metafunction defines the implementation requirements of a mapping of
- * vertices to the keys that describe them. This is function takes three
- * parameters: the type of key, a comparator template, and vertex allocator.
- *
- * The Compare parameter must be a unary template class rather than a fully
- * instantiated type. This makes it easier to pass arbitrary template functions
- * (e.g., less and greater) instead of instantiated types.
- *
- * The Alloc parameter is also a unary template class. In this case, the caller
- * does not know the final type of the allocator object. It us ultimately
- * instantiated as an allocator of key/vertex pairs.
- *
- * @param Key The key type of the vertex map can be any LessThanComparable type.
- * @param Compare A unary template class that implements a comparison of keys.
- * @param Alloc An allocator for key/value pairs of the underliyng map.
- */
-template <
- typename Key,
- template <typename> class Compare = std::less,
- template <typename> class Alloc = std::allocator>
-struct vertex_map
-{
- typedef Key key_type;
-
- typedef std::map<Key, int, Compare<Key>, Alloc<std::pair<Key, int>>> dummy;
- typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
-
- template <typename Vertex>
- struct store
- {
- typedef Alloc<std::pair<Key, Vertex>> allocator;
- typedef Compare<Key> compare;
- typedef vertices_map<Vertex, Key, compare, allocator> type;
- };
-};
-
-/**
- * Implementation of the vertex set. This requires that vertices (actually
- * their properties) are less-than comparable.
- *
- * @param Vertex The vertex type stored by the class.
- * @param Key The type of key mapping to vertices.
- * @param Compare An ordering over keys.
- * @param Alloc The allocator for Key/Vertex pairs.
- */
-template <typename Vertex, typename Key, typename Compare, typename Allocator>
-class vertices_map
-{
-public:
- typedef std::map<Key, Vertex, Compare, Allocator> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
-
- typedef Key key_type;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_properties vertex_properties;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- inline vertices_map()
- : _verts()
- { }
-
- /**
- * Add a vertex to the store mapped to the given key, and having the given
- * properties.
- */
- inline vertex_descriptor add(key_type const& k, vertex_properties const& vp)
- { return make_descriptor(_verts, _verts.insert(std::make_pair(k, vp)).first); }
-
- /**
- * Find the vertex mapped to the given key and return a descriptor to it.
- */
- inline vertex_descriptor find(key_type const& k) const
- { return make_descriptor(_verts, _verts.find(k)); }
-
- /** @name Remove Vertex
- * Remove the vertex identified by the descriptor or the its properties.
- */
- //@{
- inline void remove(vertex_descriptor d)
- { _verts.erase(make_iterator(_verts, d)); }
-
- inline void remove(key_type const& k)
- { _verts.erase(_verts.find(k)); }
- //@}
-
- /** Return the number of vertices in the map. */
- inline size_type size() const
- { return _verts.size(); }
-
- /** @name Vertex Iteration */
- //@{
- inline vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- inline vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
- /** @name Vertex and Key Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return make_iterator(_verts, v)->second; }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return make_iterator(_verts, v)->second; }
-
- key_type const& key(vertex_descriptor d) const
- { return make_iterator(_verts, d)->first; }
- //@}
-
- /** @name Property Accessors */
- //@{
- vertex_properties& properties(vertex_descriptor v)
- { return vertex(v).properties(); }
-
- vertex_properties const& properties(vertex_descriptor v) const
- { return vertex(v).properties(); }
- //@}
-
-private:
- mutable store_type _verts;
-};
-
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multimap.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_set.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,150 +0,0 @@
-
-#ifndef VERTEX_SET_HPP
-#define VERTEX_SET_HPP
-
-#include <set>
-
-#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
-
-#include <boost/graphs/utility.hpp>
-#include <boost/graphs/vertex_iterator.hpp>
-
-// Forward declarations
-template <typename, typename, typename> class vertices_set;
-
-/**
- * This metafunction defines the implementation requirements of a set of
- * vertices. This function allos the parameterization of vertex comparability
- * by allowing the caller to specify the comparator.
- *
- * The Compare parameter must be a unary template class. This lets us specify
- * arbitrary function objects by name without having to explicitly instantiate
- * them.
- *
- * The Alloc parameter is also a unary template class. In this case, the caller
- * does not actually know what the final instantiated type is going to be.
- *
- * @param Compare A unary template class that compares vertex properties.
- * @param Alloc A unary template class that allocates vertices.
- */
-template <
- template <typename> class Compare = std::less,
- template <typename> class Alloc = std::allocator>
-struct vertex_set
-{
- typedef unused key_type;
-
- typedef std::set<int, Compare<int>, Alloc<int>> dummy;
- typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
-
- // This metafunction generates the underlying vertex store implementation.
- template <typename Vertex>
- struct store
- {
- typedef Alloc<Vertex> allocator;
- typedef property_comparator<Compare<typename Vertex::vertex_properties>> compare;
- typedef vertices_set<Vertex, compare, allocator> type;
- };
-};
-
-
-/**
- * Implementation of the vertex set. This requires that vertices (actually
- * their properties) are less-than comparable.
- *
- * @param Vertex The type of vertex stored by the set.
- * @param Compare An ordering of vertices (should delegate to properties).
- * @param Allocator The allocator for stored vertices.
- */
-template <typename Vertex, typename Compare, typename Allocator>
-class vertices_set
-{
-public:
- typedef std::set<Vertex, Compare, Allocator> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_properties vertex_properties;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- inline vertices_set()
- : _verts()
- { }
-
- /**
- * Add a vertex to the store with the given properties (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- inline vertex_descriptor add(vertex_properties const& vp)
- { return make_descriptor(_verts, insert(_verts, vertex_type(vp))); }
-
- /** Find the vertex with the given properties. */
- inline vertex_descriptor find(vertex_properties const& vp) const
- { return make_descriptor(_verts, _verts.find(vp)); }
-
- /** @name Remove Vertex
- * Remove the given vertex or the one identified by the given properties.
- */
- //@{
- inline void remove(vertex_descriptor v)
- {
- iterator i = make_iterator(_verts, v);
- erase(_verts, make_iterator(_verts, v));
- }
-
- inline void remove(vertex_properties const& v)
- { remove(find(v)); }
- //@}
-
- /** Return the number of vertices in the set. */
- inline size_type size() const
- { return _verts.size(); }
-
- /** @name Vertex Iteration */
- //@{
- inline vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- inline vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return const_cast<vertex_type&>(*make_iterator(_verts, v)); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Property Accessors */
- //@{
- vertex_properties& properties(vertex_descriptor v)
- { return vertex(v).properties(); }
-
- vertex_properties const& properties(vertex_descriptor v) const
- { return vertex(v).properties(); }
- //@{
-
-private:
- mutable store_type _verts;
-};
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/vertex_vector.hpp 2008-08-08 10:21:09 EDT (Fri, 08 Aug 2008)
+++ (empty file)
@@ -1,149 +0,0 @@
-
-#ifndef VERTEX_VECTOR_HPP
-#define VERTEX_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/none.hpp>
-#include <boost/descriptors.hpp>
-
-#include <boost/graphs/utility.hpp>
-#include <boost/graphs/vertex_iterator.hpp>
-
-// Forward declarations
-template <typename, typename> struct vertices_vector;
-
-/**
- * The vertex vector stores vertices in a vector, allowing for fast inserts
- * and iteration, but slow finds and removals.
- *
- * The Alloc parameter is a unary template class responsible for allocating
- * the stored vertices. We use a template rather than a type because the caller
- * does not know the actual types being allocated.
- *
- * @param Alloc A unary template class that will allocate stored vertices.
- */
-template <template <typename> class Alloc = std::allocator>
-struct vertex_vector
-{
- typedef unused key_type;
-
- typedef std::vector<int, Alloc<int>> dummy;
- typedef typename descriptor_traits<dummy>::descriptor_type vertex_descriptor;
-
- // 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
- {
- typedef Alloc<Vertex> allocator;
- typedef vertices_vector<Vertex, allocator> type;
- };
-};
-
-/**
- * The vertex_vector template implements veretex storage for adjacency lists
- * as a vector. This essentially provides a heavily constrained interface
- * to the underlying vector. Note that many operations normally supported by
- * a vector are not allowed with graphs.
- *
- * Adding vertices does not invalidate descriptors, but may result in the
- * reallocation of the underlying store. However, removing vertices could
- * corrupt the entire graph (since indices are adjusted). As a result, this
- * store type does not provide remove operations.
- */
-template <typename Vertex, typename Allocator>
-class vertices_vector
-{
-public:
- typedef std::vector<Vertex, Allocator> store_type;
- typedef typename store_type::size_type size_type;
- typedef typename store_type::iterator iterator;
-
- typedef Vertex vertex_type;
- typedef typename Vertex::vertex_properties vertex_properties;
-
- typedef typename descriptor_traits<store_type>::descriptor_type vertex_descriptor;
-
- typedef basic_vertex_iterator<store_type> vertex_iterator;
- typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
-
- // Constructors
- inline vertices_vector()
- : _verts()
- { }
-
- /** @name Add Vertex
- * Add a vertex to the store with the given properties (or none). Return
- * a descriptor to the vertex that was added to the vector.
- */
- //@{
- inline vertex_descriptor add()
- { return add(vertex_properties()); }
-
- inline vertex_descriptor add(vertex_properties const& vp)
- {
- iterator i = insert(_verts, vertex_type(vp));
- return make_descriptor(_verts, i);
- }
- //@}
-
- /**
- * Return a descriptor to the vertex with the given properties. If you
- * end up calling this function, you're probably using the wrong graph
- * type.
- */
- vertex_descriptor find(vertex_properties const& vp) const
- {
- iterator i = std::find_if(_verts.begin(), _verts.end(), find_properties(vp));
- return make_descriptor(_verts, i);
- }
-
- /** Rerturn the number of vertices in the vector. */
- size_type size() const
- { return _verts.size(); }
-
- /** @name Vertex Iterators */
- //@{
- vertex_iterator begin_vertices() const
- { return vertex_iterator(_verts, _verts.begin()); }
-
- vertex_iterator end_vertices() const
- { return vertex_iterator(_verts, _verts.end()); }
-
- vertex_range vertices() const
- { return std::make_pair(begin_vertices(), end_vertices()); }
-
- inline typename store_type::iterator begin() const
- { return _verts.begin(); }
-
- inline iterator end() const
- { return _verts.end(); }
- //@}
-
-
- /** @name Vertex Accessors */
- //@{
- vertex_type& vertex(vertex_descriptor v)
- { return *make_iterator(_verts, v); }
-
- vertex_type const& vertex(vertex_descriptor v) const
- { return *make_iterator(_verts, v); }
- //@}
-
- /** @name Property Accessors */
- //@{
- vertex_properties& properties(vertex_descriptor v)
- { return vertex(v).properties(); }
-
- vertex_properties const& properties(vertex_descriptor v) const
- { return vertex(v).properties(); }
- //@}
-
-private:
- mutable store_type _verts;
-};
-
-#endif
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk