Cette implémentation permet de manipuler des graphes orientés sans arêtes multiples (il y a au plus une arête entre deux sommets). Deux représentation des graphes sont possibles : par matrice d'adjacence et par listes d' adjacence. Plusieurs algorithmes classiques comme les parcours en largeur et en profondeur sont programmés.
Dans cette implémentation, une valeur est associée à chaque sommet du graphe. Un graphe est vu comme une structure de donnée au même titre que les piles, les piles et les tas. Les arêtes du graphe modélisent une relation entre ces données. Les parcours d'un graphe sont alors différentes façons de parcourir les données en tenant compte des relations entre ces données. Pour cette raison, les parcours sont fournis sous forme d'itérateurs.
Dans cette représentation, le graphe est représenté par une matrice booléenne indexée en ligne et en colonne par les sommets du graphe. Pour deux sommets u et v, l'entrée (u,v) de la matrice détermine si l'arête (u,v) de u à v est présente dans le graphe. Cette représentation du graphe a l'inconvénient de nécessiter un espace mémoire proportionnel à |S|2 quelque soit le nombre d'arêtes du graphe. Cet inconvénient disparaît lorsque le graphe est dense, c'est-à-dire lorsque le nombre d'arêtes est de l'ordre de grandeur de |S|2. Dans ce cas, le graphe est représenté de manière compacte puisque l'espace occupé par chaque arête est faible.
Dans l'implémentation de cette représentation, le nombre de sommets du graphe doit être donné à la construction et aucun autre sommet ne peut être ajouté ensuite.
Dans cette représentation, chaque sommet contient une liste des sommets qui lui sont adjacents. L'intérêt de cette représentation est que l'espace occupé par le graphe est proportionnel au nombre d'arètes du graphe. Par contre, l'espace occupé par chaque arête est relativement élevé.
L'implémentation de cette représentation autorise l'ajout de nouveaux sommets à un graphe. Par contre la suppression d'un sommet n'est pas possible.
Les différents algorithmes qui sont programmés et en particulier les parcours de graphes le sont à partir de deux opérations de bases sur le graphe. La première opération est le fait de pouvoir parcourir les sommets du graphes. La seconde opération est le fait de parcourir les sommets adjacents à un sommet donné. Ces deux opérations sont fournies par le graphe sous forme d'itérateurs.
Les algorithmes sur graphes sont programmés de manière générique en utilisant les itérateurs.
Les deux parcours de graphes principaux, c'est-à-dire le parcours en largeur et le parcours en profondeur sont programmés. Ces deux parcours sont également implémentés sous forme d'itérateurs. Les appels successifs à la méthode next() de ces objets retournent les valeurs des sommets dans l'ordre déterminé par le parcours. Les méthodes retournant ces itérateurs pour les parcours sont les méthodes breathFirstIterator et depthFirstIterator. La méthode breathFirstIterator prend en paramètre le sommet à partir duquel doit s'effectuer le parcours en largeur alors que la méthode depthFirstIterator ne prend pas de paramètre. Les itérateurs retournés par ces méthodes sont implémentés par des classes internes BreadthFirstIterator et DepthFirstIterator de la classe AbstractGraph.
La recherche d'un cycle dans un graphe et le tri topologique d'un graphe acyclique sont programmés. La méthode cyclic retourne un booléen qui indique si le graphe contient un cycle. La méthode topologicalSort retourne un tableau qui contient les sommets du graphe dans un ordre topologique lorsque le graphe est acyclique. Ces algorithmes sont implémentés par un parcours en profondeur du graphe. Ce parcours est effectué par des méthodes de la classe DepthFirstSearch qui est une classe interne de la classe AbstractGraph.
Le calcul des composantes fortement connexes est programmé. La méthode stronglyConnectedComponents retourne un tableau qui donne les représentant de la classe de chaque sommet du graphe. L'algorithme utilisé est l'algorithme de Tarjan qui effectue un parcours en profondeur du graphe puis un parcours en profondeur du graphe transposé. Ces deux parcours sont effectués par des méthodes de la classe StronglyConnectedComponents qui est une classe interne de la classe AbstractGraph.
L'organisation en classes est la suivante :
La documentation Javadoc.