[Boost-commit] svn:boost r50035 - sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list

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
-