Structure de graphe
par Philippe Chassignet

Introduction

Le but de ce TD est de familiariser avec la structure de graphe. Les deux premières parties sont une application directe du cours. On va instancier un graphe avec une représentation matricielle et son utilisation se fera par le biais d'une classe abstraite plus générale. On programmera ainsi quelques algorithmes classiques vus en cours.

On aura ensuite à instancier d'autres représentations qui réalisent la même classe abstraite.

La classe Arc

Pour tout ce TD, un objet de la classe Arc servira à coder un arc d'un graphe orienté. On considère pour l'instant que les noeuds sont identifiés par des entiers. Un arc est alors défini par trois entiers qui représentent les deux sommets origine et destination et une longueur. On fournit cette classe Arc minimale, avec : Il sera indiqué plus loin quand des modifications de cette classe seront nécessaires.

Graphe avec représentation matricielle

1. Une premier graphe

Définir une classe GrapheMatrice, dont un objet est représenté avec un tableau private Arc[][] arcs;, avec un constructeur GrapheMatrice(int n). Le paramètre n indique le nombre maximal de sommets, ce qui permet de dimensionner le tableau, ce nombre sera mémorisé dans un champ private final int maxS;. Le graphe ainsi construit pourra avoir au maximum n sommets, identifiés par les entiers de 0 à n-1. Une référence arc[i][j] est soit null, soit un arc de i vers j.

Compléter avec les méthodes d'objets :

On testera avec :
public static void test() {
  GrapheMatrice g = new GrapheMatrice(10);
  g.ajouterArc(new Arc(0, 2));
  g.ajouterArc(new Arc(1, 2));
  g.ajouterArc(new Arc(2, 3));
  g.ajouterArc(new Arc(2, 4));
  g.ajouterArc(new Arc(3, 0));
  System.out.println(g.existeArc(0, 1)+" "+g.existeArc(0, 2));
  System.out.println(g.arc(0, 1)+" "+g.arc(0, 2));
  System.out.println(g.maxSommets());
  System.out.println(g);
}
qui doit donner une sortie de la forme :
false true
null 0 -> 2
10
---------------
0 -> 2
1 -> 2
2 -> 3
2 -> 4
3 -> 0
---------------
Les lignes --------------- sont produites par toString() pour encadrer le détail des arcs.

2. Abstraction

Modifier le programme précédent de la façon suivante : Le test est inchangé mais il peut être déplacé dans la classe Graphe.

3. Opérations de base

Ajouter, dans la classe Graphe, la fonction static void copie(Graphe g1, Graphe g2) qui, en partant d'un graphe g1 construit et défini, et d'un graphe g2 construit de taille suffisante (et supposé vide), ajoute dans g2 une copie de chaque arc de g1. On utilisera la fonction copie de la classe Arc.

Sur le même principe, écrire la fonction static void reciproque(Graphe g1, Graphe g2) qui, pour tout arc (i,j) de g1, construit un arc (j,i) dans g2.

On testera avec l'exemple précédent.

public static void test() {
  GrapheMatrice g = new GrapheMatrice(10);
  g.ajouterArc(new Arc(0, 2));
  g.ajouterArc(new Arc(1, 2));
  g.ajouterArc(new Arc(2, 3));
  g.ajouterArc(new Arc(2, 4));
  g.ajouterArc(new Arc(3, 0));
  System.out.println("graphe :");
  System.out.println(g);
//    test pour question 3
  System.out.println("copie :");
  GrapheMatrice g2 = new GrapheMatrice(g.maxSommets());
  copie(g, g2);
  System.out.println(g2);
  System.out.println("reciproque :");
  GrapheMatrice gr = new GrapheMatrice(g.maxSommets());
  reciproque(g, gr);
  System.out.println(gr);
}
qui doit donner :
graphe :
---------------
0 -> 2
1 -> 2
2 -> 3
2 -> 4
3 -> 0
---------------
copie :
---------------
0 -> 2
1 -> 2
2 -> 3
2 -> 4
3 -> 0
---------------
reciproque :
---------------
0 -> 3
2 -> 0
2 -> 1
3 -> 2
4 -> 2
---------------

