#include <stdio.h>
#include <stdlib.h>

void mysrand48(long seed) { srand((int)seed); }
double mydrand48(void) { return (double)rand() / (RAND_MAX + 1.0); }

/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
#define XMALLOC_ARRAY1 1001
#define XMALLOC_ARRAY2 1002
#define XMALLOC_ARRAY3 1003

void releaseAdjacent(int ***adjacent, int n) {
  int i;
  if (*adjacent == 0)
    return;
  for (i = 0; i < n; i++)
    xfree((*adjacent)[i], XMALLOC_ARRAY2);
  xfree(*adjacent, XMALLOC_ARRAY1);
}

int allocationAdjacentMap(int ***adjacent, int n) {
  int i, j;
  if ((*adjacent = xmalloc(n * sizeof(int *), XMALLOC_ARRAY1)) == 0)
    return 0;
  for (i = 0; i < n; i++)
    (*adjacent)[i] = 0;
  for (i = 0; i < n; i++) {
    if (((*adjacent)[i] = xmalloc(n * sizeof(int), XMALLOC_ARRAY2)) == 0)
      break;
    for (j = 0; j < n; j++)
      (*adjacent)[i][j] = 0;
  }
  if (i == n)
    return 1;
  releaseAdjacent(adjacent, n);
  return 0;
}

#define BUFFLEN 1024
static char buffS[BUFFLEN];

int putInfo2AdjacentMap(FILE *fp, int ***adjacent, int n) {
  int from, to;
  int line;
  line = 0;
  while (line++, fgets(buffS, BUFFLEN, fp) != 0) {
    if (sscanf(buffS, "%d %d", &from, &to) != 2) {
      fprintf(stderr, "input data file, line %d is bad form.\n", line);
      return 0;
    }
    if (from < 0 || from >= n) {
      fprintf(stderr, "input data file, out of range.\n");
      return 0;
    }
    if (to < 0 || to >= n) {
      fprintf(stderr, "input data file, out of range.\n");
      return 0;
    }
    (*adjacent)[from][to] = (*adjacent)[to][from] = 1;
  }
  return 1;
}

void getNodeNum(FILE *fp, int *n) {
  if ((fgets(buffS, BUFFLEN, fp) == 0) || (sscanf(buffS, "%d", n) != 1)) {
    fprintf(stderr, "input data file: first line is not a number.\n");
    *n = 0;
  }
}

void getAdjacentMap_sub(FILE *fp, int ***adjacent, int *n) {
  /* read first line -> n */
  if (getNodeNum(fp, n), *n > 0) {
    if (allocationAdjacentMap(adjacent, *n) > 0) {
      if (putInfo2AdjacentMap(fp, adjacent, *n) > 0) {
        /* do nothing, OK */
      } else {
/* bellow, error handling */
        goto error;
      }
    } else {
      fprintf(stderr, "cannot allocate enough memory.\n");
      *n = 0;
    }
  } else {
    /* bad file format */
  error:
    *n = 0;
  }
}

int getAdjacentMap(char const * const filename, int ***adjacent, int *n) {
  FILE *fp;
  if ((fp = fopen(filename, "r")) != 0) {
    if (getAdjacentMap_sub(fp, adjacent, n), n == 0) {
      fprintf(stderr, "bad file format: %s.\n", filename);
      return 0;
    }
    fclose(fp);
  } else {
    fprintf(stderr, "cannot open the file: %s.\n", filename);
    return 0;
  }
  return 1;
}

void task2(int **adjacent, int n) {
  /* 2 */
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
      printf("%d ", adjacent[i][j]);
    putchar('\n');
  }
  putchar('\n');
}

void task3(int **adjacent, int **degree, int n) {
  /* 3 */
  int i, j, s, t;
  s = 0;
  if ((*degree = xmalloc(sizeof(int) * n, XMALLOC_ARRAY3)) != 0) {
    for (i = 0; i < n; i++) {
      printf("%d: ", i);
      t = 0;
      for (j = 0; j < n; j++)
        if (adjacent[i][j])
          t++;
      printf("%d\n", t);
      (*degree)[i] = t;
      s += t;
    }
    printf("%f\n\n", (double)s / n);
  }
}

#define SEED 31415926L
#define START_NODE 0
#define STOP_NODE 6
void task4(int **adjacent, int *degree, int n) {
  /* 4 */
  int v, next, before;
  int idx, i, flag;
  double d;
  mysrand48(SEED);
  v = START_NODE;
  before = -1;
  flag = 0;
  while (v != STOP_NODE) {
    if (flag) printf(" -> "); else flag = 1;
    printf("%d", v);
    do {
      idx = (int)((double)((d = mydrand48()) * degree[v]));
      for (next = 0; !adjacent[v][next]; next++)
        ;
      i = 0;
      while (i < idx) {
        next++;
        while (!adjacent[v][next])
          next++;
        i++;
      }
    } while (next == before);
    before = v;
    v = next;
    /* printf("%d->%d:%d(%f)\n", before, v, idx, d); */
  }
  printf("-> %d", v);
}

#define FILENAME "graph1.txt"
int main() {
  int n;
  int **adjacent;
  int *degree;
  degree = 0; adjacent = 0;
  if (getAdjacentMap(FILENAME, &adjacent, &n)) {
    task2(adjacent, n);
    task3(adjacent, &degree, n);
    task4(adjacent, degree, n);
  }
  releaseAdjacent(&adjacent, n);
  xfree(degree, XMALLOC_ARRAY3);
  xmallocdump();
  return 0;
}
/* end */

cannot open the file: graph1.txt.