Le type Graphe

Comme pour les autres structures de données, il faut distinguer un type abstrait, l'interface Graphe, qui déclare des méthodes publiques, et des types qui implémentent cette interface, par exemple, les classes GrapheParMatrice et GrapheParListe que nous discuterons bientôt. Ces types seront rassemblés dans un paquet graphe, qui pourra être utilisé de la façon suivante :

import graphe;

class GrapheDemo {
  public static void main(String[] args) {
    Graphe g = new GrapheParMatrice(4);
    g.ajouteArc(0,1);
    g.ajouteArc(1,2);
    g.ajouteArc(2,3);
    g.ajouteArc(3,0);
    g.ajouteArc(0,2);
    g.ajouteArc(3,1);
    g.ajouteArc(1,1);
    // ...
  }
}

Cet exemple déclare une variable g de type Graphe ; le choix d'une implémentation se fait via un constructeur, ici GrapheParMatrice ; ce constructeur prend en argument la taille du graphe, c'est-à-dire le nombre de ses sommets. Une fois ce constructeur invoqué, g désigne un graphe à 4 sommets, sans arcs. Il est commode, pour spécifier un arc, de disposer d'une numérotation des sommets par un indice commençant par 0 ; les instructions suivantes ajoutent succesivement des arcs au graphe, chaque arc étant spécifié par les indices de ses sommets initial et final.

Deux autres types abstraits seront nécessaires, Sommet et Arc. Il arrive fréquemment que les sommets ou les arcs soient étiquetés, par exemple, par une couleur, ou par un nombre qui indique une distance ou un coût. Par suite, les sommets et les arcs devront comporter un champ information de type Object ; si ce champ est privé, les interfaces Arc et Sommet doivent exporter des méthodes d'accès valInformation() (sur les patterns d'accès, voir § 3.4). Comme les sommets peuvent être désignés par un numéro (utilisé en paramètre de la méthode ajouteArc()), la méthode valIndice() permet d'accéder à cet indice. Le sommet initial et le sommet final d'un arc sont obtenus par les méthodes valSommetInitial() et valSommetFinal(). Enfin, les méthodes sommets(), arcs() et adjacents() retournent des itérateurs qui auront un rôle crucial dans les algorithmes sur les graphes.

public interface Graphe {
  void ajouteArc(int u, int v);
  Iterator sommets();
  Iterator arcs();
  void parcoursProfondeur();
  void parcoursLargeur();
}

public interface Arc {
  Sommet valSommetInitial();
  Sommet valSommetFinal();
  Object valInformation();
}

public interface Sommet
{
  int valIndice();
  Iterator adjacents();
  Object valInformation();
}