| Faculté des Sciences de Luminy |
Programmation Orientée Objets, langage Java
|
|
Henri Garreta
|
Fichier Sommet.java :
public class Sommet {
private int numero;
private long marque;
public Sommet(int numero) {
this.numero = numero;
}
public int numero() {
return numero;
}
public long marque() {
return marque;
}
public void marquer(long marque) {
this.marque = marque;
}
public boolean equals(Object obj) {
return numero == ((Sommet) obj).numero;
}
public String toString() {
return "<" + numero + ">";
}
}
Fichier Arete.java :
public class Arete {
private Sommet[] extremites;
private long marque;
public Arete(Sommet a, Sommet b) {
extremites = new Sommet[] { a, b };
}
public Sommet[] extremites() {
return extremites;
}
public Sommet autreExtremite(Sommet s) {
return extremites[s.equals(extremites[0]) ? 1 : 0];
}
public long marque() {
return marque;
}
public void marquer(long marque) {
this.marque = marque;
}
public String toString() {
return "(" + extremites[0] + "," + extremites[1] + ")";
}
}
Fichier Graphe.java :
import java.util.Iterator;
import java.io.PrintStream;
public interface Graphe {
void initialiser(int maxSommets);
int nombreSommets();
Iterator sommets();
int nombreAretes();
Iterator aretes();
Sommet sommet(int numero);
Arete arete(Sommet a, Sommet b);
Sommet insererSommet(int numero);
Arete insererArete(Sommet a, Sommet b);
void supprimerSommet(Sommet sommet);
void supprimerArete(Arete arete);
Iterator sommetsVoisins(Sommet s);
void insererArete(int i, int j);
void marquerTousLesSommets(int marque);
void parcoursEnLargeur(Sommet depart, Action action);
void parcoursEnProfondeur(Sommet depart, Action action);
void affichage(PrintStream sortie);
void lecture(String nomFichier) throws Exception;
}
Fichier Action.java :
public interface Action {
void action(Sommet s);
}
Fichier GrapheAbstrait.java :
import java.util.*;
import java.io.*;
public abstract class GrapheAbstrait implements Graphe {
public static final int BLANC = 1;
public static final int GRIS = 2;
public static final int NOIR = 3;
public void insererArete(int i, int j) {
Sommet a = sommet(i);
if (a == null)
a = insererSommet(i);
Sommet b = sommet(j);
if (b == null)
b = insererSommet(i);
if (arete(a, b) == null)
insererArete(a, b);
}
public void marquerTousLesSommets(int marque) {
Iterator it = sommets();
while (it.hasNext())
((Sommet) it.next()).marquer(marque);
}
public void parcoursEnLargeur(Sommet depart, Action action) {
marquerTousLesSommets(BLANC);
LinkedList file = new LinkedList();
depart.marquer(GRIS);
file.addLast(depart);
while (file.size() > 0) {
Sommet u = (Sommet) file.removeFirst();
action.action(u);
Iterator i = sommetsVoisins(u);
while (i.hasNext()) {
Sommet v = (Sommet) i.next();
if (v.marque() == BLANC) {
v.marquer(GRIS);
file.addLast(v);
}
}
u.marquer(NOIR);
}
}
public void parcoursEnProfondeur(Sommet depart, Action action) {
marquerTousLesSommets(BLANC);
parcoursRec(depart, action);
}
private void parcoursRec(Sommet u, Action action) {
action.action(u);
u.marquer(GRIS);
Iterator i = sommetsVoisins(u);
while (i.hasNext()) {
Sommet v = (Sommet) i.next();
if (v.marque() == BLANC)
parcoursRec(v, action);
}
u.marquer(NOIR);
}
public void affichage(PrintStream sortie) {
Iterator it = sommets();
while (it.hasNext()) {
Sommet s = (Sommet) it.next();
sortie.print(s + " -> ");
Iterator e = sommetsVoisins(s);
while (e.hasNext())
sortie.print((Sommet) e.next() + " ");
sortie.println();
}
}
public void lecture(String nomFichier) throws Exception {
InputStream entree = new FileInputStream(nomFichier);
Reader lecteur = new InputStreamReader(entree);
LineNumberReader lignes = new LineNumberReader(lecteur);
lignes.setLineNumber(1);
StreamTokenizer st = new StreamTokenizer(lignes);
st.nextToken();
if (st.ttype == st.TT_WORD
&& st.sval.toUpperCase().equals("MAX")) {
st.nextToken();
if (st.ttype != st.TT_NUMBER)
throw new Exception("lecture (ligne "
+ lignes.getLineNumber() + ") nombre attendu");
int max = (int) Math.round(st.nval);
initialiser(max);
st.nextToken();
if (st.ttype == st.TT_WORD
&& st.sval.toUpperCase().equals("SOMMETS")) {
st.nextToken();
while (st.ttype == st.TT_NUMBER) {
int i = (int) Math.round(st.nval);
insererSommet(i);
st.nextToken();
}
}
else
for (int i = 0; i < max; i++)
insererSommet(i);
}
else {
if ( ! (st.ttype == st.TT_WORD
&& st.sval.toUpperCase().equals("SOMMETS")))
throw new Exception("lecture (ligne "
+ lignes.getLineNumber() + ") 'aretes' attendu");
st.nextToken();
while (st.ttype == st.TT_NUMBER) {
int i = (int) Math.round(st.nval);
insererSommet(i);
st.nextToken();
}
}
if ( ! (st.ttype == st.TT_WORD
&& st.sval.toUpperCase().equals("ARETES")))
throw new Exception("lecture (ligne "
+ lignes.getLineNumber() + ") 'aretes' attendu");
st.nextToken();
while (st.ttype == st.TT_NUMBER) {
int i = (int) Math.round(st.nval);
st.nextToken();
if (st.ttype != st.TT_NUMBER)
throw new Exception("lecture (ligne "
+ lignes.getLineNumber() + ") nombre attendu");
int j = (int) Math.round(st.nval);
st.nextToken();
insererArete(i, j);
}
if ( ! (st.ttype == st.TT_WORD
&& st.sval.toUpperCase().equals("FIN")))
throw new Exception("lecture (ligne "
+ lignes.getLineNumber() + ") 'fin' attendu");
entree.close();
}
}
Fichier GrapheMI.java :
import java.util.Iterator;
public class GrapheMI extends GrapheAbstrait {
private int maxSommets;
private int nombreSommets;
private int nombreAretes;
private Sommet[] sommets;
private Arete[][] matrice;
public void initialiser(int maxSommets) {
this.maxSommets = maxSommets;
nombreSommets = 0;
nombreAretes = 0;
sommets = new Sommet[maxSommets];
matrice = new Arete[maxSommets][maxSommets];
}
public int nombreSommets() {
return nombreSommets;
}
public Iterator sommets() {
return new IterSommets();
}
public int nombreAretes() {
return nombreAretes;
}
public Iterator aretes() {
return new IterAretes();
}
public Sommet sommet(int numero) {
return sommets[numero];
}
public Arete arete(Sommet a, Sommet b) {
return matrice[a.numero()][b.numero()];
}
public Sommet insererSommet(int numero) {
Sommet s = new Sommet(numero);
sommets[numero] = s;
nombreSommets++;
return s;
}
public Arete insererArete(Sommet p, Sommet q) {
Arete a = new Arete(p, q);
matrice[p.numero()][q.numero()]
= matrice[q.numero()][p.numero()] = a;
nombreAretes++;
return a;
}
public void supprimerSommet(Sommet s){
Arete[] ligne = matrice[s.numero()];
for (int i = 0; i < maxSommets; i++) {
Arete a = ligne[i];
if (a != null)
supprimerArete(a);
}
sommets[s.numero()] = null;
nombreSommets--;
}
public void supprimerArete(Arete a) {
Sommet p = a.extremites()[0];
Sommet q = a.extremites()[1];
matrice[p.numero()][q.numero()]
= matrice[q.numero()][p.numero()] = null;
nombreAretes--;
}
public Iterator sommetsVoisins(Sommet s) {
return new IterVoisins(s);
}
// Itérateur parcourant les sommets du graphe
private class IterSommets implements Iterator {
private int pos;
public IterSommets() {
pos = 0;
while (pos < maxSommets && sommets[pos] == null)
pos++;
}
public boolean hasNext() {
return pos < maxSommets;
}
public Object next() {
Sommet res = sommets[pos++];
while (pos < maxSommets && sommets[pos] == null)
pos++;
return res;
}
public void remove() {
}
}
// Itérateur parcourant voisins d'un sommet
private class IterVoisins implements Iterator {
Sommet sommet;
private Arete[] ligne;
private int pos;
public IterVoisins(Sommet sommet) {
this.sommet = sommet;
ligne = matrice[sommet.numero()];
pos = 0;
while (pos < maxSommets && ligne[pos] == null)
pos++;
}
public boolean hasNext() {
return pos < maxSommets;
}
public Object next() {
if (pos < maxSommets) {
Sommet res = ligne[pos++].autreExtremite(sommet);
while (pos < maxSommets && ligne[pos] == null)
pos++;
return res;
}
else
return null;
}
public void remove() {
}
}
// Itérateur parcourant les arêtes du graphe
private class IterAretes implements Iterator {
private int plin, pcol;
public IterAretes() {
plin = pcol = 0;
avancer();
}
public boolean hasNext() {
return plin < maxSommets && pcol < maxSommets;
}
public Object next() {
if (plin < maxSommets && pcol < maxSommets) {
Arete res = matrice[plin][pcol];
avancer();
return res;
}
else
return null;
}
private void avancer() {
do {
pcol++;
if (pcol >= maxSommets) {
plin++;
pcol = plin + 1;
}
}
while(plin < maxSommets - 1
&& (pcol >= maxSommets || matrice[plin][pcol] == null));
}
public void remove() {
}
}}
Fichier TestGraphe.java :
public class TestGraphe {
public static void main(String[] args) {
Graphe g;
Action traverser = new Action() {
public void action(Sommet s) {
System.out.println("=> " + s);
}
};
// Création
g = new GrapheMI();
// Lecture
try {
g.lecture("donnees.graphe");
}
catch (Exception e) {
System.out.println("Probleme : " + e);
}
// Affichage
System.out.println("Graphe lu");
g.affichage(System.out);
// Parcours des arêtes
System.out.println("Parcours des arêtes");
Iterator it = g.aretes();
while (it.hasNext())
System.out.println(it.next());
// Parcours en largeur
System.out.println("Parcours en largeur");
g.parcoursEnLargeur(g.sommet(3), traverser);
// Parcours en profondeur
System.out.println("Parcours en profondeur");
g.parcoursEnProfondeur(g.sommet(3), traverser);
// Affichage et suppression d'arête
Arete a = g.arete(g.sommet(1), g.sommet(3));
System.out.println("Suppression de l'arête " + a);
g.supprimerArete(a);
g.affichage(System.out);
// Suppression de sommet
Sommet s = g.sommet(1);
System.out.println("Suppression du sommet " + s);
g.supprimerSommet(s);
g.affichage(System.out);
System.out.println("*** Terminé ***");
}
}
Fichier donnees.graphe :
MAX 10 SOMMETS 0 1 2 3 4 ARETES 0 1 0 2 1 2 1 4 2 3 1 3 3 4 FIN
Affichage produit par l'exécution de la classe TestGraphe :
Graphe lu <0> -> <1> <2> <1> -> <0> <2> <3> <4> <2> -> <0> <1> <3> <3> -> <1> <2> <4> <4> -> <1> <3> Parcours en largeur => <3> => <1> => <2> => <4> => <0> Parcours en profondeur => <3> => <1> => <0> => <2> => <4> Suppression de l'arête (<1>,<3>) <0> -> <1> <2> <1> -> <0> <2> <4> <2> -> <0> <1> <3> <3> -> <2> <4> <4> -> <1> <3> Suppression du sommet <1> <0> -> <2> <2> -> <0> <3> <3> -> <2> <4> <4> -> <3> *** Terminé ***
Fichier xxx.java :
A venir...
Fichier xxx.java :
A venir...