Projet d'algorithme
Manipulation de graphes

LIU Florence et MULOT Yannick

Introduction

Le projet consiste à réaliser la commande graphes qui applique différents algorithmes sur les graphes.
Nous présenterons dans une première partie les fichiers sources, la commande et ses différentes options (alogorithmes) ainsi que les formats des fichiers. Dans la deuxième partie nous définirons les structures de données utilisées pour la représentation des graphes dans le code et nous donnerons les étapes pour construire le graphe à partir d'un fichier ou d'un autre graphe. Puis nous détaillerons les algorithmes et leur complexité. Et enfin dans la derniére partie, nous expliquerons l'analyse de la ligne de commande.

Chapter 1   Présentation du programme

1.1   Fichiers sources

Nous avons séparer le programme en plusieurs fichiers pour une meilleure compréhension :

Structures : Algorithmes : Gestion de la ligne de commande :
Pour compiler le programme, nous avons un fichier Makefile dans le répertoire.
Nous expliquons dans la section suivante comment lancer le programme.

1.2   Commande

Synopsis : graphes -acdDhkpst [fichier] [n] [-o fichier]
Une des options au moins doit obligatoirement être présente. Certaines peuvent être demandées en même temps si elles s'appliquent à un même type de graphe (orienté ou non orienté).
En cas d'absence de fichiers dans la ligne de commande, nous utiliserons l'entrée et la sortie standard.
Remarque :
La fin de la saisie sur l'entrée standard est signalée par un Ctrl D.

1.3   Options


Options d'algorithme :
pour les graphes non orientés


pour les graphes orientés

1.4   Formats des fichiers

1.4.1   Format d'entrée

Ces fichiers contiennent la description d'un graphe sous forme de matrice d'adjacence ou de liste d'adjacence.
Nous voulons des graphes valués positivement pour pouvoir appliquer tous nos algorithmes.

Description :
première ligne
: le nombre de sommets
deuxième ligne
: une lettre indiquant le type du graphe : o pour graphe orienté n pour graphe non orienté
troisième ligne
: une lettre indiquant le type de représentation du graphe : m pour matrice d'adjacence, l pour listes d'adjacence.
lignes suivantes
: les lignes de la matrice ou la suite des listes.
Le programme ignore les blancs en trop (espace ou tabulation) et crée un graphe à partir de ce fichier.

Erreurs de fichier :

1.4.2   Formats de sortie

Tous les entiers indiqués sur une même ligne sont séparés par un unique caractère blanc. Toutes les lignes se terminent par \n.

Les fichiers de format GRAPHE
Ce fichier est créé par la fonction de Warshall-Floyd. Le résultat de cet algorithme est un graphe représenté par une matrice d'adjacence. Ce fichier est donc identique à celui decrit précédemment.

Les fichiers de format ARBRE Ce fichier est créé par les fonctions sur les arbres recouvrant minimums.
première ligne
: le nombre d'arcs
deuxième ligne
: le poids de l'arbre
lignes suivantes
: sur chaque ligne, un des arcs de l'arbre recouvrant (indiqué par un couple de sommets en ordre croissant), les différents couples étant triés dans l'ordre croissant.

Les fichiers de format LISTE
Sur chaque ligne, une liste des sommets.
S'il y a plusieurs réponses, les lignes sont triées et rangée dans l'ordre croissant.

Les fichiers de format TRI
première ligne
: les états réalisables au début (sommets sans contraintes, en ordre croissant)
lignes suivantes
: sur chaque ligne, la liste des sommets (en ordre croissant) réalisables si ceux de la ligne précédente (et ceux au-dessus) sont réalisés (pour un graphe donné, ce fichier est unique).

Chapter 2   Construction des graphes et fonctions utiles

2.1   Structures de données

2.1.1   Graphe

