path: root/graph.c

/*
	Projet d'algorithmique et programmation 2013-2014
	(cours de C.Matthieu et J.Stern)
	Alex AUVOLAT, Mendes OULAMARA

	Fonctions pour la manipulation de graphes.
*/

#include <stdlib.h>

#include "graph.h"

graph load_graph(FILE *stream) {
	int i, r, a, b;

	graph k = malloc(sizeof(struct graph_descriptor));

	fscanf(stream, "%d ", &k->N);	// read node count
	k->neighbour = malloc(k->N * sizeof(set));
	for (i = 0; i < k->N; i++) k->neighbour[i] = empty_set(k->N);
	
	fscanf(stream, "%d ", &r);
	for (i = 0; i < r; i++) {
		fscanf(stream, "%d %d ", &a, &b);
		set_add_ip(b, k->neighbour[a]);
		set_add_ip(a, k->neighbour[b]);
	}

	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"); fscanf(stream, " edge");		// either col or edge
	fscanf(stream, " %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);
		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];
}

void dump_graphviz(const graph g, FILE *stream) {
	int i = 0;
	fprintf(stream, "graph A {\n");

	for (i = 0; i < g->N; i++) {
		fprintf(stream, "  \"%d\" []\n", i);
	}

	for (i = 0; i < g->N; i++) {
		set n = copy_set(graph_neighbours(g, i));
		while (!(is_set_empty(n))) {
			int j = elt_of_set(n);
			if (j >= i) fprintf(stream, "  \"%d\" -- \"%d\"\n", i, j);
			set_remove_ip(j, n);
		}
	}
	fprintf(stream, "}\n");
}

void delete_graph(graph g) {
	int i;
	for (i = 0; i < g->N; i++) {
		delete_set(g->neighbour[i]);
	}
	free(g->neighbour);
	free(g);
}