path: root/graph.h

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

	Fonctions pour la manipulation de graphes.
	Remarque : un graphe utilise les ensembles de set_*.c, donc si on utilise
	l'implémentation sous forme de bitset cela donne l'équivalent d'une matrice
	d'adjacence, alors que l'utilisation de l'implémentation sous forme de liste
	liée est plus adaptée pour un graphe peu rempli.

	Dans l'ensemble du projet on travaille sur des graphes  non orientées,
	c'est-à-dire que la matrice d'adjacence est symmétrique.

	La structure donnée ici permet très facilement d'accéder à l'ensemble
	des voisins d'un sommet, mais il est un peu plus compliqué d'énumérer
	toutes les arêtes du graphe.

	Il est recommandé d'utiliser la fonction graph_neighbours(int s) pour
	accéder aux voisins d'un noeud, car celle-ci renvoie un const set et
	non un simple set, ce qui évite d'accidentelles modifications des
	données du graphe.
*/

#ifndef DEF_GRAPH_H
#define DEF_GRAPH_H

#include <stdio.h>

#include "sets.h"

struct graph_descriptor {
	int N;					// nombre de noeuds
	set *neighbour;			// ensemble des voisins de chaque noeuds
};

typedef struct graph_descriptor *graph;


graph load_graph(FILE *stream);				// spécification du format dans le fichier README
graph load_graph_dimacs(FILE *stream);		// cf README
const set graph_neighbours(const graph g, int n);
void dump_graphviz(const graph g, FILE *stream);
void delete_graph(graph g);

#endif