[Boost-commit] svn:boost r45227 - sandbox/boost/algorithm/cluster

From: franklin.jonathan_at_[hidden]
Date: 2008-05-08 16:05:47

Author: jfranklin
Date: 2008-05-08 16:05:46 EDT (Thu, 08 May 2008)
New Revision: 45227
URL: http://svn.boost.org/trac/boost/changeset/45227

Log:
Added some concept checking, and renamed a few template parameters.

Added:
   sandbox/boost/algorithm/cluster/concept.hpp   (contents, props changed)
Text files modified: 
   sandbox/boost/algorithm/cluster/cluster_data.hpp |     9 ++++-                                   
   sandbox/boost/algorithm/cluster/dbscan.hpp       |    65 +++++++++++++++++++++++---------------- 
   2 files changed, 45 insertions(+), 29 deletions(-)

Modified: sandbox/boost/algorithm/cluster/cluster_data.hpp
==============================================================================
--- sandbox/boost/algorithm/cluster/cluster_data.hpp	(original)
+++ sandbox/boost/algorithm/cluster/cluster_data.hpp	2008-05-08 16:05:46 EDT (Thu, 08 May 2008)
@@ -1,3 +1,8 @@
+//  (C) Copyright Jonathan Franklin 2008.
+//  Use, modification and distribution are subject to 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)
+
 #if ! defined BOOST_ALGORITHM_CLUSTER_CLUSTER_DATA_HPP
 #define BOOST_ALGORITHM_CLUSTER_CLUSTER_DATA_HPP
 
@@ -13,10 +18,10 @@
 
 /*! TODO: Document this type.
  */
