Class AbstractGraph.DepthFirstSearch

java.lang.Object
  |
  +--AbstractGraph.DepthFirstSearch

Enclosing class:

AbstractGraph

private class AbstractGraph.DepthFirstSearch

extends java.lang.Object

Parcours en profondeur. Ce parcours en profondeur permet de tester si un graphe est acyclique et auquel cas de calculer un tri topologique des sommets.

Field Summary

(package private) byte	black
(package private) byte[]	color
(package private) byte	grey
(package private) java.util.LinkedList	list
(package private) byte	white

Constructor Summary

(package private)

AbstractGraph.DepthFirstSearch() Constructeur

Method Summary

(package private) Vertex[]	topologicalSort() Tri topologique des sommets.
private boolean	topologicalSortVisit(Vertex u) Appel récusif pour le tri topologique.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

color

byte[] color

white

final byte white

See Also:

Constant Field Values

grey

final byte grey

See Also:

Constant Field Values

black

final byte black

See Also:

Constant Field Values

list

java.util.LinkedList list

Constructor Detail

AbstractGraph.DepthFirstSearch

AbstractGraph.DepthFirstSearch()

Constructeur

Method Detail

topologicalSortVisit

private boolean topologicalSortVisit(Vertex u)

Appel récusif pour le tri topologique. Cette méthode ajoute les sommets à la liste au fur et à mesure que leur traitement se termine. Cette méthode retourne en outre si le graphe possède un cycle.

topologicalSort

Vertex[] topologicalSort()

Tri topologique des sommets. Si le graphe est acyclique, cette fonction retourne un tableau contenant les sommets triés dans un ordre topologique. Si le graphe possède un cycle, cette fonction retourne la référence null.