Class AbstractGraph

java.lang.Object
  |
  +--AbstractGraph

All Implemented Interfaces:

Graph

Direct Known Subclasses:

ListGraph, MatrixGraph

abstract class AbstractGraph

extends java.lang.Object

implements Graph

Implémentation générique des graphes Cette classe abstraite gère le nombre des sommets. Elle implémente aussi les parcours de graphes puisque ceux-ci ne dépendent pas de l'implémentation du graphe.

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
private class	AbstractGraph.DepthFirstSearch Parcours en profondeur.
private class	AbstractGraph.StronglyConnectedComponents

Field Summary

protected int

verticesNumber Nombre de sommets du graphe

Constructor Summary

protected

AbstractGraph() Création d'un graphe vide

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

verticesNumber

protected int verticesNumber

Nombre de sommets du graphe

Constructor Detail

AbstractGraph

protected AbstractGraph()

Création d'un graphe vide

Method Detail

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

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)