blob: e85ef9029a2ac257f4e54d301c192534dcc3eee8 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
/*
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
|
