Subject: [Boost-commit] svn:boost r50035 - sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list
From: asutton_at_[hidden]
Date: 2008-11-30 08:34:33
Author: asutton
Date: 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
New Revision: 50035
URL: http://svn.boost.org/trac/boost/changeset/50035
Log:
Removing old files
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_list.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_multiset.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_set.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_vector.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_list.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_vector.hpp
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_list.hpp 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
+++ (empty file)
@@ -1,118 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_INCIDENCE_LIST_HPP
-#define BOOST_GRAPHS_ADJLIST_INCIDENCE_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/graphs/utility.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * 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 label. 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 label_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, label_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, label_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, label_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 label_descriptor label(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
- size_type _size;
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_set.hpp 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
+++ (empty file)
@@ -1,118 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_INCIDENCE_SET_HPP
-#define BOOST_GRAPHS_ADJLIST_INCIDENCE_SET_HPP
-
-#include <map>
-
-#include <boost/descriptors.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * 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 label. 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 label_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 label 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, label_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, label_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, label_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, label_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 label connected by this edge. */
- inline label_descriptor label(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/incidence_vector.hpp 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
+++ (empty file)
@@ -1,98 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_INCIDENCE_VECTOR_HPP
-#define BOOST_GRAPHS_ADJLIST_INCIDENCE_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * 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 label. 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 label_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, label_descriptor()); }
-
- insertion_result<incidence_descriptor> add(vertex_descriptor v, label_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, label_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 label of this edge. */
- inline label_descriptor label(incidence_descriptor d) const
- { return make_iterator(_edges, d)->second; }
-
-private:
- mutable store_type _edges;
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_list.hpp 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
+++ (empty file)
@@ -1,143 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_PROPERTY_LIST_HPP
-#define BOOST_GRAPHS_ADJLIST_PROPERTY_LIST_HPP
-
-#include <list>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * The property list implements global list of label 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_label;
- 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 label_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 label_descriptor add()
- { return add(edge_label()); }
-
- inline label_descriptor add(edge_label 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 label. Finding an edge by its
- * label is guaranteed to be O(E).
- */
- inline label_descriptor find(edge_label 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(label_descriptor d)
- {
- _props.erase(make_iterator(_props, d));
- --_size;
- }
-
- /** Return the number of label. */
- 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(label_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(label_descriptor d) const
- { return make_iterator(_props, d)->second; }
-
- /** Return the label referenced by the given descriptor. */
- inline edge_label& label(label_descriptor d)
- { return make_iterator(_props, d)->first; }
-
- /** Return the first vertex of the edge. */
- inline vertex_descriptor first_vertex(label_descriptor d) const
- { return make_iterator(_props, d)->second.first.first; }
-
- /** Return the second vertex of the edge. */
- inline vertex_descriptor second_vertex(label_descriptor d) const
- { return make_iterator(_props, d)->second.second.first; }
-
- /** Return the first incidence descriptor of the edge. */
- inline incidence_descriptor first_edge(label_descriptor d) const
- { return make_iterator(_props, d)->second.first.second; }
-
- /** Return the second incidence descriptor of the edge. */
- inline incidence_descriptor second_edge(label_descriptor d) const
- { return make_iterator(_props, d)->second.second.second; }
-
-
- /** Return a descriptor for the iterator. */
- inline label_descriptor describe(iterator i) const
- { return make_descriptor(_props, i); }
-
-private:
- mutable store_type _props;
- size_type _size;
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/property_vector.hpp 2008-11-30 08:34:32 EST (Sun, 30 Nov 2008)
+++ (empty file)
@@ -1,126 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_PROPERTY_VECTOR_HPP
-#define BOOST_GRAPHS_ADJLIST_PROPERTY_VECTOR_HPP
-
-#include <vector>
-#include <algorithm>
-
-#include <boost/descriptors.hpp>
-#include <boost/graphs/utility.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-/**
- * The property vector implements a vector-based global property store for
- * vector-based edge storage. Assuming, of course, that there are actually edge
- * label.
- */
-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_label;
- 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 label_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.
- */
- //@{
- label_descriptor add()
- { return add(edge_label()); }
-
- label_descriptor add(edge_label const& ep)
- {
- iterator i = _props.insert(_props.end(), make_pair(ep, end_pair()));
- return make_descriptor(_props, i);
- }
- //@}
-
- /**
- * Find the edge with the given label. This function is guaranteed to
- * run in O(E) time.
- */
- label_descriptor find(edge_label const& ep) const
- {
- iterator i = std::find_if(_props.begin(), _props.end(), find_first(ep));
- return make_descriptor(_props, i);
- }
-
- /** Return the number of label 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(label_descriptor d, end_pair const& p)
- { make_iterator(_props, d)->second = p; }
-
- /** Return the label referenced by the given descriptor. */
- inline edge_label& label(label_descriptor d)
- { return make_iterator(_props, d)->first; }
-
- /** Return the ends referened by the given descriptor. */
- inline end_pair const& ends(label_descriptor d) const
- { return make_iterator(_props, d)->second; }
-
- /** Return the first vertex of the edge. */
- inline vertex_descriptor first_vertex(label_descriptor d) const
- { return ends(d).first.first; }
-
- /** Return the second vertex of the edge. */
- inline vertex_descriptor second_vertex(label_descriptor d) const
- { return ends(d).second.first; }
-
- /** Return the first incidence descriptor of the edge. */
- inline incidence_descriptor first_edge(label_descriptor d) const
- { return ends(d).first.second; }
-
- /** Return the second incidence descriptor of the edge. */
- inline incidence_descriptor second_edge(label_descriptor d) const
- { return ends(d).second.second; }
-
-
- /** Return a descriptor for the iterator. */
- inline label_descriptor describe(iterator i) const
- { return make_descriptor(_props, i); }
-
-private:
- mutable store_type _props;
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
-