Algorithmes classiques

4. Algorithme de Roy-Warshall

Toujours dans la classe Graphe, écrire la fonction static void fermetureTransitive(Graphe g1, Graphe g2) qui, en partant d'un graphe g1 construit et défini, et d'un graphe g2 construit (et supposé vide), ajoute dans g2 tous les arcs de la fermeture transitive de g1. Ainsi, l'existence d'un arc de i à j dans g2 correspond à l'existence d'un chemin de i à j dans g1. En particulier, un arc de i à i dans g2 correspond à l'existence d'un circuit passant par i dans g1.
On adaptera l'algorithme de Roy-Warshall vu en cours. Avec l'exemple précédent, on doit obtenir :
---------------
0 -> 0
0 -> 2
0 -> 3
0 -> 4
1 -> 0
1 -> 2
1 -> 3
1 -> 4
2 -> 0
2 -> 2
2 -> 3
2 -> 4
3 -> 0
3 -> 2
3 -> 3
3 -> 4
---------------

5. Algorithme de Floyd

On s'intéresse maintenant aux plus courts chemins, c'est-à-dire que l'on considère des graphes dont les arcs ont une longueur strictement positive. Comme on le voit dans l'exemple ci-dessous, on obtient de tels arcs en utilisant le constructeur avec un troisième paramètre. On notera également que la méthode copie de la classe Arc copie aussi le champ longueur.

Écrire la fonction static void plusCourtChemins(Graphe g1, Graphe g2) qui réalise l'algorithme de Floyd. Dans le résultat g2, la longueur d'un arc de i à j sera celle d'un plus court chemin de i à j dans g1. La longueur d'un arc de i à i sera celle d'un plus court circuit passant par i dans g1.

On testera avec :

GrapheMatrice g = new GrapheMatrice(10);
g.ajouterArc(new Arc(1, 2, 9));
g.ajouterArc(new Arc(1, 3, 2));
g.ajouterArc(new Arc(2, 4, 4));
g.ajouterArc(new Arc(3, 2, 3));
g.ajouterArc(new Arc(3, 4, 8));
g.ajouterArc(new Arc(3, 5, 7));
g.ajouterArc(new Arc(5, 1, 4));
g.ajouterArc(new Arc(5, 4, 3));
GrapheMatrice gf = new GrapheMatrice(g.maxSommets());
plusCourtChemins(g, gf);
System.out.println(gf);
qui doit donner :
---------------
1 -> 1 : 13
1 -> 2 : 5
1 -> 3 : 2
1 -> 4 : 9
1 -> 5 : 9
2 -> 4 : 4
3 -> 1 : 11
3 -> 2 : 3
3 -> 3 : 13
3 -> 4 : 7
3 -> 5 : 7
5 -> 1 : 4
5 -> 2 : 9
5 -> 3 : 6
5 -> 4 : 3
5 -> 5 : 13
---------------

6. Mémoriser les chemins

On veut maintenant garder la trace des plus courts chemins. En préliminaire, on va ajouter un champ via aux objets de la classe Arc et modifier les constructeurs en consésenquence. Pour un arc (i,j) de la fermeture transitive, le champ via indiquera le premier sommet après i sur l'un des plus courts chemins menant de i à j.
On pourra ensuite définir la fonction static void initVia(Graphe g1, Graphe g2) qui, pour chaque arc de i à j de g1, construit un arc i à j via j de même longueur dans g2.
Enfin, on adaptera une fonction construitPlusCourtChemins, sur le modèle de plusCourtChemins, pour calculer les valeurs du champ via pour les arcs construits par l'algorithme de Floyd.

Avec l'exemple précédent, on doit obtenir :

