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

#include "graphaux.h"
#include "graphes.h"

Macros
#define	TAILLEBUF 4096

Fonctions
pcell	AlloueCell (pcell *plibre)
	retire la premiere cellule de la liste pointée par plibre et retourne un pointeur sur cette cellule. Plus de détails...

void	LibereCell (pcell *plibre, pcell p)
	insère la cellule p au début de la liste pointée par 'plibre'. Plus de détails...

void	RetireTete (pcell plibre, pcell pliste)
	retire la première cellule de la liste 'pliste'. La cellule est chaînee à la liste 'plibre'. Plus de détails...

void	AjouteTete (pcell plibre, pcell pliste, int a, TYP_VARC v)
	ajoute une cellule contenant le sommet 'a' et la valeur 'v' en tête de la liste 'pliste'. La cellule est prise dans la liste 'plibre'. Plus de détails...

int	EstDansListe (pcell p, int a)
	retourne 1 si le sommet 'a' se trouve dans la liste 'p', 0 sinon. Plus de détails...

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. Plus de détails...

void	TermineGraphe (graphe *g)
	libère la memoire occupée par le graphe g. Plus de détails...

graphe *	ReadGraphe (char *filename)
	Lit les données d'un graphe dans le fichier filename, retourne un pointeur sur la structure graphe construite. Plus de détails...

void	AjouteArc (graphe *g, int i, int s)
	ajoute l'arc (i,s) au graphe g (application gamma seulement). Plus de détails...

void	AjouteArcValue (graphe *g, int i, int s, TYP_VARC v)
	ajoute l'arc (i,s) au graphe g (application gamma seulement). Plus de détails...

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. Plus de détails...

int	PopSuccesseur (graphe *g, int i)
	retire un arc (i,s) du graphe g (application gamma seulement), et retourne le sommet s Plus de détails...

int	EstSuccesseur (graphe *g, int i, int s)
	retourne 1 si le sommet 's' est un successeur du sommet 'i', 0 sinon. Plus de détails...

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). Plus de détails...

Description détaillée

fonctions de base pour la manipulation de graphes

Documentation des fonctions

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) : extrémité initiale de l'arc.
s	(entrée) : extrémité finale de l'arc.

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

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

void AjouteArcValue	(	graphe *	g,
		int	i,
		int	s,
		TYP_VARC	v
	)

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

Paramètres

g	(entrée/sortie) : un graphe.
i	(entrée) : extrémité initiale de l'arc.
s	(entrée) : extrémité finale de l'arc.
v	(entrée) : une valeur pour l'arc.

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

Référencé par ReadGraphe().

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

ajoute une cellule contenant le sommet 'a' et la valeur 'v' 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.
v	(entrée) : une valeur.

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

Référencé par AjouteArc(), et AjouteArcValue().

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().

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().

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 GrapheAleatoire(), et ReadGraphe().

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().

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.

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(), AjouteArcValue(), InitGraphe(), graphe::nomsommet, graphe::x, et graphe::y.

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().

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.

Macros

Fonctions

Description détaillée

Documentation des fonctions