PDS_TriangleCount/src/elearn.cpp

/*!
 * \file    elearn.cpp
 * \brief   e-learning version of the exercise.
 *
 * \author
 *    Christos Choutouridis AEM:8997
 *    <cchoutou@ece.auth.gr>
 */
#include <elearn.h>

//------- e-learning code start ---------

//! Credits to PDS team
static void coo2csc_e(
      uint32_t *row, uint32_t *col, uint32_t const* row_coo, uint32_t const* col_coo, uint32_t nnz, uint32_t n, uint32_t isOneBased
      ) {
   // ----- cannot assume that input is already 0!
   for (uint32_t l = 0; l < n+1; l++) col[l] = 0;

   // ----- find the correct column sizes
   for (uint32_t l = 0; l < nnz; l++)
      col[col_coo[l] - isOneBased]++;

   // ----- cumulative sum
   for (uint32_t i = 0, cumsum = 0; i < n; i++) {
      uint32_t temp = col[i];
      col[i] = cumsum;
      cumsum += temp;
   }
   col[n] = nnz;
   // ----- copy the row indices to the correct place
   for (uint32_t l = 0; l < nnz; l++) {
      uint32_t col_l;
      col_l = col_coo[l] - isOneBased;

      uint32_t dst = col[col_l];
      row[dst] = row_coo[l] - isOneBased;

      col[col_l]++;
   }
   // ----- revert the column pointers
   for (uint32_t i = 0, last = 0; i < n; i++) {
      uint32_t temp = col[i];
      col[i] = last;
      last = temp;
   }
}

/*!
 * A small binary search utility
 */
uint32_t find_idx(const uint32_t* v, uint32_t begin, uint32_t end, uint32_t match) {
   uint32_t b = begin, e = end-1;
   while (b <= e) {
      uint32_t m = (b+e)/2;
      if       (v[m] == match)   return  m;
      else if  (b >= e)          return  end;
      else {
         if    (v[m] <  match)   b = m +1;
         else                    e   = m -1;
      }
   }
   return end;
}

/*!
 * Sparse matrix item accessor
 */
uint32_t get(uint32_t* R, uint32_t* C, uint32_t i, uint32_t j) {
   uint32_t e = C[j+1];
   return (find_idx(R, C[j], e, i) != e) ? 1 : 0;
}

/*!
 * \param coo_row    pointer to coo row data
 * \param coo_col    pointer to coo_column data
 * \param n          the size of matrix
 * \param nz         the number of non-zero items
 * \return           The vertex-wise count vector
 */
uint32_t* vertexWiseTriangleCounts (uint32_t *coo_row, uint32_t *coo_col, uint32_t n, uint32_t nz) {
   uint32_t* v = (uint32_t*)malloc(sizeof(uint32_t)*n);
   uint32_t* R = (uint32_t*)malloc(sizeof(uint32_t)*nz);
   uint32_t* C = (uint32_t*)malloc(sizeof(uint32_t)*n+1);

   // convert input
   coo2csc_e (R, C, coo_row, coo_col, nz, n, 1);

   // we use the lower triangular optimization just because ;)
   for (uint32_t i=0 ; i<n ; ++i) {
      for (uint32_t j = C[i]; j<C[i+1] ; ++j) {
         uint32_t j_idx = R[j];
         for (uint32_t k = C[j_idx] ; k<C[j_idx+1] ; ++k) {
            uint32_t k_idx = R[k];
            if (get(R, C, k_idx, i)) {
               ++v[i];
               ++v[j_idx];
               ++v[k_idx];
            }
         }
      }
   }
   return v;
}

//------- e-learning code end ---------

/*!
 * A unit-test like functionality to check our implementation.
 * \return
 */
uint32_t elearn_test (void) {
   uint32_t CooR[] = { 2, 4, 6, 7, 3, 5, 6, 8, 11, 12, 4, 11, 12, 7, 6, 7, 9, 10, 12};
   uint32_t CooC[] = { 1, 1, 1, 1, 2, 2, 2, 2,  2,  2, 3,  3,  3, 4, 5, 6, 8,  8, 11};
   uint32_t    N   = 12;
   uint32_t   NZ   = 19;
   uint32_t   c3[] = { 3, 5, 3, 1, 1, 3, 2, 0, 0, 0, 3, 3 };

   uint32_t* tc3 = vertexWiseTriangleCounts(CooR, CooC, N, NZ);   // call

   for (uint32_t i=0 ; i<N ; ++i)                                 // validate
      if (tc3[i] != c3[i])
         return 0;   // fail
   return 1;         // pass
}