Checking in

rapidsai · rapids-bot · May 27, 2021 · Apr 20, 2021 · Apr 20, 2021 · Apr 23, 2021
commit 635d018f687c82f571b7c511e7632400046fec6a
@@ -73,11 +73,11 @@ void merge_msts(raft::Graph_COO<value_idx, value_idx, value_t> &coo1,
  * @param[inout] color the color labels array returned from the mst invocation
  * @return updated MST edge list
  */
-template <typename value_idx, typename value_t, typename mst_epilogue_f>
+template <typename value_idx, typename value_t, typename mst_epilogue_f, typename red_op>
 void connect_knn_graph(const raft::handle_t &handle, const value_t *X,
                        raft::Graph_COO<value_idx, value_idx, value_t> &msf,
                        size_t m, size_t n, value_idx *color,
-                       mst_epilogue_f mst_epilogue_func,
+                       mst_epilogue_f mst_epilogue_func, red_op reduction_op,
                        raft::distance::DistanceType metric =
                          raft::distance::DistanceType::L2SqrtExpanded) {
   auto d_alloc = handle.get_device_allocator();
@@ -86,7 +86,7 @@ void connect_knn_graph(const raft::handle_t &handle, const value_t *X,
   raft::sparse::COO<value_t, value_idx> connected_edges(d_alloc, stream);
 
   raft::linkage::connect_components<value_idx, value_t>(handle, connected_edges,
-                                                        X, color, m, n);
+                                                        X, color, m, n, reduction_op);
 
   mst_epilogue_func(handle, connected_edges.rows(), connected_edges.cols(),
                     connected_edges.vals(), connected_edges.nnz);
@@ -96,6 +96,9 @@ void connect_knn_graph(const raft::handle_t &handle, const value_t *X,
                                            connected_edges.nnz, indptr2.data(),
                                            m + 1, d_alloc, stream);
 
+  raft::print_device_vector("new_rows", connected_edges.rows(), connected_edges.nnz, std::cout);
+  raft::print_device_vector("new_cols", connected_edges.cols(), connected_edges.nnz, std::cout);
+  raft::print_device_vector("new_dists", connected_edges.vals(), connected_edges.nnz, std::cout);
   // On the second call, we hand the MST the original colors
   // and the new set of edges and let it restart the optimization process
   auto new_mst = raft::mst::mst<value_idx, value_idx, value_t>(
@@ -129,39 +132,38 @@ void connect_knn_graph(const raft::handle_t &handle, const value_t *X,
  * @param[in] max_iter maximum iterations to run knn graph connection. This
  *  argument is really just a safeguard against the potential for infinite loops.
  */
-template <typename value_idx, typename value_t, typename mst_epilogue_f>
+template <typename value_idx, typename value_t, typename mst_epilogue_f, typename red_op>
 void build_sorted_mst(const raft::handle_t &handle, const value_t *X,
                       const value_idx *indptr, const value_idx *indices,
                       const value_t *pw_dists, size_t m, size_t n,
                       value_idx *mst_src, value_idx *mst_dst,
-                      value_t *mst_weight, size_t nnz,
-                      mst_epilogue_f epilogue_func,
+                      value_t *mst_weight, value_idx *color, size_t nnz,
+                      mst_epilogue_f epilogue_func, red_op reduction_op,
                       raft::distance::DistanceType metric =
                         raft::distance::DistanceType::L2SqrtExpanded,
                       int max_iter = 10) {
   auto d_alloc = handle.get_device_allocator();
   auto stream = handle.get_stream();
 
-  rmm::device_uvector<value_idx> color(m, stream);
 
   // We want to have MST initialize colors on first call.
   auto mst_coo = raft::mst::mst<value_idx, value_idx, value_t>(
-    handle, indptr, indices, pw_dists, (value_idx)m, nnz, color.data(), stream,
+    handle, indptr, indices, pw_dists, (value_idx)m, nnz, color, stream,
     false, true);
 
 
   int iters = 1;
   int n_components =
-    linkage::get_n_components(color.data(), m, d_alloc, stream);
+    linkage::get_n_components(color, m, d_alloc, stream);
 
   while (n_components > 1 && iters < max_iter) {
     printf("Didn't converge. trying again\n");
     connect_knn_graph<value_idx, value_t>(handle, X, mst_coo, m, n,
-                                          color.data(), epilogue_func);
+                                          color, epilogue_func, reduction_op);
 
     iters++;
 
-    n_components = linkage::get_n_components(color.data(), m, d_alloc, stream);
+    n_components = linkage::get_n_components(color, m, d_alloc, stream);
   }
 
   /**
@@ -184,14 +186,14 @@ void build_sorted_mst(const raft::handle_t &handle, const value_t *X,
                " or increase 'max_iter'",
                max_iter);
 
-  if (mst_coo.n_edges != m - 1) {
-    raft::print_device_vector("mst_src", mst_coo.src.data(), mst_coo.n_edges,
-                              std::cout);
-    raft::print_device_vector("mst_dst", mst_coo.dst.data(), mst_coo.n_edges,
-                              std::cout);
-    raft::print_device_vector("mst_weight", mst_coo.weights.data(),
-                              mst_coo.n_edges, std::cout);
-  }
+//  if (mst_coo.n_edges != m - 1) {
+//    raft::print_device_vector("mst_src", mst_coo.src.data(), mst_coo.n_edges,
+//                              std::cout);
+//    raft::print_device_vector("mst_dst", mst_coo.dst.data(), mst_coo.n_edges,
+//                              std::cout);
+//    raft::print_device_vector("mst_weight", mst_coo.weights.data(),
+//                              mst_coo.n_edges, std::cout);
+//  }
 
   RAFT_EXPECTS(mst_coo.n_edges == m - 1,
                "n_edges should be %d but was %d. This"

@@ -77,10 +77,12 @@ void single_linkage(const raft::handle_t &handle, const value_t *X, size_t m,
   /**
    * 2. Construct MST, sorted by weights
    */
+  rmm::device_uvector<value_idx> color(m, stream);
+  raft::linkage::FixConnectivitiesRedOp<value_idx, value_t> op(color.data(), m);
   detail::build_sorted_mst<value_idx, value_t>(
     handle, X, indptr.data(), indices.data(), pw_dists.data(), m, n,
-    mst_rows.data(), mst_cols.data(), mst_data.data(), indices.size(),
-    MSTEpilogueNoOp<value_idx, value_t>(), metric);
+    mst_rows.data(), mst_cols.data(), mst_data.data(), color.data(), indices.size(),
+    MSTEpilogueNoOp<value_idx, value_t>(), op, metric);
 
   pw_dists.release();
 

@@ -200,23 +200,22 @@ struct LookupColorOp {
  * @param[in] d_alloc device allocator to use
  * @param[in] stream cuda stream for which to order cuda operations
  */
-template <typename value_idx, typename value_t>
+template <typename value_idx, typename value_t, typename red_op>
 void perform_1nn(cub::KeyValuePair<value_idx, value_t> *kvp,
                  value_idx *nn_colors, value_idx *colors, const value_t *X,
                  size_t n_rows, size_t n_cols,
                  std::shared_ptr<raft::mr::device::allocator> d_alloc,
-                 cudaStream_t stream) {
+                 cudaStream_t stream, red_op reduction_op) {
   rmm::device_uvector<int> workspace(n_rows, stream);
   rmm::device_uvector<value_t> x_norm(n_rows, stream);
 
   raft::linalg::rowNorm(x_norm.data(), X, n_cols, n_rows, raft::linalg::L2Norm,
                         true, stream);
 
-  FixConnectivitiesRedOp<value_idx, value_t> red_op(colors, n_rows);
   raft::distance::fusedL2NN<value_t, cub::KeyValuePair<value_idx, value_t>,
                             value_idx>(kvp, X, X, x_norm.data(), x_norm.data(),
                                        n_rows, n_rows, n_cols, workspace.data(),
-                                       red_op, red_op, true, true, stream);
+                                       reduction_op, reduction_op, true, true, stream);
 
   LookupColorOp<value_idx, value_t> extract_colors_op(colors);
   thrust::transform(thrust::cuda::par.on(stream), kvp, kvp + n_rows, nn_colors,
@@ -318,11 +317,12 @@ void min_components_by_color(raft::sparse::COO<value_t, value_idx> &coo,
  * @param[in] n_rows number of rows in X
  * @param[in] n_cols number of cols in X
  */
-template <typename value_idx, typename value_t>
+template <typename value_idx, typename value_t, typename red_op>
 void connect_components(const raft::handle_t &handle,
                         raft::sparse::COO<value_t, value_idx> &out,
                         const value_t *X, const value_idx *orig_colors,
                         size_t n_rows, size_t n_cols,
+                        red_op reduction_op,
                         raft::distance::DistanceType metric =
                           raft::distance::DistanceType::L2SqrtExpanded) {
   auto d_alloc = handle.get_device_allocator();
@@ -352,7 +352,7 @@ void connect_components(const raft::handle_t &handle,
   rmm::device_uvector<value_idx> src_indices(n_rows, stream);
 
   perform_1nn(temp_inds_dists.data(), nn_colors.data(), colors.data(), X,
-              n_rows, n_cols, d_alloc, stream);
+              n_rows, n_cols, d_alloc, stream, reduction_op);
 
   /**
    * Sort data points by color (neighbors are not sorted)