PR.c

#include "list.h"
#include <math.h>

struct MATRIX {
  unsigned m;
  unsigned n;
  char**   b;
};
typedef struct MATRIX matrix;

struct GRAPH {
  unsigned size; /* number of vertices */
  list_unsigned** al; /* adjacency list representing edges */
};
typedef struct GRAPH graph;

void matrix_clear(matrix* M) {
  unsigned i;
  for (i = 0; i < M->m; ++i)
    free(M->b[i]);
  free(M->b);
  free(M);
}

matrix* read_matrix(char* filename) {
   FILE* fp;
  if (NULL == (fp = fopen(filename,"r"))) {
    fprintf(stderr,"ERROR: Can't read the graph file.\n");
    exit(1);
  }
  char* line = NULL;
  size_t len = 0;
  unsigned m = 0;
  unsigned n;
  if (-1 == getline(&line, &len, fp)) { exit(1); }
  ++m, n = strlen(line)-1;
  while (-1 != getline(&line, &len, fp)) { ++m; }

  matrix* M = (matrix*)calloc(1, sizeof(matrix));
  M->b = (char**)calloc(m,sizeof(char*));
  M->m = m;
  M->n = n;
  
  unsigned i, j;
  rewind(fp);
  for (i = 0; getline(&line, &len, fp) != -1; ++i) {
    M->b[i] = (char*)calloc(n, sizeof(char));
    for (j = 0; j < n; ++j) { M->b[i][j] = line[j]; }
  }
  fclose(fp);
  return M;
}

void matrix_print(matrix* M) {
  unsigned i, j;
  for (i = 0; i < M->m; ++i) {
    for (j = 0; j < M->n; ++j) putchar(M->b[i][j]);
    putchar('\n');
  }
}

graph* make_overlap_graph(matrix* M, list_unsigned** r) {
  graph* g = (graph*)calloc(1,sizeof(graph));
  g->size = M->m; /* the number of vertices (g->size) is M->m */
  g->al = (list_unsigned**)calloc(M->m, sizeof(list_unsigned*));

  unsigned i;
  for (i = 0; i < M->m; ++i) { g->al[i] = (list_unsigned*)calloc(1, sizeof(list_unsigned)); }
  for (i = 0; i < M->m; ++i) {
    unsigned j;
    for (j = i+1; j < M->m; ++j) {
      unsigned count = 0, min = r[i]->size, min_idx = i, max_idx = j;
      if (r[j]->size < min) { min = r[j]->size; min_idx = j; max_idx = i; }
      list_unsigned_cell* p;
      for (p = r[min_idx]->head; NULL != p; p = p->next) { if ('1' == M->b[max_idx][p->key]) { ++count; } }
      if (0 < count && count < r[min_idx]->size) { list_unsigned_add_rear(g->al[i], j); list_unsigned_add_rear(g->al[j], i); }
    }
  }
  
  return g;
}

void graph_print(graph* G) {
  const unsigned d = floor(log10(G->size)) + 1;
  unsigned i;
  for (i = 0; i < G->size; ++i) { printf("al[%*d] : ", d, i); list_unsigned_print(G->al[i]); putchar('\n'); }
}

void graph_clear(graph* G) {
  unsigned i;
  for (i = 0; i < G->size; ++i) { list_unsigned_clear(G->al[i]); }
  free(G->al);
  free(G);
}

list_unsigned** make_row_set(matrix* M) {
  list_unsigned** r = (list_unsigned**)calloc(M->m, sizeof(list_unsigned*));
  unsigned i;
  for (i = 0; i < M->m; ++i) {
    r[i] = (list_unsigned*)calloc(1, sizeof(list_unsigned));
    unsigned j;
    for (j = 0; j < M->n; ++j) { if ('1' == M->b[i][j]) { list_unsigned_add_rear(r[i], j); } }
  }
  return r;
}

void row_set_clear(list_unsigned** r, const unsigned m) {
  unsigned i;
  for (i = 0; i < m; ++i) { list_unsigned_clear(r[i]); }
  free(r);
}

void row_set_print(list_unsigned** r, const unsigned m) {
  unsigned i;
  for (i = 0; i < m; ++i) { printf("r[%d] : ", i); list_unsigned_print(r[i]); putchar('\n'); }
}

/*

#include "lbfs.h"

int main(int argc, char** argv) {
  matrix* M = read_matrix(argv[1]);
  matrix_print(M);
  list_unsigned** r = make_row_set(M);
  row_set_print(r, M->m);

  graph* G = make_overlap_graph(M, r);
  graph_print(G);
  graph_clear(G);
  
  row_set_clear(r, M->m);
  matrix_clear(M);
  return 0;
}

*/