Class ListGraph

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

All Implemented Interfaces:

Graph

class ListGraph

extends AbstractGraph

Implémentation des graphes par listes d'adjacence

Nested Class Summary

(package private) class	AbstractGraph.BreadthFirstIterator Itérateur pour un parcours en largeur du graphe
(package private) class	AbstractGraph.DepthFirstIterator Itérateur pour un parcours en largeur du graphe

Field Summary

private java.util.List	verticesList Liste des sommets
protected int	verticesNumber Nombre de sommets du graphe

Constructor Summary

ListGraph()
Création d'un graphe vide

ListGraph(Graph g)
Création d'un graphe identique à un graphe donné

Method Summary

java.util.Iterator	breathFirstIterator(Vertex v) Retourne un itérateur pour un parcours en largeur du graphe
boolean	cyclic() Test si le graphe a un cycle par un parcours en profondeur
java.util.Iterator	depthFirstIterator(Vertex v) Retourne un itérateur pour un parcours en profondeur du graphe
java.lang.Object	get(Vertex v) Retoune la valeur un sommet
boolean	getEdge(Vertex s, Vertex b) Retourne s'il y a une arête entre deux sommets
java.util.Iterator	nextVertices(Vertex v) Retourne un itérateur sur les sommets adjacents au sommet donné
Vertex	put(java.lang.Object value) Ajoute un nouveau sommet avec une valeur donnée
void	putEdge(Vertex s, Vertex b) Ajoute une arête entre les deux sommets donnés
Vertex[]	stronglyConnectedComponents() Calcul des composantes fortement connexes
Vertex[]	topologicalSort() Tri topologique
java.lang.String	toString() Conversion en chaîne
void	transpose() Transposition du graphe (retournement des arêtes)
java.util.Iterator	vertices() Retourne un itérateur sur les sommets
int	verticesNumber() Retourne le nombre de sommets

Methods inherited from class java.lang.Object

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

Field Detail

verticesList

private java.util.List verticesList

Liste des sommets

verticesNumber

protected int verticesNumber

Nombre de sommets du graphe

Constructor Detail

ListGraph

public ListGraph()

Création d'un graphe vide

ListGraph

public ListGraph(Graph g)

Création d'un graphe identique à un graphe donné

Method Detail

vertices

public java.util.Iterator vertices()

Retourne un itérateur sur les sommets

put

public Vertex put(java.lang.Object value)

Ajoute un nouveau sommet avec une valeur donnée

putEdge

public void putEdge(Vertex s,
                    Vertex b)

Ajoute une arête entre les deux sommets donnés

getEdge

public boolean getEdge(Vertex s,
                       Vertex b)

Retourne s'il y a une arête entre deux sommets

nextVertices

public java.util.Iterator nextVertices(Vertex v)

Retourne un itérateur sur les sommets adjacents au sommet donné

transpose

public void transpose()

Transposition du graphe (retournement des arêtes)

verticesNumber

public int verticesNumber()

Retourne le nombre de sommets

Specified by:

verticesNumber in interface Graph

get

public java.lang.Object get(Vertex v)

Retoune la valeur un sommet

Specified by:

get in interface Graph

toString

public java.lang.String toString()

Conversion en chaîne

Overrides:

toString in class java.lang.Object

breathFirstIterator

public java.util.Iterator breathFirstIterator(Vertex v)

Retourne un itérateur pour un parcours en largeur du graphe

Specified by:

breathFirstIterator in interface Graph

depthFirstIterator

public java.util.Iterator depthFirstIterator(Vertex v)

Retourne un itérateur pour un parcours en profondeur du graphe

Specified by:

depthFirstIterator in interface Graph

cyclic

public boolean cyclic()

Test si le graphe a un cycle par un parcours en profondeur

Specified by:

cyclic in interface Graph

topologicalSort

public Vertex[] topologicalSort()

Tri topologique

Specified by:

topologicalSort in interface Graph

stronglyConnectedComponents

public Vertex[] stronglyConnectedComponents()

Calcul des composantes fortement connexes

Specified by:

stronglyConnectedComponents in interface Graph