Un graphe peut être représenté par une liste ou une matrice d'adjacence. Nous avons donc fait une union pour pouvoir utiliser l'une des deux repr{esentations en gardant le même nom de type.
typedef union
{
  int ** matrice;
  Liste * liste;
}Format;
La structure du graphe comporte toutes les informations fournies par le fichier GRAPHE d'entrée.
typedef struct
{
  int nb_sommets;
  char type;          // oriente ou non
  char format;        // liste ou matrice d'adjacence
  Format adjacence;
}Graphe;
Comme nous connaissons le nombre de sommets du graphe, nous allouons exactement la place nécessaire pour le graphe.

2.1.2   Liste d'adjacence

La liste d'adjacence est représentée par un tableau de nb_sommets listes. Chaque cellule d'une liste représente une arête du graphe. Soit la liste i (i est l'indice du tableau où se trouve cette liste). Chacune de ses cellules indique le sommet et le coût de l'arête (i, sommet).
typedef struct _cellule
{
  int cout;
  int sommet;
  struct _cellule * suivant;
}Cellule, * Liste;

2.1.3   Matrice d'adjacence

La matrice d'adjacence est représentée par un tableau à deux dimensions :
- une matrice carrée de taille nb_sommets*nb_sommets pour le graphe orienté.
- une matrice triangualire inférieur de nb_sommets lignes pour le graphe non orienté (à chaque ligne nous diminuons le nombre de colonnes).

Remarque :
Pour un graphe non orienté nous devrions avoir une matrice triangulaire supérieur. Nous avons donc un décalage d'indice dans notre représentation. Le calcul est toutefois simple : sommet = i + j avec i le numéro de la ligne et j le numéro de la colonne de notre matrice.

2.1.4   Constantes

Dans notre programme nous avons défini plusieurs constantes pour indiquer certains aspects d'un graphe.

2.2   Construction du graphe à partir d'un fichier

Nous avons deux types de graphe (orienté et non orienté) et deux représentation (liste et matrice d'adjacence). Il nous faut donc distinguer quatre constructions possibles.
De plus pour faciliter par la suite l'application de certains algorithmes (comme Dijkstra) nous vérifions que le graphe est valué positivement.

2.2.1   Fichier2graphe

La fonction fichier2graphe vérifie les trois premières lignes du fichier (erreur si format ou type inconnu, nombre de sommets négatif ou nul), remplit les champs de la structure Graphe et appelle une des fonctions de constructions du graphe en fonction du type et du format.

Arguments : Valeur de retour : Complexité :
La complexité de cette fonction dépend de celle de la fonction de construction appelée. Elle est soit en 0(n) avec n le nombre d'arcs soit en O(n2) avec n le nombre de sommets.

2.2.2   Liste d'adjacence

Nous avons les fonctions graphe_o_liste et graphe_n_liste qui fabriquent une liste d'adjacence.

Arguments : Valeur de retour : Ces deux fonctions sont pratiquement identiques à quelques conditions près.

Algorithme :
Nous allouons un tableau de listes de taille nb_sommets (allocation avec calloc pour initialiser les listes à NULL).
De i variant de 1 à nb_sommets : Nous vérifions aussi qu'il n'y ait rien à la fin du fichier.

Pour le graphe non orienté nous regardons en plus que le sommet lu dans la boucle ne soit pas supérieur à i (numéro de l'autre sommet de l'arète).

Complexité :
Les tests, les affectations, les allocations sont des opérations constantes. Nous parcourons toutes les lignes du fichier. Au mieux, nous avons une complexité en O(n) avec n le nombre de sommets dans le graphe. Au pire nous avons également une complexité en O(n) mais avec n le nombres d'arcs dans le graphe.

2.2.3   Matrice d'adjacence

Nous avons les fonctions graphe_o_matrice et graphe_n_matrice qui construisent une matrice d'adjacence.

Arguments : Valeur de retour : Ces deux fonctions sont quasiment identiques. La seule différence est que pour le graphe non orienté nous avons une variable qui diminue le nombre de colonnes à chaque entrée de la boucle pour finalement obtenir une matrice triangulaire.

Algorithme :
Nous allouons un tableau de tableaux de taille nb_sommets.
De i variant de 1 à nb_sommets : Nous vérifions aussi qu'il n'y ait rien à la fin du fichier.

Complexité :
Les tests, les affectations, les allocations sont des opérations constantes. Nous parcourons le fichier pour remplir toute la matrice donc la complexité est en 0(n2) avec n le nombre de sommets dans le graphe.

2.3   Conversion du graphe d'un format à l'autre

Certains algorithmes sur les graphes fonctionnent plus rapidement ou sont plus facile à écrire avec un type de représentation en mémoire particulier. De ce fait il nous est utile de pouvoir convertir les formats des graphes. Ces conversions ne sont pas difficiles à faire étant donné auà ce stade les coûts et les sommets sont corrects. Le seul problème qui peut se poser c'est celui de la place mémoire.
Les fonctions de conversion prennents les mêmes arguments et retournent les mêmes valeurs.

Arguments : Valeur de retour : A la fin de ces fonctions le graphe source existe toujours. Il faut le libérer dans la fonction qui appelle une des fonctions de conversion puisque nous n'en avons plus besoin.

2.3.1   D'une matrice à une liste

La fonction matrice2liste affecte aux champs du graphe destination ceux du graphe source en changeant évidemment le champs format. Elle alloue le tableau de listes et appelle une des deux fonctions de conversion qui suivent en fonction du type du graphe.
Les fonctions o_matrice2liste et n_matrice2liste se ressemblent beaucoup. Pour le graphe non orienté les indices de la matrice triangulaire sont décalés, il faut y faire attention.

Algorithme :
Pour chaque case de la matrice, si le coût n'est pas nul nous ajoutons le sommet et le coût dans la liste correspondante.

Complexité :
Les tests, les affectations, les allocations sont des opérations constantes. Nous parcourons toute la matrice donc la complexité est en 0(n2) avec n le nombre de sommets dans le graphe.

2.3.2   D'une liste à une matrice

La fonction liste2matrice remplit les champs du graphe destination avec ceux du graphe source en modifiant le champs format. Elle alloue le tableau de tableaux (de int) et appelle une des deux fonctions de conversion qui suivent en fonction du type du graphe.
Les fonctions o_liste2matrice et n_liste2matrice sont assez simples. Pour le graphe non orienté nous avons une variable qui diminue pour obtenir la matrice triangulaire.

Algorithme :
Pour chaque ligne de la matrice, nous allouons la ligne (allocation avec calloc pour initialiser les cases à 0). Nous parcourons la liste correspondante à la ligne et pourélément de la liste, nous récupérons le coût et nous l'affectons au sommet correspondant.

Complexité :
Nous parcourons toutes les listes. Chaque cellule représente un arc donc la complexité est en 0(n) avec n le nombre de sommets ou d'arcs dans le graphe.

2.4   Fonctions diverses sur les graphes

2.4.1   Libération du graphe

Si le graphe est représenté par une liste d'adjacence, nous libérons chaque liste par la fonction récursive liberer_liste puis nous libérons le tableau de listes. La complexité est donc en O(n) avec n le nombre de sommets ou d'arcs dans le graphe
Si le graphe est une matrice d'adjacence, nous libérons chacune de ses lignes puis le tableau. La complexité est en O(n) avec n le nombre de sommets.

2.4.2   Connexité du graphe

Pour appliquer les algorithmes sur les graphes non orientés il faut que les graphes soient connexes, qu'il soit en un seul morceau.
Pour vérifier cela nous eesayons de voir si nous pouvons atteindre tous les sommets par un seul parcours.

Comme nous voulons regarder dès le début si le graphe est connexe nous avons écrit deux fonctions de parcours, un pour une représentation en liste d'adjacence, un pour une représentation en matrice.
Les fonctions parcours_liste_prefixe et parcours_matrice_prefixe parcourent le graphe et comptent le nombre de sommets visités.
La fonction graphe_connexe appelle l'une des deux fonctions précédentes en fonction du format du graphe et compare le nombre de sommets visités avec le nombre de sommets total dans le graphe. Elle retourne 1 si le graphe est connexe, 0 sinon. La complexité de cette fonction dépend de la complexité de la fonction appelée, c'est-à-dire en O(n) pour une liste avec n le nombre d'arcs et en O(n2) pour une matrice avec n le nombre de sommets.


Chapter 3   Algorithmes sur les graphes

3.1   Graphe non orienté

A l'exécution des alogorithmes sur les graphes non orientés, nous supposons que le graphe passé en argument est bien non orienté et connexe.

3.1.1   Algorithme de Kruskal

La fonction Kruskal construit l'arbre couvrant minimal d'un graphe représenté par une liste d'adjacence. Pour cela nous essayons de construire un arbre avec nb_sommets-1 arcs sans cycle. Comme le graphe est connexe, nous pouvons construire cet arbre.

Arguments : Valeur de retour : Structures de données : Algorithme :
Au début nous considérons que chaque sommet constitue un sous-arbre et le poids total de l'arbre recouvrant est initialisé à 0.
Tant que nous n'avons pas les nb_sommets-1 arêtes de l'arbre : Nous ecrivons dans le fichier le nombre d'arcs, le poids de l'arbre et les arcs (couple de sommets) en parcourant la matrice triangulaire.

La fonction Kruskal utilise la fonction fusionner_arbres pour relier les deux sous-arbres. Cette fonction remet à jour le le tableau numero qui indique le numéro du sous-arbre auquel appartient un sommet donc sa complexité est en O(n) avec n la taille du tableau soit nb_sommets.

Complexité :
Nous cherchons nb_sommets-1 arêtes parmi nb_aretes. Donc au pire nous avons une complexité en O(nb_sommets*max_aretes) soit en O(n3) avec n le nombre de sommets. Si le graphe n'a pas beaucoup d'arcs nous avons une complexité en O(n2) avec n le nombre de sommets car nous appellons nb_sommets la fonction fusionner_arbres qui est en O(n).

3.1.2   Algorithme de Prim

L'algorithme de Prim permet également de construire un arbre couvrant minimal mais d'un graphe repésenté par un matrice triangulaire (il faut faire attention aux indices).

Arguments : Valeur de retour : A la différence de la fonction Kruskal qui construisait plusieurs sous-arbres, la fonction Prim ne construit qu'un seul arbre. Elle y rajoute les sommets un par un. Le graphe étant connexe, tous les sommets du graphe seront ajouteés dans l'arbre.
Nous distinguons deux ensembles de sommets dans cet algorithme : Structures de données : Algorithme :
Nous considérons le sommet passé en paramtre comme le premier sommet de l'arbre. Nous initialisons donc le tableau plus_proche par ce sommet. Le tableau distance est donc initialisé par la ligne racine de la matrice triangulaire.
Tant qu'il y a encore des sommets en dehors de l'arbre : Nous ecrivons dans le fichier le nombre d'arêtes, le poids de l'arbre et les arêtess (couple de sommets) en parcourant la matrice triangulaire.

Complexité :
Nous recherchons le sommet s par parcours du tableau distance et nous effectuons ce parcours nb_sommets fois pour traiter tous les sommets du graphe. Donc la complexité de la fonction Prim est en O(n2) avec n le nombre de sommets dans le graphe.

3.1.3   Points d'articulation

Un sommet s est un point d'articulation du graphe G connexe si G privé de s n'est plus connexe.
Nous notons num[s] le numéro du sommet s. Pour chaque sommet s nous définissons bas[s] comme le plus petit numérod'un sommet t tel qu'il existe une arête (x, t) qui n'est pas dans l'arbre d'exploration A avec
num[t] £ num[s] £ num[x]
x est un descendant de s dans A (l'arc (x, t) est un arc arrière).
Si une telle arête n'existe pas nous posons bas[s]=num[s].

A partir de là, un sommet s est un point d'articulation si et seulement si: Nous avons notre algorithme.

Nous travaillons sur un graphe représenté par une liste d'adjacence.
Décrivons d'abord la fonction calculer_num_bas qui, comme l'indique son nom, calcule les valeurs des tableaux num et bas.

Arguments : Algorithme :
Soit s le sommet à traiter, nous initialisons num[s] et bas[s] à l'entier passé en paramètre. Nous incémentons cette variable.
Pour tous les successeurs t du sommet s dans le graphe : Complexité :
Cette fonction est récursive et s'appelle nb_sommets fois pour traiter tous les sommets du graphe (le graphe étant connexe tous les sommets seront traités). Pour chaque sommet nous regardons tous leurs successeurs et modifions le tableau bas (de taille nb_sommets). Si nous changeons à chaque appel toutes les valeurs du tableau bas, nous pouvons estimer au pire des cas la complexité à O(kn) avec k le nombre de sommets dans le graphe et n le nombre d'arêtes.

Pour calculer les points d'articulation d'un graphe il faut que ce graphe ait au moins trois sommets. Cette vérification est faite dans la fonction points_articulation.

Arguments : Valeur de retour : Algorithme :
Nous initialisons tous les tableaux à -1 et nous appelons la fonction calculer_num_bas pour le sommet 0.
Nous comparons les valeurs des tableaux num et bas, comme nous l'avons indiqué précédemment, à l'aide le tableau pere pour connaitre les fils des sommets (nous ignorons donc les sommets sans fils).
Nous écrivons les sommets qui sont des points d'articulation dans le fichier dans l'ordre croissant.

Complexité :
Les comparaisons et affectations sont des opérations constantes. Donc la comparaison des valeurs des tableaux se font en O(nb_sommets). S'ajoute la complexité de la fonction calculer_num_bas. Donc la complexité de la fonction poitns_articulation est en O(kn) avec k le nombre de sommets dans le graphe et n le nombre d'arêtes.


3.2   Graphe orienté

A l'exécution des alogorithmes sur les graphes orientés, nous supposons que le graphe passé en argument est bien orienté.

3.2.1   Algorithme de Dijkstra

L'algorithme de Dijkstra consiste à trouver tous les plus courts chemins ayant pour origine un sommet donné. Cet algorithme ne s'applique qu'à des graphes valués positivement. Nous l'appliquons à un graphe représenté par une liste d'adjacence.

Arguments : Structures de données : Par la suite nous appellerons S l'ensemble des sommets i pour lesquels la longueur optimale du plus court chemin de l'origine s à i est connue et E som complémentaire.

Algorithme : Nous initialisons le tableau distance à ¥ (nous aurions pu initialiser distance[i] au coût de l'arête (s, i mais cela revient au même de le faire plus tard dans la boucle). Nous mettons distance[s] à 0.
Tant qu'il y a au moins un sommet dans E : Pour tous les sommets [i] du graphe Complexité : Nous cherchons le plus court chemin d'un sommet donné vers les autres sommets donc nous calculons nb_sommets chemins.
Pour chaque chemin nous cherchons la plus petite distance parmi les sommets non traités. La complexité de la fonction Dijkstra est en O(n2) avec n le nombre de sommets dans le graphe.

3.2.2   Algorithme de Dijkstra avec un tas

Plusieurs algorithmes ont été développés pour améliorer la complexité de l'algorithme de Dijkstra notamment en introduisant une structure de tas pour choisir le sommet i entrant dans l'ensemble S à chaque étape.

Structure du tas :
Nous repésentons le tas par un tableau. Chaque élément du tableau contient un sommet et la distance du chemin allant de l'origine à ce sommet.
typedef struct
{
  int sommet;
  int distance;
}Element;

typedef struct
{
  Element * tableau;
  int nb_elements;
}Tas;
Nous commençons le tableau à 1 au lieu de 0 pour faciliter les calculs. Par conséquent tas.tableau[1] est la racine.
Nous considérons le tas comme un arbre binaire donc le sommet tas.tableau[i] du tas : Nous avons les fonctions : Nous allons voir plus en détails la réorganisation du tas dans les trois dernière fonctions. Nous avons ici trois réorganisation : L'algorithme de Dijkstra :
Arguments : Valeur de retour : Algorithme :
Nous initialisons les tableaux et crééons le tas. Nous y ajoutons l'origine s avec comme distance 0.
Tant que le tas n'est pas vide : Nous détruisons le tas.
Nous écrivons les résultats dans le fichier.

Complexité :
Avec le tas, la complexité de l'algorithme est amélioré. La fonction Dijkstra_tas est en O(nlogn).

3.2.3   Algorithme de Warshall-Floyd

L'algorithme de Warshall-Floyd donne les plus courts chemins entre n'importe quel couples de sommets. Nous l'appliquons sur un graphe représenté par une matrice d'adjacence.

Arguments : Structures de données : Algorithme :
Nous recopions la matrice d'adjacence dans la matrice cout. S'il n'y a pas d'arêtes entre deux sommets nous mettons le coût à l'infini.
Pour k variant de 0 à nb_sommets-1 : Nous recopions la matrice distance dans le fichier.

Complexité :
Nous cherchons un chemin pour chaque couple de sommets en passant par chaque sommet. Nous avons donc une complexité en O(n3) avec n le nombre de sommets dans le graphe.

3.2.4   Composantes fortement connexes

Un graphe est fortement connexe si pour tous sommets u et v il existe un chemin de u à v et de v à u. Un sous-graphe fortement connexe ayant un nombre maximal de sommet est appelé composante fortement connexe.Nous allons déterminer ces composantes à partir d'un graphe repésenté par une matrice.
Le choix de la représentation du graphe est important car nous devons parcourir le graphe transposé (les arcs (i,j) deviennent des arcs (j, i) ). Nous n'aurons pas à transformer le graphe car sa transposée est facile à obtenir par la matrice.


Arguments : Algorithme :
Nous effectuons un premier parcours en profondeur du graphe en notant les sommets dans un tableau à la fin de leur exploration. S'il y a encore des sommets non visités nous reprenons le parcours sur le plus petit sommet.
Nous effectuons un deuxième parcours en profondeur mais sur le graphe retourné cette fois. Nous faisons un parcours en préfixe avec comme sommet de départ le dernier sommet du tableau obtenu par le premier parcours. S'il y a encore des sommets non visités nous recommençons le parcours avec le dernier sommet non visité du tableau. Lors de ce deuxième parcours nous indiquons à quelle composante connexe appartient chaque sommet par un numéro.
Nous écrivons chaque composante connexe dans le fichier dans l'ordre croissant des sommets.

Complexité :
Nous faisons plusieurs parcours en profondeur. Le parcours en profondeur s'effectue en O(n) avec n le nombre de sommets. A la fin des parcours nous obtenons un tableau indiquant pour chaque sommet à quelle composante connexe il fait partie. Pour afficher les composantes trièes dans l'ordre nous devons parcourir ce tableau autant de fois qu'il y a de composantes fortement connexes. Donc au pire des cas nous avons une complexité en O(n2) avec n le nombre de sommets dans le graphe.

3.2.5   Tri topologique

Le tri topologique indique l'ordre dans lequel les états (sommets) d'un graphe peuvent se réaliser en sachant que certains sont réalisable en même temps (nous les trions dans ce cas là).

Arguments : Valeur de retour : Comme nous souhaitons les suites de sommets dans l'ordre croissant nous n'utiliserons pas un ensemble S pour les sommets non traités (comme dans Dijkstra) qui risquent de les mélanger mais plutôt un marqueur. Nous choisissons donc de parcourir le tableau predecesseur (qui indique le nombre de prédécesseurs pour un sommet) plusieurs fois ce qui implique une complexité pouvant aller jusqu'à O(n2).

Algorithme :
Nous indiquons dans un tableau predecesseur le nombre de prédècesseurs pour chaque sommet.
Tant que nous n'aurons pas traité tous les sommets : Complexité :
Nous parcourons le tableau predecesseur de taille nb_sommets autant de fois qu'il y a d'étapes dans le tri topologique. Dans le pire des cas si nous n'avons qu'un sommet par étape nous aurons nb_sommets étapes et donc nous aurons une complexité en O(n2).


Chapter 4   Gestion de la ligne de commande

La gestion de la ligne de commande se fait en grande partie dans la fonction principale main. Comme les éléments de la ligne de commande se trouvent dans les arguments du main il est inutile d'écrire une fonction avec comme paramètres ceux de main. Toutefois la reconnaissance des options et l'appel des fonctions d'algorithme sont faites par des fonctions définies dans les fichiers option.h et option.c.

4.1   Analyse de la ligne de commande

La ligne de commande contient au moins une option. Les noms des fichiers sont facultatifs.

Nous vérifions le nombre d'arguments sur la ligne de commande. Il faut :

4.1.1   Analyse des options

Nous analysons d'abord l'argument des options qui doit être en deuxième position sur la ligne de commande. Nous indiquons à l'aide d'un tableau de type Booleen quelles options sont demandées. Cette analyse est faite par la fonction reconnaitre_options :

Arguments : Valeur de retour : Algorithme :
Nous initialisons le tableau options à FAUX pour indiquer qu'aucune option n'est demandée.
La chaîne doit commencer par le caractère -et avoir une lettre à la deuxième position.
Pour tous les caractères de cette chaîne, nous regardons si l'option existe : Complexité :
Nous parcourons toutes la chaines pour reconnaitre les options. Donc la complexité est en O(n) avec n la longueur de la chaine.

Nous avons ainsi le tableau des options, il nous reste plus qu'à le parcourir et exécuter les algorithmes.

4.1.2   Analyse des autres arguments

Les arguments autres que le nom de l'excutable et les options n'ont pas de place précise sur la ligne de commande. Chaque argument ne doit être présent qu'une seule fois sur la ligne de commande.
Nous considérons qu'un nom de fichier ne peux pas être un nombre et que si nous avons un nombre sur la ligne de commande alors il correspond à un sommet.

Après avoir sauvé ces arguments dans des variables, nous les analysons : Enfin nous pouvons créer le graphe et appliquer nos algorithmes.

4.2   Exécution du programme

4.2.1   Création du graphe

Le graphe est créé à partir du fichier d'entrée. Si ce fichier n'existe pas nous utilisons l'entrée standard.
Nous appelons la fonction fichier2graphe pour créer le graphe. S'il y a une erreur lors de la construction du graphe nous le libérons et sortons du programme.
Nous vérifions que les options demandées sont appliquables au graphe construit.

4.2.2   Exécution des algorithmes

Nous avons deux cas à distinguer : les graphes orientés et les graphes non orientés.
Pour chacun des cas, L'ordre d'exécution des algorithmes dépend du format du graphe.
Par exemple, si nous avons un graphe représenté par une matrice nous effectuons d'abord les algorithmes qui s'appliquent sur les matrices d'adjacence puis nous convertissons le graphe en liste d'adjacence pour pouvoir y aplliquer les autres algorithmes.

Voici donc une partie de la fonction main concernant l'exécution des algorithmes : Pour ne pas surcharger la fonction main, nous avons écrit quatre fonctions qui regroupent les algorithmes selon leur type et format : Ces fonctions ont à peu près le même prototype et le même algorithme : Arguments : Algorithme :
Le fichier de sortie est initialisé à la sortie standard.
Pour chaque algorithme : La seule erreur que nous pouvons rencontrer dans l'appel de ces fonctions est l'impossibilité de créer les fichiers de sortie. Cela peut être un problème de droits donc si nous avons une erreur pour l'un des fichiers de sortie, le programme ne s'arrête pas et passe à l'algorithme suivant. Ainsi nous exécutons le plus d'algorithmes possibles.

Complexité :
La complexité de ces fonctions dépendent de celle des fonctions appelées.


This document was translated from LATEX by HEVEA.