Référence du fichier graph_algos.c

algorithmes fondamentaux Plus de détails...

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

Fonctions
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

algorithmes fondamentaux

---

Documentation des fonctions

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.

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

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