Référence du fichier graphes.h

structures de base pour la manipulation de graphes Plus de détails...

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

Aller au code source de ce fichier.

Classes
struct	cell
	structure de cellule pour les listes chaînees de successeurs. Plus de détails...
struct	graphe
	structure pour la representation des graphes Plus de détails...
Macros
#define	M_PI   3.14159265358979323846
#define	max(X, Y)   ((X)>=(Y)?(X):(Y))
#define	min(X, Y)   ((X)<=(Y)?(X):(Y))
Définition de type
typedef cell *	pcell
	pointeur sur une cellule
Fonctions
void	AfficheEnsemble (boolean *s, int n)
	affiche à l'écran l'ensemble representé par le tableau de booléens s.
void	AfficheListe (pcell p)
	affiche le contenu de la liste p.
void	AfficheSuccesseurs (graphe *g)
	affiche le graphe dans sa représentation "listes de successeurs".
void	AfficheArcs (graphe *g)
	affiche le graphe dans sa représentation "listes d'arcs".
void	AfficheValeursSommets (graphe *g)
	affiche les valeurs associées aux sommets.
void	PSGraphe (graphe *g, char *filename, double r, double t, double marge)
	génère une figure PostScript d'après la représentation "successeurs" du graphe g.
void	AutoNomsSommets (graphe *g, int mode)
	génère automatiquement des noms pour les sommets du graphe g.
void	PlongementCirculaire (graphe *g, double r)
	affecte à chaque sommet des coordonnées (x,y) régulierement réparties sur un cercle.
void	PlongementRadial (graphe *g, int c)
	répartit les sommets de g sur des cercles concentriques en fonction de leur rang, avec le sommet c au centre.
pcell	AlloueCell (pcell *plibre)
	retire la premiere cellule de la liste pointée par plibre et retourne un pointeur sur cette cellule.
void	LibereCell (pcell *plibre, pcell p)
	insère la cellule p au début de la liste pointée par 'plibre'.
void	RetireTete (pcell *plibre, pcell *pliste)
	retire la première cellule de la liste 'pliste'. La cellule est chaînee à la liste 'plibre'.
void	AjouteTete (pcell *plibre, pcell *pliste, int a)
	ajoute une cellule contenant le sommet 'a' en tête de la liste 'pliste'. La cellule est prise dans la liste 'plibre'.
int	EstDansListe (pcell p, int a)
	retourne 1 si le sommet 'a' se trouve dans la liste 'p', 0 sinon.
graphe *	InitGraphe (int nsom, int nmaxarc)
	alloue la memoire nécessaire pour représenter un graphe a 'nsom' sommets, possédant au maximum 'nmaxarc' arcs. Retourne un pointeur sur la structure allouée.
void	TermineGraphe (graphe *g)
	libère la memoire occupée par le graphe g.
graphe *	ReadGraphe (char *filename)
	Lit les données d'un graphe dans le fichier filename, retourne un pointeur sur la structure graphe construite.
void	AjouteArc (graphe *g, int i, int s)
	ajoute l'arc (i,s) au graphe g (application gamma seulement).
void	RetireArc (graphe *g, int i, int s)
	retire l'arc (i,s) du graphe g (application gamma seulement), si celui-ci etait présent. Sinon, pas d'action.
int	PopSuccesseur (graphe *g, int i)
	retire un arc (i,s) du graphe g (application gamma seulement), et retourne le sommet s
int	EstSuccesseur (graphe *g, int i, int s)
	retourne 1 si le sommet 's' est un successeur du sommet 'i', 0 sinon.
graphe *	GrapheAleatoire (int nsom, int narc)
	retourne un graphe aléatoire à 'nsom' sommets et 'narc' arcs. Le graphe est antisymétrique et sans boucle. Le nombre d'arcs doit être <= nsom (nsom - 1) / 2. Les arcs sont pondérés (valeur aléatoire entre 0.0 et 1.0).
graphe *	Symetrique (graphe *g)
	construit et retourne le graphe g_1 symétrique du graphe g (algorithme linéaire)
graphe *	FermetureSymetrique (graphe *g)
	construit et retourne la fermeture symétrique du graphe g (algorithme linéaire)
