[Boost-commit] svn:boost r38478 - sandbox/SOC/2007/graphs/boost/graph

From: asutton_at_[hidden]
Date: 2007-08-06 13:21:55

Author: asutton
Date: 2007-08-06 13:21:54 EDT (Mon, 06 Aug 2007)
New Revision: 38478
URL: http://svn.boost.org/trac/boost/changeset/38478

Log:
Completely rewrote the exterior property code and probably some
of the closeness and clustering coefficient code.
Added exterior edge properties and abstracted the ability to
switch on index types based on the key types passed to
various functions. it's sweet.

Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp   |    15 +-                                      
   sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp |     1                                         
   sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp      |   214 +++++---------------------------------- 
   3 files changed, 39 insertions(+), 191 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/closeness_centrality.hpp	2007-08-06 13:21:54 EDT (Mon, 06 Aug 2007)
@@ -80,10 +80,9 @@
                                 Measure measure,
                                 Combinator combine)
     {
-        typedef typename Measure::distance_type Distance;
-        typedef typename Measure::distance_values DistanceValues;
-        Distance n = detail::combine_distances(g, dist, combine,
-                                               DistanceValues());
+        typedef typename property_traits<DistanceMap>::value_type Distance;
+        typedef numeric_values<Distance> DistanceValues;
+        Distance n = detail::combine_distances(g, dist, combine, DistanceValues());
         return measure(n, num_vertices(g));
     }
 
@@ -95,7 +94,7 @@
                                 DistanceMap dist,
                                 Measure measure)
     {
-        typedef typename Measure::distance_type Distance;
+        typedef typename property_traits<DistanceMap>::value_type Distance;
         return vertex_closeness_centrality(g, dist, measure, std::plus<Distance>());
     }
 
@@ -124,10 +123,11 @@
                          Measure measure)
     {
         typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
+        typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
 
         typename graph_traits<Graph>::vertex_iterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
-            cent[*i] = vertex_closeness_centrality(g, dist[*i], measure);
+            cent[*i] = vertex_closeness_centrality(g, DistanceMap(dist[*i]), measure);
         }
     }
 
@@ -142,8 +142,7 @@
         typedef typename property_matrix_traits<DistanceMatrix>::value_type Distance;
         typedef typename exterior_vertex_property<Graph, Distance>::map_type DistanceMap;
         typedef typename property_traits<CentralityMap>::value_type Result;
-        closeness_centrality(g, dist, cent,
-                             measure_closeness<Result>(g, DistanceMap()));
+        closeness_centrality(g, dist, cent, measure_closeness<Result>(g, DistanceMap()));
     }
 }
 

