next up previous contents index
Next: Itération préfixe d'un graphe Up: Patterns Previous: Itérations sur les tables

   
Implémentation d'un itérateur

Les algorithmes sur les graphes ont souvent besoin d'énumérer les sommets adjacents à un sommet. Par exemple, un parcours en profondeur utilise l'idiome suivant, où origine est de type Sommet :

    Iterator i = origine.adjacents();
    while (i.hasNext()) { 
      Sommet suivant = (Sommet) i.next();
      ...
    }

La méthode adjacents(), qui retourne un itérateur, est déclarée dans l'interface Sommet :

public interface Sommet
{
  int getIndice();
  Iterator adjacents();
}

Cette méthode ne peut être implémentée que dans le contexte d'une implémentation concrète des graphes. Par exemple, si les graphes sont implémentées comme des matrices d'arcs, par la classe GrapheParMatrice, la classe interne privée _Sommet qui implémente l'interface Sommet définit un itérateur à l'aide d'une implémentation anonyme d'Iterator. C'est la méthode hasNext() qui fait l'essentiel du travail, pour chercher l'élément suivant non nul dans la ligne de la matrice correspondant au sommet considéré. Les variables booléennes trouvé et terminé évitent à la méthode next() de refaire cette recherche ; cependant comme un utilisateur de l'itérateur n'est pas contraint à invoquer hasNext() juste avant next(), il faut éventuellement que next() invoque hasNext() pour faire cette recherche. L'implémentation de la méthode remove() (qui est optionnelle) se réduit ici au déclenchement de l'exception UnsupportedOperationException.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class GrapheParMatrice extends GrapheAbstrait {
  private Arc[][] matrice;
  
  private class _Sommet implements Sommet {
    protected int indice;
    protected Object info;
    
    _Sommet(int indice, Object info) {
      this.indice = indice;
      this.info = info;
    }
    
    public Iterator adjacents() {
      return new Iterator() {
        private int j=0;
        private boolean trouvé, terminé;

        public boolean hasNext() {
          while (j<nbSommets && matrice[indice][j] == null) j++;
          if (j < nbSommets) {
            trouvé = true;
            return true;
          } else {
            trouvé = false;
            terminé = true;
            return false;
          }
        }

        public Object next() {
          if (terminé) throw new NoSuchElementException();
          if (trouvé || hasNext()) {
            Object suivant = sommets[j];
            j++;
            return suivant;
          } else throw new NoSuchElementException();
        }

        public void remove() {
          throw new UnsupportedOperationException();
        }
      };
    }
  }
}



 
next up previous contents index
Next: Itération préfixe d'un graphe Up: Patterns Previous: Itérations sur les tables
R. Lalement
2000-10-23