-template<typename Cluster>
+template<typename ClusterT>
 struct cluster_data
 {
-  typedef Cluster value_type;
+  typedef ClusterT value_type;
   typedef std::vector<value_type> clusters;
   cluster_data() : m_pClusters(new clusters) {}
   ~cluster_data() {}

Added: sandbox/boost/algorithm/cluster/concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/boost/algorithm/cluster/concept.hpp	2008-05-08 16:05:46 EDT (Thu, 08 May 2008)
@@ -0,0 +1,38 @@
+//  (C) Copyright Jonathan Franklin 2008.
+//  Use, modification and distribution are subject to 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)
+
+#if ! defined BOOST_ALGORITHM_CLUSTER_CONCEPT_HPP
+#define BOOST_ALGORITHM_CLUSTER_CONCEPT_HPP
+
+#include <boost/concept_check.hpp>
+
+namespace boost
+{
+namespace algorithm
+{
+namespace cluster
+{
+
+  // TODO: Document the purpose of this concept.
+  template<typename T, typename DistanceFunT>
+  struct DistanceComparableConcept
+  {
+    void constraints()
+    {
+      // Operation
+      d(t, t);
+    }
+  private:
+    T t;
+    DistanceFunT d;
+  };
+
+  // TODO: Add concepts here, then delete this comment.
+
+} // End of namespace cluster;
+} // End of namespace algorithm;
+} // End of namespace boost;
+
+#endif // BOOST_ALGORITHM_CLUSTER_CONCEPT_HPP

Modified: sandbox/boost/algorithm/cluster/dbscan.hpp
==============================================================================
--- sandbox/boost/algorithm/cluster/dbscan.hpp	(original)
+++ sandbox/boost/algorithm/cluster/dbscan.hpp	2008-05-08 16:05:46 EDT (Thu, 08 May 2008)
@@ -1,7 +1,13 @@
+//  (C) Copyright Jonathan Franklin 2008.
+//  Use, modification and distribution are subject to 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)
+
 #if ! defined BOOST_ALGORITHM_CLUSTER_DBSCAN_HPP
 #define BOOST_ALGORITHM_CLUSTER_DBSCAN_HPP
 
 #include <boost/algorithm/cluster/cluster_data.hpp>
+#include <boost/algorithm/cluster/concept.hpp>
 #include <vector>
 
 namespace boost
@@ -13,19 +19,22 @@
 
 namespace detail
 {
+// TODO: Where should we put these?
+int const UNCLASSIFIED = -1;
+int const NOISE = 0;
 
 // TODO: Replace this naive query function w/ R*-tree or fractional cascading.
 // This query mechanism makes the runtime quadratic.
-template<typename NTupleIter, typename DistFun>
+template<typename NTupleIterT, typename DistFunT>
 static void query(
-  NTupleIter const & query_pt,
-  NTupleIter const & begin,
-  NTupleIter const & end,
-  typename NTupleIter::difference_type eps,
-  DistFun const & d,
-  std::vector<NTupleIter> & v)
+  NTupleIterT const & query_pt,
+  NTupleIterT const & begin,
+  NTupleIterT const & end,
+  typename NTupleIterT::difference_type eps,
+  DistFunT const & d,
+  std::vector<NTupleIterT> & v)
 {
-  for(NTupleIter cur_pt = begin; cur_pt != end; ++cur_pt)
+  for(NTupleIterT cur_pt = begin; cur_pt != end; ++cur_pt)
   {
     if (query_pt == cur_pt)
       continue;
@@ -38,12 +47,12 @@
 }
 
 // TODO: Replace this so we don't have to store the cluster info for each tuple?
-template<typename NTupleIter>
+template<typename NTupleIterT>
 struct node
 {
-  node(NTupleIter const & t) : tuple(t), cluster(UNCLASSIFIED) {}
+  node(NTupleIterT const & t) : tuple(t), cluster(UNCLASSIFIED) {}
 
-  NTupleIter tuple;
+  NTupleIterT tuple;
   int cluster;
 };
 
@@ -58,31 +67,33 @@
  * \param[in] d
  * \return The cluster data (partitioning of the tuples).
  */
-template<typename Cluster, typename NTupleIter, typename DistFun>
-cluster_data<Cluster>
-dbscan(NTupleIter const & begin,
-       NTupleIter const & end, 
-       typename NTupleIter::difference_type const & eps,
+template<typename ClusterT, typename NTupleIterT, typename DistFunT>
+cluster_data<ClusterT>
+dbscan(NTupleIterT const & begin,
+       NTupleIterT const & end, 
+       typename NTupleIterT::difference_type const & eps,
        size_t min_points,
-       DistFun const & d)
+       DistFunT const & d)
 {
-  int const UNCLASSIFIED = -1;
-  int const NOISE = 0;
+  // Concept check.
+  function_requires<
+    DistanceComparableConcept<typename NTupleIterT::value_type, DistFunT> >();
+    //DistanceComparableConcept<int, DistFunT> >();
 
   // TODO: Rework the algorithm to NOT make this extra collection?
-  typedef detail::node<NTupleIter> node;
+  typedef detail::node<NTupleIterT> node;
   typedef std::vector<node> ntuple_nodes;
   ntuple_nodes tuples;
 
   // Initialize algorithm.
   //size_t num_elems = 0;
-  for(NTupleIter it = begin; it != end; ++it)
+  for(NTupleIterT it = begin; it != end; ++it)
   {
     //++num_elems;
     tuples.push_back(node(it));
   }
 
-  typedef cluster_data<std::vector<NTupleIter> > cluster_data;
+  typedef cluster_data<std::vector<NTupleIterT> > cluster_data;
   cluster_data p;
 
   // TODO: We should try to make cluster_num go away.
@@ -90,7 +101,7 @@
   for(ntuple_nodes::iterator it = tuples.begin(); it != tuples.end(); ++it)
   {
     // Skip this tuple if its already been classified as a cluster or noise.
-    if (it->cluster != UNCLASSIFIED)
+    if (it->cluster != detail::UNCLASSIFIED)
       continue;
 
     // Expand cluster.
@@ -100,14 +111,14 @@
     // If the neighborhood of this tuple is too small, then mark it as noise.
     if (seeds.size() < min_points)
     {
-      it->cluster = NOISE;
+      it->cluster = detail::NOISE;
       continue;
     }
 
     // Start the next cluster.
     ++cluster_num;
-    p.push_back(Cluster()); // TODO: This is goofy.
-    Cluster & cur_cluster = p.back();
+    p.push_back(ClusterT()); // TODO: This is goofy.
+    ClusterT & cur_cluster = p.back();
 
     // Mark entire neighborhood as part of the current cluster.
     it->cluster = cluster_num;
@@ -134,7 +145,7 @@
         {
           if (results[n]->cluster < 1) // Not assigned to cluster yet.
           {
-            if (UNCLASSIFIED == results[n]->cluster)
+            if (detail::UNCLASSIFIED == results[n]->cluster)
               seeds.push_back(results[n]);
             results[n]->cluster = cluster_num;
             cur_cluster.push_back(results[n]->tuple);