dist_cc.h

Go to the documentation of this file.

#ifndef DIST_CC_H
#define DIST_CC_H
 
/************************************************************************ 
 * @file dist_cc.h
 * @brief Connected Cluster (CC) algorithm routines and helpers
 * 
 * author: Leonid Pryadko <leonid.pryadko@ucr.edu>, Weilei Zeng
 ************************************************************************/
 
#include <inttypes.h>
#include <strings.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <m4ri/m4ri.h>
 
#include "mmio.h"
#include "uthash.h"
#include "util_hash.h"
#include "util_m4ri.h"
#include "util_io.h"
 
#ifdef __cplusplus
extern "C" {
#endif

static inline int one_csr_row_combine(one_vec_t * const v1, const one_vec_t * const v0,
                  const csr_t * const mat, const int row){
#ifndef NDEBUG
  if ((!v1) || (!v0) || (!mat))
    ERROR("all arguments must be allocated: v1=%p v0=%p mat=%p\n",v1,v0,mat);
  if(v1 == v0)
    ERROR("the two vectors should not be the same !");
  if((row<0) || (row >= mat->rows))
    ERROR("this should not happen\n");
#endif
  int iM, i0=0, i1=0; 
  for (iM = mat->p[row]; iM < mat->p[row+1]; iM++){
    const int ic = mat->i[iM];
    while((i0 < v0->wei) && (v0->vec[i0] < ic))
      v1->vec[i1++] = v0->vec[i0++];
    if(i0 >= v0->wei)
      break;
    if(v0->vec[i0]==ic)
      i0++; 
    else
      v1->vec[i1++] = ic;
  }
  if(i0 >= v0->wei) 
    for (                      ; iM < mat->p[row+1]; iM++){
      const int ic = mat->i[iM];
      v1->vec[i1++] = ic;
    }
  else 
    while(i0 < v0->wei)
      v1->vec[i1++] = v0->vec[i0++];
  
  v1->wei = i1;
  return i1; 
}

static inline int one_ordered_ins(one_vec_t * const err, const int j){
  int pos=err->wei-1;
  while((pos >= 0) && (j < err->vec[pos])){
    err->vec[pos+1] = err->vec[pos];
    pos--;
  }
#ifndef NDEBUG  
  if ((pos >= 0) && (j == err->vec[pos]))
    ERROR("Unexpected! vec[%d]=%d is already present!",pos,j);
#endif   
  err->vec[pos+1]=j;
#ifndef NDEBUG
  for(int i=0; i < err->wei; i++)
    if(err->vec[i] >= err->vec[i+1]){
      printf("check ordering at i=%d! ",i);
      one_vec_print(err);
      ERROR("unexpected");
    }
#endif   
  err->wei ++;
  return pos+1;
}

static inline int one_ordered_search(one_vec_t * const err, const int val){
  int bot=0, top=err->wei , mid=0;
#ifndef NDEBUG  
  if (!top)
    return -1;
#endif   
  while(top - bot > 1){
    mid = (top+bot) >> 1;
#ifndef NDEBUG  
  if (mid>=err->wei)
    ERROR("this should not happen");
#endif   
    if (err->vec[mid] <= val)
      bot = mid;
    else
      top = mid;
  }
  if ( err->vec[bot] == val)
    return bot;
  else
    return -1;
} 

static inline void one_ordered_pos_del(
    one_vec_t * const err, _maybe_unused const int val, const int pos
) {
#ifndef NDEBUG
  if ((pos < 0) || (pos >= err->wei) || (err->wei == 0)
      || (err->vec[pos] != val))
    ERROR("this should not happen!");
#endif
  err->wei--; 
  for (int i = pos; i < err->wei; i++)
    err->vec[i] = err->vec[i + 1];
}

static inline int one_ordered_find_del(one_vec_t * const err, const int val) {
  int pos = one_ordered_search(err, val);
  if (pos == -1)
    return 0;
  one_ordered_pos_del(err, val, pos);
  return 1;
}
 
int start_CC_recurs(one_vec_t *err, one_vec_t *urr, one_vec_t * const syn[],
            const int w_limit, const int max_col_wt, 
            const csr_t * const mH, const csr_t * const mHT,
                    params_t * const p);
 
int do_CC_dist(params_t * const p);
 
#ifdef __cplusplus
}
#endif
 
#endif /* DIST_CC_H */