From 8d7bfe241b730e26175aa49a800c5fc9fdb4909c Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Mon, 25 Nov 2013 17:39:24 +0100 Subject: Added parser for DIMACS format + some examples. --- graph.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'graph.c') diff --git a/graph.c b/graph.c index e6be1c1..a957136 100644 --- a/graph.c +++ b/graph.c @@ -29,6 +29,51 @@ graph load_graph(FILE *stream) { return k; } +graph load_graph_dimacs(FILE *stream) { + int i, n, m, a, b; + + + char buf = fgetc(stream); + while (buf == 'c') { + buf = fgetc(stream); + if (buf == '\n') buf = fgetc(stream); + else buf = 'c'; + } + if (buf != 'p') { + fprintf(stderr, "File format error (expected 'p' declaration)\n"); + return NULL; + } + fscanf(stream, " col %d %d\n", &n, &m); // read node count + fprintf(stderr, "Load DIMACS: n = %d, m = %d\n", n, m); + + graph k = malloc(sizeof(struct graph_descriptor)); + k->N = n; + k->neighbour = malloc(n * sizeof(set)); + for (i = 0; i < n; i++) k->neighbour[i] = empty_set(n); + + for (i = 0; i < m; i++) { + + buf = fgetc(stream); + while (buf == 'c') { + buf = fgetc(stream); + if (buf == '\n') buf = fgetc(stream); + else buf = 'c'; + } + if (buf != 'e') { + fprintf(stderr, "File format error (expected 'e' declaration)\n"); + return NULL; + } + + fscanf(stream, " %d %d\n", &a, &b); + fprintf(stderr, "Edge: (%d, %d)\n", a, b); + a--; b--; + set_add_ip(b, k->neighbour[a]); + set_add_ip(a, k->neighbour[b]); + } + + return k; +} + const set graph_neighbours(const graph g, int n) { return g->neighbour[n]; } -- cgit v1.2.3