void	CompFortConnexe (graphe *g, graphe *g_1, int a, boolean *Ca)
	retourne dans Ca la composante fortement connexe de g contenant a (sous la forme d'un tableau de booléens).
boolean	ExisteCircuit (graphe *g, int a)
	teste l'existence d'un circuit dans g contenant a
void	CompConnexe (graphe *g, graphe *g_1, int a, boolean *Ca)
	retourne la composante connexe de g contenant a (sous la forme d'un tableau de booléens).
boolean	Connexe (graphe *g, graphe *g_1)
	retourne 1 si le graphe est connexe, 0 sinon.

---

Description détaillée

structures de base pour la manipulation de graphes

---

Documentation des fonctions

void AfficheArcs

(

graphe *

g

)

affiche le graphe dans sa représentation "listes d'arcs".

Paramètres:

g

(entrée) : un graphe.

Références graphe::narc, graphe::queue, graphe::tete, et graphe::v_arcs.

void AfficheEnsemble	(	boolean *	s,
		int	n
	)

affiche à l'écran l'ensemble representé par le tableau de booléens s.

Paramètres:

	s	(entrée) : un tableau de valeurs booléennes.
	n	(entrée) : la taille du tableau.

void AfficheListe

(

pcell

p

)

affiche le contenu de la liste p.

Paramètres:

p

(entrée) : une liste chaînee de successeurs.

Références cell::next, et cell::som.

Référencé par AfficheSuccesseurs().

void AfficheSuccesseurs

(

graphe *

g

)

affiche le graphe dans sa représentation "listes de successeurs".

Paramètres:

g

(entrée) : un graphe.

Références AfficheListe(), graphe::gamma, et graphe::nsom.

void AfficheValeursSommets

(

graphe *

g

)

affiche les valeurs associées aux sommets.

Paramètres:

g

(entrée) : un graphe.

Références graphe::nsom, et graphe::v_sommets.

void AjouteArc	(	graphe *	g,
		int	i,
		int	s
	)

ajoute l'arc (i,s) au graphe g (application gamma seulement).

Paramètres:

	g	(entrée/sortie) : un graphe.
	i	(entrée) : un sommet de g.
	s	(entrée) : un sommet de g.

Références AjouteTete(), graphe::gamma, graphe::libre, et graphe::narc.

Référencé par FermetureSymetrique(), GrapheAleatoire(), ReadGraphe(), et Symetrique().

void AjouteTete	(	pcell *	plibre,
		pcell *	pliste,
		int	a
	)

ajoute une cellule contenant le sommet 'a' en tête de la liste 'pliste'. La cellule est prise dans la liste 'plibre'.

Paramètres:

	plibre	(entrée) : pointeur sur une liste chaînee de cellules libres.
	pliste	(entrée) : pointeur sur une liste.
	a	(entrée) : un sommet.

Références AlloueCell(), cell::next, et cell::som.

Référencé par AjouteArc().

pcell AlloueCell

(

pcell *

plibre

)

retire la premiere cellule de la liste pointée par plibre et retourne un pointeur sur cette cellule.

Paramètres:

plibre

(entrée) : pointeur sur une liste chaînee de cellules libres.

Renvoie:

pointeur sur une cellule.

Références cell::next.

Référencé par AjouteTete().

void AutoNomsSommets	(	graphe *	g,
		int	mode
	)

génère automatiquement des noms pour les sommets du graphe g.

Paramètres:

	g	(entrée) : un graphe.
	mode	(entrée) : 1 pour que les noms soient les indices des sommets, 2 pour que les noms soient les valeurs associées aux sommets, 3 pour des noms composes de l'indice et de la valeur.

Références graphe::nomsommet, graphe::nsom, et graphe::v_sommets.

void CompConnexe	(	graphe *	g,
		graphe *	g_1,
		int	a,
		boolean *	Ca
	)

retourne la composante connexe de g contenant a (sous la forme d'un tableau de booléens).

Paramètres:

	g	(entrée) : un graphe.
	g_1	(entrée) : le graphe symétrique de g.
	a	(entrée) : un sommet du graphe g.

Renvoie:

un sous-ensemble de sommets de g (tableau de booléens).

Références CreeLifoVide(), graphe::gamma, LifoPop(), LifoPush(), LifoTermine(), LifoVide(), cell::next, graphe::nsom, et cell::som.

Référencé par Connexe().

void CompFortConnexe	(	graphe *	g,
		graphe *	g_1,
		int	a,
		boolean *	Ca
	)

retourne dans Ca la composante fortement connexe de g contenant a (sous la forme d'un tableau de booléens).

Paramètres:

	g	(entrée) : un graphe.
	g_1	(entrée) : le graphe symétrique de g.
	a	(entrée) : un sommet du graphe g.
	Ca	(sortie) : un sous-ensemble des sommets de g (tableau de booléens).

Avertissement:

Ca doit avoir été alloué correctement (pas de vérification)

Références CreeLifoVide(), EnsembleVide(), graphe::gamma, LifoPop(), LifoPush(), LifoTermine(), LifoVide(), cell::next, graphe::nsom, et cell::som.

boolean Connexe	(	graphe *	g,
		graphe *	g_1
	)

retourne 1 si le graphe est connexe, 0 sinon.

Paramètres:

	g	(entrée) : un graphe.
	g_1	(entrée) : le graphe symétrique de g.

Renvoie:

booléen.

Références CompConnexe(), EnsembleVide(), et graphe::nsom.

int EstDansListe	(	pcell	p,
		int	a
	)

retourne 1 si le sommet 'a' se trouve dans la liste 'p', 0 sinon.

Paramètres:

	p	(entrée) : une liste chaînee de successeurs.
	a	(entrée) : un sommet.

Renvoie:

booléen.

Références cell::next, et cell::som.

Référencé par EstSuccesseur().

int EstSuccesseur	(	graphe *	g,
		int	i,
		int	s
	)

retourne 1 si le sommet 's' est un successeur du sommet 'i', 0 sinon.

Paramètres:

	g	(entrée) : un graphe.
	i	(entrée) : un sommet de g.
	s	(entrée) : un sommet de g.

Renvoie:

booléen.

Références EstDansListe(), et graphe::gamma.

Référencé par GrapheAleatoire().

boolean ExisteCircuit	(	graphe *	g,
		int	a
	)

teste l'existence d'un circuit dans g contenant a

Paramètres:

	g	(entrée) : un graphe.
	a	(entrée) : un sommet du graphe g.

Renvoie:

booléen

Références CreeLifoVide(), EnsembleVide(), graphe::gamma, LifoPop(), LifoPush(), LifoTermine(), LifoVide(), cell::next, graphe::nsom, et cell::som.

graphe* FermetureSymetrique

(

graphe *

g

)

construit et retourne la fermeture symétrique du graphe g (algorithme linéaire)

Paramètres:

g

(entrée) : un graphe.

Renvoie:

un graphe.

Avertissement:

seule la représentation 'gamma' est utilisée.

Références AjouteArc(), graphe::gamma, InitGraphe(), graphe::narc, cell::next, graphe::nsom, et cell::som.

graphe* GrapheAleatoire	(	int	nsom,
		int	narc
	)

retourne un graphe aléatoire à 'nsom' sommets et 'narc' arcs. Le graphe est antisymétrique et sans boucle. Le nombre d'arcs doit être <= nsom (nsom - 1) / 2. Les arcs sont pondérés (valeur aléatoire entre 0.0 et 1.0).

Paramètres:

	nsom	(entrée) : nombre de sommets.
	narc	(entrée) : nombre d'arcs.

Renvoie:

un graphe.

Avertissement:

la méthode employée ici est naïve, tres inefficace du point de vue temps de calcul et ne garantit aucune propriété statistique.

Références AjouteArc(), EstSuccesseur(), InitGraphe(), graphe::queue, RetireArc(), graphe::tete, et graphe::v_arcs.

graphe* InitGraphe	(	int	nsom,
		int	nmaxarc
	)

alloue la memoire nécessaire pour représenter un graphe a 'nsom' sommets, possédant au maximum 'nmaxarc' arcs. Retourne un pointeur sur la structure allouée.

Paramètres:

	nsom	(entrée) : nombre de sommets.
	nmaxarc	(entrée) : nombre maximum d'arcs.

Renvoie:

un graphe.

Références graphe::gamma, graphe::libre, graphe::narc, graphe::nmaxarc, graphe::nomsommet, graphe::nsom, graphe::queue, graphe::reserve, graphe::tete, graphe::v_arcs, graphe::v_sommets, graphe::x, et graphe::y.

Référencé par FermetureSymetrique(), GrapheAleatoire(), ReadGraphe(), et Symetrique().

void LibereCell	(	pcell *	plibre,
		pcell	p
	)

insère la cellule p au début de la liste pointée par 'plibre'.

Paramètres:

	plibre	(entrée) : pointeur sur une liste chaînee de cellules libres.
	p	(entrée) : pointeur sur une cellule.

Références cell::next.

Référencé par RetireTete().

void PlongementCirculaire	(	graphe *	g,
		double	r
	)

affecte à chaque sommet des coordonnées (x,y) régulierement réparties sur un cercle.

Paramètres:

	g	(entrée/sortie) : un graphe.
	r	(entrée) : le rayon du cercle.

Références graphe::nsom, graphe::x, et graphe::y.

void PlongementRadial	(	graphe *	g,
		int	c
	)

répartit les sommets de g sur des cercles concentriques en fonction de leur rang, avec le sommet c au centre.

Paramètres:

	g	(entrée/sortie) : un graphe.
	c	(entrée) : le sommet à placer au centre.

Références graphe::gamma, cell::next, graphe::nsom, cell::som, graphe::x, et graphe::y.

int PopSuccesseur	(	graphe *	g,
		int	i
	)

retire un arc (i,s) du graphe g (application gamma seulement), et retourne le sommet s

Paramètres:

	g	(entrée/sortie) : un graphe.
	i	(entrée) : un sommet de g.

Avertissement:

le sommet i doit avoir au moins un successeur (pas de vérification)

Références graphe::gamma, graphe::libre, RetireTete(), et cell::som.

void PSGraphe	(	graphe *	g,
		char *	filename,
		double	r,
		double	t,
		double	marge
	)

génère une figure PostScript d'après la représentation "successeurs" du graphe g.

Paramètres:

	g	(entrée) : un graphe.
	filename	(entrée) : nom du fichier postscript à générer.
	r	(entrée) : rayon des cercles qui représentent les sommets (0 pour ne pas les dessiner).
	t	(entrée) : taille (demi-longueur) des flèches pour les arcs (0 pour ne pas les dessiner).
	marge	(entrée) : marge en x et en y.

Références graphe::gamma, cell::next, graphe::nomsommet, graphe::nsom, cell::som, graphe::x, et graphe::y.

graphe* ReadGraphe

(

char *

filename

)

Lit les données d'un graphe dans le fichier filename, retourne un pointeur sur la structure graphe construite.

Paramètres:

filename

(entrée) : nom du fichier graphe.

Renvoie:

un graphe.

Références AjouteArc(), InitGraphe(), et graphe::nomsommet.

void RetireArc	(	graphe *	g,
		int	i,
		int	s
	)

retire l'arc (i,s) du graphe g (application gamma seulement), si celui-ci etait présent. Sinon, pas d'action.

Paramètres:

	g	(entrée/sortie) : un graphe.
	i	(entrée) : un sommet de g.
	s	(entrée) : un sommet de g.

Références graphe::gamma, graphe::libre, graphe::narc, et RetireTete().

Référencé par GrapheAleatoire().

void RetireTete	(	pcell *	plibre,
		pcell *	pliste
	)

retire la première cellule de la liste 'pliste'. La cellule est chaînee à la liste 'plibre'.

Paramètres:

	plibre	(entrée) : pointeur sur une liste chaînee de cellules libres.
	pliste	(entrée) : pointeur sur une liste.

Références LibereCell(), et cell::next.

Référencé par PopSuccesseur(), et RetireArc().

graphe* Symetrique

(

graphe *

g

)

construit et retourne le graphe g_1 symétrique du graphe g (algorithme linéaire)

Paramètres:

g

(entrée) : un graphe.

Renvoie:

un graphe.

Avertissement:

seule la représentation 'gamma' est utilisée.

Références AjouteArc(), graphe::gamma, InitGraphe(), graphe::narc, cell::next, graphe::nsom, et cell::som.

void TermineGraphe

(

graphe *

g

)

libère la memoire occupée par le graphe g.

Paramètres:

g

(entrée) : un graphe.

Références graphe::gamma, graphe::nomsommet, graphe::nsom, graphe::queue, graphe::reserve, graphe::tete, graphe::v_arcs, et graphe::v_sommets.