codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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, °ree, n); task4(adjacent, degree, n); } releaseAdjacent(&adjacent, n); xfree(degree, XMALLOC_ARRAY3); xmallocdump(); return 0; } /* end */
Private
[
?
]
Run code
Submit