Modified: sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/clustering_coefficient.hpp	2007-08-06 13:21:54 EDT (Mon, 06 Aug 2007)
@@ -103,6 +103,7 @@
     inline void
     clustering_coefficient(const Graph& g, ClusteringMap cluster)
     {
+        typedef typename property_traits<ClusteringMap>::value_type T;
         typename graph_traits<Graph>::vertex_iterator i, end;
         for(tie(i, end) = vertices(g); i != end; ++i) {
             cluster[*i] = vertex_clustering_coefficient<T>(g, *i);

Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp	2007-08-06 13:21:54 EDT (Mon, 06 Aug 2007)
@@ -8,217 +8,65 @@
 #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
 
 #include <vector>
-#include <tr1/unordered_map>
-
-#include <boost/type_traits/is_same.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/property_map.hpp>
+#include <boost/utility.hpp>
+#include <boost/graph/container_property_map.hpp>
 
 namespace boost
 {
     namespace detail
     {
-        // These property map adapters are basically here to provide a common
-        // method for initializing the property maps. They also provide a
-        // cast operator for returning the underlying mapping type.
-
-        // Do we really /need/ to do this. Not really. There are otherways
-        // to achieve syntactic conformity, but they're less graceful.
-
-        template <typename Graph, typename Container>
-        struct vector_property_map_adapter
-            : public boost::put_get_helper<
-                    typename iterator_property_map<
-                            typename Container::iterator,
-                            typename property_map<Graph, vertex_index_t>::type
-                        >::reference,
-                    vector_property_map_adapter<Graph, Container>
-                >
-        {
-            typedef iterator_property_map<
-                    typename Container::iterator,
-                    typename property_map<Graph, vertex_index_t>::type
-                > map_type;
-            typedef typename map_type::key_type key_type;
-            typedef typename map_type::value_type value_type;
-            typedef typename map_type::reference reference;
-            typedef typename map_type::category category;
-
-            inline vector_property_map_adapter()
-                : m_map()
-            { }
-
-            inline vector_property_map_adapter(Container& c)
-                : m_map(c.begin())
-            { }
-
-            inline vector_property_map_adapter(const vector_property_map_adapter& x)
-                : m_map(x.m_map)
-            { }
-
-            inline reference operator [](const key_type& k) const
-            { return m_map[k];  }
-
-            map_type m_map;
-        };
-
-        template <typename Graph, typename Container>
-        struct hash_property_map_adapter
-            : public boost::put_get_helper<
-                    typename associative_property_map<Container>::reference,
-                    hash_property_map_adapter<Graph, Container>
-                >
+        // The vector matrix provides a little abstraction over vector
+        // types that makes matrices easier to work with. Note that it's
+        // non-copyable, meaning you should be passing it by value.
+        template <typename Graph, typename Key, typename Value>
+        struct vector_matrix
         {
-            typedef associative_property_map<Container> map_type;
-            typedef typename map_type::key_type key_type;
-            typedef typename map_type::value_type value_type;
-            typedef typename map_type::reference reference;
-            typedef typename map_type::category category;
-
-            inline hash_property_map_adapter()
-                : m_map()
-            { }
-
-            inline hash_property_map_adapter(Container& c)
-                : m_map(c)
-            { }
-
-            inline hash_property_map_adapter(const hash_property_map_adapter& x)
-                : m_map(x.m_map)
-            { }
-
-            inline reference operator[](const key_type& k) const
-            { return m_map[k]; }
-
-            operator map_type() const
-            { return m_map; }
-
-            map_type m_map;
-        };
-    }
-
-    namespace detail
-    {
-        // These structures implement very, very basic matrices
-        // over vectors and hash tables. Like the adapters above, these
-        // classes provide a degree of syntactic uniformity for their
-        // declarations.
-
-        template <typename Graph, typename Value>
-        struct vector_matrix_adapter
-        {
-            typedef typename graph_traits<Graph>::vertices_size_type size_type;
-            typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+            typedef std::size_t size_type;
+            typedef Key key_type;
             typedef Value value_type;
 
             typedef std::vector<value_type> container_type;
             typedef std::vector<container_type> matrix_type;
+            typedef container_property_map<Graph, container_type, Key> map_type;
+            typedef typename map_type::indexer_type indexer_type;
 
-            inline vector_matrix_adapter(size_type n)
+            // Instantiate the matrix over n elements (creates an nxn matrix).
+            // The graph has to be passed in order to ensure the index maps
+            // are constructed correctly when returning indexible elements.
+            inline vector_matrix(size_type n, const Graph& g)
                 : m_matrix(n, container_type(n))
+                , m_graph(g)
             { }
 
-            inline typename matrix_type::reference operator [](key_type k)
-            { return m_matrix[k]; }
+            inline map_type operator [](key_type k)
+            { return map_type(m_matrix[indexer_type::index(k, m_graph)], m_graph); }
 
-            inline typename matrix_type::reference operator [](key_type k) const
-            { return m_matrix[k]; }
+            inline map_type operator [](key_type k) const
+            { return map_type(m_matrix[indexer_type::index(k, m_graph)], m_graph); }
 
             mutable matrix_type m_matrix;
+            const Graph& m_graph;
         };
-
-        // There's a strange side-effect using the []'s of a hashtable in
-        // that it's a modifying operation. If the key isn't found, this
-        // will create a value for the key with the default value. However,
-        // since we know that all the keys exist in the map, it shouldn't
-        // be a big deal.
-        //
-        // Also, we can kind of skip the initialization of the underlying
-        // data structures. there's going to be a bunch of resizing, but
-        // in the long run, it may not hurt too much.
-        template <typename Graph, typename Value>
-        struct hash_matrix_adapter
-        {
-            typedef typename graph_traits<Graph>::vertices_size_type size_type;
-            typedef typename graph_traits<Graph>::vertex_descriptor key_type;
-
-            typedef Value value_type;
-            typedef std::tr1::unordered_map<key_type, value_type> container_type;
-            typedef std::tr1::unordered_map<key_type, container_type> matrix_type;
-
-            inline hash_matrix_adapter(size_type n)
-                : m_matrix(n)
-            {
-                typename matrix_type::iterator i, end = m_matrix.end();
-                for(i = m_matrix.begin(); i != end; ++i) {
-                    i->second.rehash(n);
-                }
-            }
-
-            inline typename matrix_type::mapped_type& operator [](key_type k)
-            { return m_matrix[k]; }
-
-            inline typename matrix_type::mapped_type& operator [](key_type k) const
-            { return m_matrix[k]; }
-
-            mutable matrix_type m_matrix;
-        };
-}
-
-    // This is very, very dirty. If the adjacency list implementation
-    // has not been included at this point, we need to define
-    // it's graph tag so we can specialize on it. I feel so unclean.
-    // A better solution would be to migrate commonly used graph tags
-    // like this to a separate header.
-#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
-    struct vec_adj_list_tag { };
-#endif
-
-    // These structures associate a preferred mapping style
-    // with a graph type.
-    struct vector_mapped_tag {};
-    struct hash_mapped_tag {};
+    }
 
     template <typename Graph, typename Value>
-    struct vector_mapped_vertex_property_traits
+    struct exterior_vertex_property
     {
-        typedef vector_mapped_tag mapping_type;
         typedef typename graph_traits<Graph>::vertex_descriptor key_type;
         typedef Value value_type;
-
-        typedef typename std::vector<Value> container_type;
-        typedef detail::vector_matrix_adapter<Graph, value_type> matrix_type;
-        typedef detail::vector_property_map_adapter<Graph, container_type> map_type;
+        typedef std::vector<Value> container_type;
+        typedef detail::vector_matrix<Graph, key_type, Value> matrix_type;
+        typedef container_property_map<Graph, container_type, key_type> map_type;
     };
 
     template <typename Graph, typename Value>
-    struct hash_mapped_vertex_property_traits
+    struct exterior_edge_property
     {
-        typedef hash_mapped_tag mapping_type;
-        typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+        typedef typename graph_traits<Graph>::edge_descriptor key_type;
         typedef Value value_type;
-
-        typedef typename std::tr1::unordered_map<key_type, value_type> container_type;
-        typedef detail::hash_matrix_adapter<Graph, value_type> matrix_type;
-        typedef detail::hash_property_map_adapter<Graph, container_type> map_type;
-    };
-
-
-    template <typename Graph, typename Value>
-    struct exterior_vertex_property
-    {
-        typedef typename Graph::graph_tag graph_tag;
-        typedef typename mpl::if_<
-                is_same<graph_tag, vec_adj_list_tag>,
-                vector_mapped_vertex_property_traits<Graph, Value>,
-                hash_mapped_vertex_property_traits<Graph, Value>
-            >::type traits_type;
-
-        typedef typename traits_type::key_type key_type;
-        typedef typename traits_type::value_type value_type;
-        typedef typename traits_type::container_type container_type;
-        typedef typename traits_type::matrix_type matrix_type;
-        typedef typename traits_type::map_type map_type;
+        typedef std::vector<Value> container_type;
+        typedef detail::vector_matrix<Graph, key_type, Value> matrix_type;
+        typedef container_property_map<Graph, container_type, key_type> map_type;
     };
 
     template <typename Matrix>