[Boost-commit] svn:boost r53556 - in trunk/boost/graph: . detail

Subject: [Boost-commit] svn:boost r53556 - in trunk/boost/graph: . detail
From: asutton_at_[hidden]
Date: 2009-06-01 17:44:36

Author: asutton
Date: 2009-06-01 17:44:35 EDT (Mon, 01 Jun 2009)
New Revision: 53556
URL: http://svn.boost.org/trac/boost/changeset/53556

Log:
Re-added the exterior property labeling framework under a different name
Added:
   trunk/boost/graph/detail/hashed_property_container.hpp   (contents, props changed)
   trunk/boost/graph/detail/indexed_property_container.hpp   (contents, props changed)
   trunk/boost/graph/shared_properties.hpp   (contents, props changed)

Added: trunk/boost/graph/detail/hashed_property_container.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/hashed_property_container.hpp	2009-06-01 17:44:35 EDT (Mon, 01 Jun 2009)
@@ -0,0 +1,108 @@
+// (C) Copyright Andrew Sutton 2008-2009
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_DETAIL_HASHED_PROPERTIES_HPP
+#define BOOST_GRAPH_DETAIL_HASHED_PROPERTIES_HPP
+
+#include <tr1/unordered_map>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/functional/hash.hpp>
+
+namespace boost { namespace graph_detail {
+
+/**
+ * Wrap an iterator with a default value so that it generates default values
+ * over a range of keys.
+ */
+template <typename Iter, typename Prop>
+struct key_value_iterator
+{
+    typedef typename std::forward_iterator_tag iterator_category;
+    typedef typename std::size_t difference_type;
+
+    typedef std::pair<typename Iter::value_type, Prop> value_type;
+    typedef value_type reference;
+    typedef value_type pointer;
+
+    key_value_iterator(Iter i, Prop const& p)
+        : iter(i), value(p)
+    { }
+
+    key_value_iterator& operator++()
+    { ++iter; return *this; }
+
+    reference operator*()
+    { return make_pair(*iter, value); }
+
+    bool operator==(key_value_iterator const& x) const
+    { return iter == x.iter; }
+
+    bool operator!=(key_value_iterator const& x) const
+    { return iter != x.iter; }
+
+    Iter    iter;
+    Prop    value;
+};
+
+template <typename Iter, typename Prop>
+inline key_value_iterator<Iter, Prop>
+make_key_value_iterator(Iter i, Prop const& x)
+{ return key_value_iterator<Iter, Prop>(i, x); }
+
+/**
+ * A simple wrapper around an unordered map, this is used to map descriptors
+ * to arbitrary property values. Note that the property type must be default
+ * constructible.
+ *
+ * This may seem a little odd because we're passing an iterator and not the key
+ * type. However, the key type is always the iterator's value type.
+ */
+template <typename Descriptor, typename Property>
+class hashed_property_container
+{
+public:
+    typedef Property value_type;
+    typedef Descriptor key_type;
+    typedef std::tr1::unordered_map<key_type, value_type, boost::hash<key_type>> container_type;
+
+    /**
+     * Construct the hashtable over n buckets. This may not actually allocate
+     * n buckets, so we can't necessarily guarantee that memory will actually
+     * be allocated for each element, much less what those default values would
+     * actually be.
+     */
+    hashed_property_container(std::size_t n)
+        : data(n)
+    { }
+
+    /**
+     * Construct the hashtable over the keys in the iterator range [f, l) with
+     * the default value x.
+     */
+    template <typename Iter>
+    hashed_property_container(Iter f, Iter l, value_type const& x)
+        : data(detail::make_key_value_iterator(f, x),
+               detail::make_key_value_iterator(l, value_type()))
+    { }
+
+    template <typename Range>
+    hashed_property_container(Range rng, value_type const& x)
+        : data(detail::make_key_value_iterator(rng.first, x),
+               detail::make_key_value_iterator(rng.second, value_type()))
+    { }
+
+    inline value_type& operator[](key_type const& k)
+    { return data[k]; }
+
+    inline value_type const& operator[](key_type const& k) const
+    { return data[k]; }
+
+    container_type data;
+};
+
+} } // namespace boost::graph_detail
+
+
+#endif

