Class MatrixGraph

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

All Implemented Interfaces:

Graph

class MatrixGraph

extends AbstractGraph

Implémentation des graphes par matrice d'adjacence. Dans cette implémentation, le nombre de sommets est fixé à la création du graphe. Il n'est pas possible d'ajouter de nouveaux sommets.

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	MatrixGraph.NextVertices Itérateur sur les les sommets adjacents au sommet donné
private class	MatrixGraph.Vertices Itérateur sur les sommets

Field Summary

private boolean[][]	matrix Matrice d'adjacence
private MatrixVertex[]	verticesArray Tableaux des sommets
protected int	verticesNumber Nombre de sommets du graphe

Constructor Summary

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

MatrixGraph(int size)
Création d'un graphe sans arêtes d'un nombre de sommets donnés

Method Summary

java.util.Iterator	breathFirstIterator(int i) Retourne un itérateur pour un parcours en largeur du graphe
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(int i) Retourne un itérateur pour un parcours en profondeur du graphe
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(int s, int b) Retourne s'il y a une arête entre deux sommets
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(int s, int b) Ajoute une arête entre les deux sommets donnés
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

verticesArray

private MatrixVertex[] verticesArray

Tableaux des sommets

matrix

private boolean[][] matrix

Matrice d'adjacence

verticesNumber

protected int verticesNumber

Nombre de sommets du graphe

Constructor Detail

MatrixGraph

public MatrixGraph(int size)

Création d'un graphe sans arêtes d'un nombre de sommets donnés

MatrixGraph

public MatrixGraph(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

putEdge

public void putEdge(int s,
                    int 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

getEdge

public boolean getEdge(int s,
                       int 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é

breathFirstIterator

public java.util.Iterator breathFirstIterator(int i)

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

depthFirstIterator

public java.util.Iterator depthFirstIterator(int i)

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

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