---------------
1 -> 1 : 13 via 3
1 -> 2 : 5 via 3
1 -> 3 : 2 via 3
1 -> 4 : 9 via 3
1 -> 5 : 9 via 3
2 -> 4 : 4 via 4
3 -> 1 : 11 via 5
3 -> 2 : 3 via 2
3 -> 3 : 13 via 5
3 -> 4 : 7 via 2
3 -> 5 : 7 via 5
5 -> 1 : 4 via 1
5 -> 2 : 9 via 1
5 -> 3 : 6 via 1
5 -> 4 : 3 via 4
5 -> 5 : 13 via 1
---------------

7. Lister les chemins

Il reste à expliciter les plus courts chemins ainsi trouvés. Écrire la fonction static void listerChemin(Graphe g, int i, int j) qui liste le détail du chemin de i à j en reprenant les informations via du graphe.

Avec l'exemple précédent et

listerChemin(gf, 5, 1);
listerChemin(gf, 5, 2);
listerChemin(gf, 5, 5);
listerChemin(gf, 4, 5);
on doit obtenir un résultat équivalent à :
Chemin de 5 a 1 (longueur 4) : 5 1
Chemin de 5 a 2 (longueur 9) : 5 1 3 2
Chemin de 5 a 5 (longueur 13) : 5 1 3 5
Pas de chemin de 4 a 5
Remarque
On pourrait faire d'autre choix pour le champ via, soit le dernier sommet avant j, soit n'importe quel sommet intermédiaire, sur l'un des plus courts chemins menant de i à j. Dans ces deux cas, une fonction listerChemin récursive s'impose.

D'autres instantiations des graphes

8. Généralisation

Écrire la classe GrapheTables extends Graphe dans laquelle la notion de tableau est remplacée par celle de table. Les arcs issus d'un même sommet sont mémorisés dans une table et le graphe est une table de ces tables. On utilisera pour cela des objets de la classe prédéfinie Hashtable. Les opérations élémentaires sur une telle table se font par ses méthodes put et get. Dans notre cas, ce sont les numéros des sommets qui servent de clefs. On remplacera donc le type tableau Arc[][] par Hashtable<Integer,Hashtable<Integer,Arc>>.

Les tests restent les mêmes et on peut mixer les déclarations par exemple,

GrapheMatrice g = new GrapheMatrice(...);
....
GrapheTables gf = new GrapheTables(...);
fermetureTransitive(g, gf);
ou
GrapheTables g = new GrapheTables(...);
....
GrapheMatrice gf = new GrapheMatrice(...);
fermetureTransitive(g, gf);

9. Parlons un peu d'efficacité

Dans le cas de clefs entières, les opérations put et get ont un coût O(1) si la table est dimensionnée assez grande. Il s'agit aussi d'éviter une expansion de la table qui se déclenche automatiquement lorsque le taux de remplissage dépasse le seuil de 75%.
On utilisera le constructeur Hashtable(int initialCapacity) pour construire une table principale de dimension suffisante, en fonction de ce seuil et du paramètre n du constructeur.

Cette solution s'impose aussi pour les sous-tables dans le cas d'un graphe "plein". On définira et on utilisera une méthode d'objet Hashtable<Integer,Arc> construitSousTable() pour construire les sous-tables. On dispose alors de maxSommets() pour les dimensionner.

Les tests restent les mêmes.

Remarque
L'efficacité reste très relative et, pour un graphe "plein" avec des sommets identifiés par des entiers, une table de hachage sera toujours moins efficace qu'un tableau. L'instanciation GrapheMatrice est donc plus efficace que GrapheTables.
L'intérêt des tables va apparaître dans ce qui suit et notamment à la question 12.

10. Et la mémoire ?

Pour commencer, on peut éviter de construire les sous-tables a priori. Modifier GrapheTables pour que cette construction se fasse par nécessité dans ajouterArc.

Dans le cas d'un graphe "creux", il est préférable d'utiliser des sous-tables plus petites pour économiser la mémoire. On va donc écrire une classe GrapheTablesCreux extends GrapheTables avec un constructeur particulier pour préciser également la taille initiale estimée des sous-tables.
On devra donc redéfinir la méthode construitSousTable().