Added: trunk/boost/graph/detail/indexed_property_container.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/detail/indexed_property_container.hpp	2009-06-01 17:44:35 EDT (Mon, 01 Jun 2009)
@@ -0,0 +1,102 @@
+// (C) Copyright Andrew Sutton 2008-2009
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_DETAIL_INDEXED_PROPERTIES_HPP
+#define BOOST_GRAPH_DETAIL_INDEXED_PROPERTIES_HPP
+
+#include <vector>
+#include <boost/iterator/iterator_facade.hpp>
+
+namespace boost { namespace graph_detail {
+
+/**
+ * Wrap an iterator with a default value so that it generates default values
+ * over a range of keys. This maintains the defalt value as an object to
+ * prevent multiple constructions if the object is "heavy".
+ */
+template <typename Iter, typename Prop>
+struct default_value_iterator
+    : iterator_facade<
+        default_value_iterator<Iter, Prop>, Prop, std::forward_iterator_tag,
+        Prop const&
+    >
+{
+    typedef typename std::forward_iterator_tag iterator_category;
+    typedef std::size_t difference_type;
+
+    typedef Prop value_type;
+    typedef value_type const& reference;
+    typedef value_type const* pointer;
+
+    default_value_iterator(Iter i, Prop const& p)
+        : iter(i), value(p)
+    { }
+
+    void advance()
+    { ++iter; }
+
+    bool equal(default_value_iterator const& x) const
+    { return iter == x.iter; }
+
+    Prop const& dereference() const
+    { return value; }
+
+    Iter iter;
+    Prop value;
+};
+
+template <typename Iter, typename Prop>
+inline default_value_iterator<Iter, Prop>
+make_default_value_iterator(Iter i, Prop const& p)
+{ return default_value_iterator<Iter, Prop>(i, p); }
+
+/**
+ * A simple wrapper around a vector. Because the "key" to this vector is
+ * actually given as a descriptor, we have to get the underlying index that
+ * allows us to map this value to a property.
+ *
+ * @todo If the underlying container is shared, then this can act as both
+ * the property map and the container. Or we could have the property map
+ * be a shared_ptr to this (or other) containers.
+ */
+template <typename Descriptor, typename Property>
+struct indexed_property_container
+{
+    typedef Property value_type;
+    typedef Descriptor key_type;
+    typedef std::vector<Property> container_type;
+
+    inline indexed_property_container(std::size_t n)
+        : data(n)
+    { }
+
+    /**
+     * Construct the hashtable over the keys in the iterator range [f, l) with
+     * the default value x.
+     */
+    template <typename Iter>
+    inline indexed_property_container(Iter f, Iter l, value_type const& x)
+        : data(detail::make_default_value_iterator(f, x),
+               detail::make_default_value_iterator(l, value_type()))
+    { }
+
+    template <typename Range>
+    inline indexed_property_container(Range rng, value_type const& x)
+        : data(detail::make_default_value_iterator(rng.first, x),
+               detail::make_default_value_iterator(rng.second, value_type()))
+    { }
+
+    inline value_type& operator[](key_type const& k)
+    { return data[k.value]; }
+
+    inline value_type const& operator[](key_type const& k) const
+    { return data[k.value]; }
+
+    container_type data;
+};
+
+} } // namespace boost::graph_detail
+
+#endif

