Référence du fichier graph_basic.c

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

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

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

---

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

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

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

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.