Les tests restent les mêmes, pour les deux classes.

11. Toujours plus efficace

Dans le cas d'un graphe "creux", une boucle
  for ( int j = 0 ; j < g.maxSommets() ; ++j )
    if ( g.existeArc(i, j) ) {
      Arc a = g.arc(i, j)
      ...
    }
n'est pas particulièrement efficace. Il est préférable de la remplacer par un boucle qui utilise un itérateur sur les arcs ayant le sommet i comme origine. On ajoute pour cela, dans la classe Graphe, la déclaration
  abstract Iterable<Arc> sortant(int origine);
et on peut alors écrire une boucle du genre for ( Arc a : g.sortant(i) ) qui intervient de manière naturelle dans de nombreux algorithmes.

Pour GrapheMatrice, on retournera un Vector (qui étend Iterable), sans trop se soucier de l'efficacité (l'itérateur sur un Vector est efficace mais il faudra remplir ce vecteur).

La réalisation de sortant est relativement triviale pour GrapheTables, la fonction values() d'une Hashtable retourne une Collection qui étend Iterable. L'itérateur associé est alors relativement efficace si la table est bien remplie.
On devra juste faire attention au cas où le sommet i n'a pas d'arc sortant. La fonction sortant ne doit pas retourner null sinon on a une erreur dans la boucle for. Dans le cas où il n'y a pas d'arc sortant, la fonction doit retourner un Iterable (par exemple un Vector) construit mais vide et mémorisé en statique. On peut aussi utiliser Collections.emptyList() qui est conçue pour retourner un tel objet.

À titre d'exemple, on modifiera les fonctions toString et copie.

Geek's zone

12. Un graphe de mots

Les clefs d'une Hashtable peuvent être de type très varié, en particulier String. Pour faire simple, on va recopier dans un nouveau fichier les classes Arc, Graphe, GrapheTables et GrapheTablesCreux et y remplacer tout ce qui concerne le type des sommets par String. On pourra notamment tester ce petit exemple :
GrapheTablesCreux g = new GrapheTablesCreux(10, 3);
g.ajouterArc(new Arc("zero", "deux"));
g.ajouterArc(new Arc("un", "deux"));
g.ajouterArc(new Arc("deux", "trois"));
g.ajouterArc(new Arc("deux", "quatre"));
g.ajouterArc(new Arc("trois", "zero"));
System.out.println("graphe :");
System.out.println(g);
System.out.println("copie :");
GrapheTablesCreux g2 = new GrapheTablesCreux(g.maxSommets(), 3);
copie(g, g2);
System.out.println(g2);
On notera que pour cela, il faut aussi se donner un moyen d'itérer sur les sommets du graphe qui sont des origines d'arcs.

13. Un graphe générique

On va maintenant refaire la même chose en définissant des classes génériques.
Dans un premier temps, on va faire une classe Arc générique qui permettra déjà le test suivant :
System.out.println(new Arc<Integer>(0, 1));
System.out.println(new Arc<Integer>(0, 1, 2, 3));
System.out.println(new Arc<Integer>(0, 1, 2).copie());
System.out.println(new Arc<String>("foo", "bar", 2));
System.out.println(new Arc<String>("foo", "bar", 2, "anywhere"));
Ensuite, on pourra écrire les classes de graphes, avec un test du style :
Graphe<Integer> g = new GrapheTablesCreux<Integer>(10, 3);
g.ajouterArc(new Arc<Integer>(0, 2));
......
System.out.println(g);
......
Graphe<String> gs = new GrapheTablesCreux<String>(10, 3);
gs.ajouterArc(new Arc<String>("zero", "deux"));
......
System.out.println(gs);
Graphe<String> gs2 = new GrapheTables<String>(gs.maxSommets());
copie(gs, gs2);
System.out.println(gs2);