Added: trunk/boost/graph/shared_properties.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/shared_properties.hpp	2009-06-01 17:44:35 EDT (Mon, 01 Jun 2009)
@@ -0,0 +1,192 @@
+// (C) Copyright Andrew Sutton 2008-2009
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRAPH_SHARED_PROPERTIES_HPP
+#define BOOST_GRAPH_SHARED_PROPERTIES_HPP
+
+#include <boost/shared_ptr.hpp>
+
+#include <boost/graph/detail/hashed_property_container.hpp>
+#include <boost/graph/detail/indexed_property_container.hpp>
+
+namespace boost {
+namespace graph_detail {
+    // Define the mapping strategy based on the type of descriptor. By default,
+    // we prefer to use hashing since the number of data structures that
+    // actually index their vertices is tiny.
+    struct index_mapping { };
+    struct hash_mapping { };
+
+    /** @internal @name Descriptor Mapping */
+    //@{
+    template <typename Descriptor>
+    struct descriptor_mapping
+    { typedef hash_mapping strategy; };
+
+    // If the descriptor is an unsigned int, then we can use a vector.
+    template <>
+    struct descriptor_mapping<std::size_t>
+    { typedef index_mapping strategy; };
+    //@}
+
+    // Select the type of container based on the underlying store selector.
+    // Noe that these have to wrap the underlying containers so that a common
+    // interface exists between the two.
+    template <typename Descriptor, typename Property>
+    struct choose_container
+        : typename mpl::if_<
+            is_same<
+                typename descriptor_mapping<Descriptor>::strategy, hash_mapping
+            >,
+            hashed_property_container<Descriptor, Property>,
+            indexed_property_container<Descriptor, Property>
+        >::type type;
+    { };
+
+    /** @internal @name Get Range
+     * Return a range over the set of vertices or edges. Note that this is
+     * going to be truly problematic if is_same<Vertex, Edge>.
+     */
+    template <typename Graph>
+    inline typename Graph::vertex_range
+    get_range(Graph const& g, typename Graph::vertex_descriptor)
+    { return g.vertices(); }
+
+    template <typename Graph>
+    inline typename Graph::edge_range
+    get_range(Graph const& g, typename Graph::edge_descriptor)
+    { return g.edges(); }
+} // namespace graph_detail
+
+// TODO: Work in progress.
+
+/**
+ * The label type allows the definition of exterior properties that
+ * can maintain either their own internal store (via shared pointers) or be
+ * constructed over an exterioir store. This is useful in algorithms that
+ * can provide default exterior properties or allow the user to provide their
+ * own.
+ *
+ * The use of this type incurs a slight overhead due to an additional level of
+ * indirection.
+ */
+template <typename Graph, typename Descriptor, typename Label>
+struct label {
+    // Select the container and map type for the self-wrapping property.
+    typedef typename detail::choose_container<
+        Descriptor, Label
+    >::type Container;
+
+    typedef typename Label value_type;
+    typedef typename Label& reference;
+    typedef typename Descriptor key_type;
+
+    // By default, the optional property contains no property. This should
+    // probably never be used.
+    label()
+        : data()
+    { }
+
+    // Allocate a label and build a property map over it.
+    label(Graph const& g, value_type const& x = value_type())
+        : container(new Container(detail::get_range(g, Descriptor()), x))
+    { }
+
+    // Construct the optional property over the given map, without allocating
+    // an exterior label.
+    label(Container&  cont)
+        : container(&cont)
+    { }
+
+    value_type& operator()(key_type const& key)
+    { return map(key); }
+
+    void operator()(key_type const& key, value_type const& value) const
+    { return map(key, value); }
+
+    optional_label& swap(optional_label& x) {
+        using std::swap;
+        swap(container, x.container);   // Should overload to constant time op.
+        swap(map, x.map);
+        return *this;
+    }
+
+    shared_ptr<Container> data;
+};
+
+/**
+ * The optional vertex map allows a user-provided property map or a self-
+ * contained exterior property to be passed to a generic function. The user
+ * provided property map is not required to be constructed over an exterior
+ * property.
+ */
+template <typename Graph, typename Label>
+struct vertex_label
+    : label<Graph, typename Graph::vertex_descriptor, Label>
+{
+    typedef label<Graph, typename Graph::vertex_descriptor, Label> Base;
+    typedef typename Base::Container Container;
+
+    vertex_label() : Base() { }
+    vertex_label(Graph const& g, Label const& x = Label()) : Base(g, x) { }
+    vertex_label(Container& cont) : Base(cost) { }
+};
+
+/**
+ * The optional edge map allows a user-provided property map or a self-
+ * contained exterior property to be passed to a generic function. The user
+ * provided property map is not required to be constructed over an exterior
+ * property.
+ */
+template <typename Graph, typename Label>
+struct edge_label
+    : label<Graph, typename Graph::edge_descriptor, Label>
+{
+    typedef label<Graph, typename Graph::vertex_descriptor, Label> base_type;
+    typedef typename Base::Container Container;
+
+    edge_label() : Base() { }
+    edge_label(Graph const& g, Label const& x = Label()) : Base(g, x) { }
+    edge_label(Container& cont) : Base(cont) { }
+};
+
+namespace detail
+{
+    // Optionally initialize the container, but not if the map is already
+    // initialized.
+    template <typename Graph, typename Map>
+    void optional_init(Graph const& g, Map& map, typename Map::value_type x)
+    {
+        if(!map.data) {
+            Map tmp(g, x);
+            map.swap(tmp);
+        }
+    }
+}
+
+/** @name Initialize Property Map
+ * Delayed initialization of optional property maps. The default solution
+ * is to do nothing (i.e,. the map is already initialized). Specialized
+ * variants simply swap the given map with one that's actually initialized.
+ */
+//@{
+/*
+template <typename Graph, typename Map>
+void initialize(Graph const&, Map&, typename Map::value_type)
+{ throw 0; }
+*/
+
+template <typename Graph, typename Label>
+void initialize(Graph const& g, optional_vertex_label<Graph, Label>& map, Label const& x)
+{ detail::optional_init(g, map, x); }
+
+template <typename Graph, typename Label>
+void initialize(Graph const g, optional_edge_label<Graph, Label>& map, Label const& x)
+{ detail::optional_init(g, map, x); }
+//@}
+
+} // namespace boost
+
+#endif