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

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

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	TYP_VARC long

#define	TYP_VSOM long

#define	HUGE HUGE_VAL

#define	SHRT_MIN -32767

#define	SHRT_MAX +32767

#define	USHRT_MAX 65535

#define	INT_MIN -32767

#define	INT_MAX +32767

#define	UINT_MAX 65535

#define	LONG_MIN -2147483647

#define	LONG_MAX +2147483647

#define	ULONG_MAX 4294967295

#define	M_PI 3.14159265358979323846

#define	max(X, Y) ((X)>=(Y)?(X):(Y))

#define	min(X, Y) ((X)<=(Y)?(X):(Y))

Définitions de type
typedef struct cell	cell

typedef cell *	pcell
	pointeur sur une cellule

typedef struct graphe	graphe

Fonctions
void	AfficheEnsemble (boolean *s, int n)
	affiche � l'�cran l'ensemble represent� par le tableau de bool�ens s. Plus de détails...

void	AfficheListe (pcell p)
	affiche le contenu de la liste p. Plus de détails...

void	AfficheSuccesseurs (graphe *g)
	affiche le graphe dans sa repr�sentation "listes de successeurs". Plus de détails...

void	AfficheArcs (graphe *g)
	affiche le graphe dans sa repr�sentation "listes d'arcs". Plus de détails...

void	AfficheValeursSommets (graphe *g)
	affiche les valeurs associ�es aux sommets. Plus de détails...

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

void	EPSGraphe (graphe g, char filename, double r, double t, double marge, int noms_sommets, int v_sommets, int col_sommets, int v_arcs)
	g�n�re une figure PostScript d'apr�s la repr�sentation "successeurs" du graphe g. Plus de détails...

void	AutoNomsSommets (graphe *g, int mode)
	g�n�re automatiquement des noms pour les sommets du graphe g. Plus de détails...

void	PlongementCirculaire (graphe *g, double r)
	affecte � chaque sommet des coordonn�es (x,y) r�gulierement r�parties sur un cercle. Plus de détails...

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

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

graphe *	Symetrique (graphe *g)

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

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 EPSGraphe	(	graphe *	g,
		char *	filename,
		double	r,
		double	t,
		double	marge,
		int	noms_sommets,
		int	v_sommets,
		int	col_sommets,
		int	v_arcs
	)

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.
noms_sommets	(entr�e) : bool�en indiquant s'il faut �crire les noms des sommets.
v_sommets	(entr�e) : bool�en indiquant s'il faut �crire les valeurs des sommets.
col_sommets	(entr�e) : bool�en indiquant s'il faut colorier les sommets dont la valeur est non nulle.
v_arcs	(entr�e) : bool�en indiquant s'il faut �crire les valeurs des arcs.

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

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

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

Classes

Macros

Définitions de type

Fonctions

Description détaillée

Documentation des fonctions