Class AbstractGraph.StronglyConnectedComponents

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

Enclosing class:

AbstractGraph

private class AbstractGraph.StronglyConnectedComponents

extends java.lang.Object

Field Summary

(package private) byte	black
(package private) byte[]	color
(package private) Vertex[]	components
(package private) byte	grey
(package private) java.util.List[]	prev
(package private) java.util.LinkedList	revlist
(package private) byte	white

Constructor Summary

(package private)

AbstractGraph.StronglyConnectedComponents() Constructeur

Method Summary

(package private) Vertex[]	components() Calcul des composantes fortement connexes.
private void	firstVisit(Vertex u) Premier parcours en profondeur
private void	secondVisit(Vertex u, Vertex w) Second parcours en profondeur

Methods inherited from class java.lang.Object

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

Field Detail

prev

java.util.List[] prev

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

revlist

java.util.LinkedList revlist

components

Vertex[] components

Constructor Detail

AbstractGraph.StronglyConnectedComponents

AbstractGraph.StronglyConnectedComponents()

Constructeur

Method Detail

firstVisit

private void firstVisit(Vertex u)

Premier parcours en profondeur

secondVisit

private void secondVisit(Vertex u,
                         Vertex w)

Second parcours en profondeur

components

Vertex[] components()

Calcul des composantes fortement connexes. Cette méthode retourne un tableau t de sommets. Pour chaque sommet u, t[u.index()] contient la référence du sommet qui représente la composante fortement contient de u. Deux sommets sont donc dans la même composante ssi t[u.index()] == t[v.index()].