Le parcours en largeur n'est pas un pré-requis pour ce TP. Il faut par contre avoir compris les structures de données fournies. Si vous ne les avez pas encore faites, commencez par faire le début du TP1 avant de vous lancer dans le TP2 :

Consignes

Le TP est à rendre (par email) pour le dimanche 12 décembre à 23h59

La pièce la plus importante sera un fichier tp2-nom-prenom.c contenant votre programme. Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront également pris en compte :

  1. la lisibilité de votre programme (choix pertinent pour les noms de variables, indentation etc.),
  2. la présence de commentaires aux endroits appropriés,
  3. ...

Les réponses aux questions posées dans le TP (complexité de vos fonctions par exemple) seront insérées comme commentaires dans votre fichier principal.

Si vous le souhaitez, vous pouvez aussi envoyer un rapport de TP. Le format de ce rapport sera au choix, mais par ordre de préférence :

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Estimation du temps

Liens utiles

Préliminaires

  1. Téléchargez l'archive du TP.
  2. La compilation se fait avec le fichier Makefile fourni comme pour le TP1. Il suffit de modifier la variable NOM pour prendre en compte votre propre fichier.
  3. Aucune fonction de test n'est fournie pour ce TP. Vous devrez donc vous débrouiller pour tester vos fonctions au fur et à mesure. (Par contre, ce n'est pas la peine de m'envoyer votre fonction principale.)

1. Le tri topologique

Nous avons vu (oups, « nous allons voir ») pendant le TD2 l'algorithme du « tri topologique ». Cet algorithme permet de linéariser un graphe orienté sans cycle et fonctionne de la manière suivante : on effectue un parcours en profondeur et on trie les sommets par ordre de « fin[] » décroissant.

Écrivez la fonction triTopologique de prototype 

int triTopologique(GrapheListe G, int *S) ;

Les consignes sont les suivantes :

  • le tri sera stocké dans le tableau S[]. S'il faut prendre les sommets dans l'ordre 4, 1, 0, 3, 5, 2, on aura alors S[0]=4, S[1]=1, S[2]=0, S[3]=3, S[4]=5, S[5]=2.
  • Si le graphe donné en argument contient un cycle, alors votre fonction devra renvoyer un entier strictement supérieur à 0 ; sinon, elle renverra la valeur 0.
  • Votre fonction devra être la plus simple possible et n'utilisera pas les listes chaînées comme structure intermédiaire.
  • Dans le cas où le graphe contient un cycle, le tableau S contiendra une « approximation » d'un tri topologique...

(N'oubliez pas de documenter ce que vous faites...)

Estimez la complexité de votre fonction.

Si le tableau S fourni en argument est égal à NULL, votre fonction devra seulement chercher si G a des cycles : elle renverra 0 si G n'a pas de cycle et un nombre strictement positif si G a au moins un cycle.

2. Composantes connexes

2.1. Graphes non-orientés (Bonus)

Calculer les composante connexes dans un graphe non-orienté se fait facilement avec un parcours.

(Bonus)

Écrivez une fonction pour calculer les composantes connexes d'un graphe non-orienté : 

int composantesConnexes(GrapheListe G, int *CC) ;
Sa valeur de retour sera le nombre de composantes fortement connexes du graphe G, et l'argument CC sera un tableau que l'on remplira avec les numéro de composantes fortement connexes : si le sommet s est dans la composante connexe c, alors après l'appel à la fonction on aura CC[s] == c.

2.2. Graphes orientés

Une composante fortement connexe dans un graphe orienté est un ensemble maximal de sommets qui vérifie la propriété suivante : « il existe un chemin orienté de n'importe quel sommet vers n'importe quel autre ».

Une manière de calculer les composantes fortement connexe du graphe G est de procéder comme suit :

  1. faire un parcours en profondeur du graphe G
  2. calculer G', le transposé de G
  3. faire un parcours (en largeur ou en profondeur) de G', en prenant les sommets par ordre de fin[] décroissant. (L'ordre de fin[] est donné par le parcours de G.)
  4. chaque arbre de la foret couvrante donné par le second parcours correspond exactement à une composante fortement connexe.

Programmer la fonction de prototype : 

int composantesFortementConnexes(GrapheListe G, int *CC) ;
Sa valeur de retour sera le nombre de composantes fortement connexes du graphe G, et l'argument CC sera un tableau que l'on remplira avec les numéro de composantes fortement connexes : si le sommet s est dans la composante connexe c, alors après l'appel à la fonction on aura CC[s] == c.

Comme pour la question 1, essayer d'avoir un code le plus simple possible et documentez bien ce que vous faites.

3. Graphes bipartis (Bonus)

Un graphe non-orienté est biparti si on peut séparer ses sommets en deux sous-ensembles S et T qui ont la propriété suivante :

Autrement dit, toutes les arêtes sont incidentes à un sommet de S et un sommet de T.

Pour faire ceci, le plus simple est d'utiliser un parcours en largeur :

(Bonus) Écrivez une fonction 

int*biparti(GrapheListe G) ;
pour calculer vérifier si un graphe est biparti ou non.

Si le graphe n'est pas biparti, votre fonction devra renvoyer NULL ; sinon, elle renverra un tableau contenant, pour chaque sommet, son ensemble :