ISN 1A TP 1 29/05/2019

Algorithmique et structure de données

TP : Itinéraire de bus avec Dijkstra

Deniaux Simon – Pecastaing Hugo

 Sommaire
I - Analyse du problème
I.a) Description du problème……………………………………………………………..3
I.b) Solutions proposées…………………………………………………………………..3
I.c) Choix d’une solution…………………………………………………………………..3

II - Le programme
II.a) Classes préalables…………………………………………………………………….3
II.b) Création du graphe……………………………………………………………………4
II.c) Recherche du chemin le plus court………………………………………………4
II.d) La Méthode principale………………………………………………………………..5
II.e) L’interface graphique………………………………………………………………….5

III - Jeu de tests……………………………………………………………………………6

IV - Mode d’emploi………………………………………………………………………..7
V - Bilan
V.a) Problèmes rencontrés………………………………………………………………..7
V.b) Solutions trouvées……………………………………………………………………7
V.c) Limite du programme…………………………………………………………………7
V.d) Améliorations envisageable………………………………………………………….7

IV - Annexes
I - Analyse du problème
I. a) Description du problème
Ce TP a pour objectif de réaliser un programme informatique permettant le calcul d’un
itinéraire sur un réseau de bus. Nous nous pencherons sur la recherche d’un chemin idéal dans un
graphe. Ce genre de mise en pratique peut porter sur le routage optimal des paquets sur le réseau
internet ou encore sur des applications permettant de trouver un itinéraire optimal partant d’un
point de départ A pour aller à un point d’arrivée B (exemple : GPS, réseau de transport, …). Pour ce
travail, le graphe représente un réseau de trois lignes de bus (A,B,C). Il y a tout d’abord les sommets
représentant les stations, puis les arêtes indiquant les routes. Chaque arête est doté d’un nombre
permettant de donner le temps de parcours entre les deux stations adjacentes. Ce TP a donc pour
objectif, d’écrire un programme en JAVA qui réalisera un itinéraire optimal partant d’une station de
départ donnée et allant à une station d’arrivée donnée. Enfin, il faut également gérer les flux
d’entrées/sorties en JAVA. Nous avons à dispositions deux fichiers textes représentant
respectivement les arrêts et lignes de bus correspondantes ainsi que les coordonnées des différents
arrêts. La première partie de notre travail consiste à implémenter ces informations pour construire
le graphe correspondant. Ensuite, nous devons créer le système de recherche de chemin optimal.
Finalement, une interface graphique doit être conçu avec l’affichage du chemin précédemment
trouvé.

I.b) - Solutions proposées

En cours, nous avons vu plusieurs méthodes :
(1) la solution de force brute qui à pour but d’avoir une approche direct sur des problèmes
simple or ici nous somme plutôt sur un algorithme complexe.
(2) l’algorithme de Dijkstra qui recherche le plus court chemin dans un graphe

I.c) - Choix d’une solution

Le choix de la solution est automatique. On va utiliser la méthode de Dijkstra. De plus,
comme vu précédemment, la solution de force brute ne serait pas adéquate pour ce type de
problème car elle répond à des problèmes beaucoup plus simple

II - Le programme
II. a) - Classes préalables
Nous avons 3 classes préalables fournies qui sont nécessaires au bon fonctionnement de
l’algorithme et ainsi procéder à la recherche d’un chemin optimal dans un graphe. Tout d’abord Liste
et Element ont dû être modifié car le chemin choisi n’est pas explicité par l’algorithme actuel. Nous
rajoutons une variable int predecesseur dans la classe Element. Ainsi cela permettra de partir du
sommet d’arrivée pour remonter au sommet de départ et donc pouvoir afficher le chemin
parcouru. De plus, la classe Arret comportant des attributs String nom, int coord X et int coord Y a été
crée pour mettre à jours les stations et les situés géographiquement. Cette dernière comporte aussi
une méthode distance2arets(Arret A) qui permet de renvoyer la distance entre l’arrêt sélectionné et
l’arrêt A.
II. b) Création du graphe
Méthodes préalables : Il faut d’abord récupérer les fichiers texte mis à disposition à l’aide la
classe Fichier. Nous avons juste besoin des méthodes listeArrets( ) et listeNomArrets( ) qui vont nous
permettent de lire dans le fichier kelkonk_bus.geo. La première méthode renvoie un vecteur
vecArets contenant les différents objets Arret dont la classe a été défini dans le fichier [Link].
Cette fonction lit les différentes lignes du fichier texte et y récupère les arrêts et leurs coordonnées
(x, y) à l’aide de la méthode split. La seconde méthode renvoie simplement une liste listeNomArrets
contenant les noms des différents arrêts de façon à associer chaque arrêt avec son numéro
correspondant. En effet, les fonctions liées au graphe fonctionnent avec des entiers et non des
chaînes de charactères.

Classe GrapheParListe : Cette classe est composé d’une variable d’instance adj de type Liste
qui correspond au à la liste adjacente du graphe. Dans celle-ci un argument fichier est pris par le
constructeur ainsi que le vecteur ListeArrets et la listeNomArrets. Dans ce constructeur, les lignes
sont lu deux à deux en récupérant les arrêts et la ligne de bus correspondant. De plus à l’aide de la
méthode distance2Arets on calcul la distance entre 2 arrêtes puis on calcul le temps de trajet à l’aide
le méthode tempsTrajet2Arets. Enfin nous mettons à jour la méthode Liste puis nous observons que
nous avons des temps de parcours et non des distances ce qui est conforme à l’optimalité demandé.

II. c) Recherche du plus court chemin

Méthodes préalables : Pour le calcul du temps du plus court chemin nous devons considérer
le changement de ligne et n’est pas possible de considérer ces temps en amont du calcul il nous
donc créer des temps supplémentaires. Nous créons donc une méthode changementLigne dans la
classe GrapheParListe avec 3 arguments en entrée sommet1, sommet2 et sommet3 . Celle-ci
retourne un booléen égal à true si si il y a un changement de ligne entre le chemin sommet1-
sommet2 et le chemin sommet2-sommet3. Algorithme de Dijkstra : La méthode plusCourtChemin
dans la méthode GrapheParListe correspond à cet algorithme. On prend num_sommet en entrée
correspondant au numéro du sommet et on renvoie un vecteur solution S. Nous devons aussi
ajouter les 300 secondes correspondant au changement de ligne. Pour cela, on regarde si le chemin
[Link] - [Link] est sur la même ligne que le chemin [Link] - [Link]. Si c’est vrai,
nous ajoutons 60 secondes sinon 300 secondes.

Chemin optimal : Maintenant que nous avons la solution de l’algorithme et que les différents
sommets ont des attributs predecesseur nous pouvons remonter le chemin en partant du point
d’arrivé. On crée la méthode cheminOptimal qui prend en entrée un sommet source source et un de
destination dest puis la solution S. Dans cette méthode nous calculons tout d’abord le temps de
parcours jusqu’au sommet d’arrivée auquel nous ajoutons les 180 secondes d’attente du bus. Puis
nous enlevons les 60 secondes d’arrêt au dernier
sommet.

II. d) La méthode principale

Dans la méthode principale nous reprenons toute les méthodes vu précédemment pour
construire la recherche de l’itinéraire. Il faut afficher le trajet détaillé, le temps de parcours et le
nombre de correspondance. Pour cela nous avons 3 méthodes :
(1) afficherTrajet : Elle renvoie une chaîne de caractère de la forme A1->…->B3->…->C6 qui
 correspond au trajet.
(2)tempsTrajetMinute : Elle renvoie une chaîne de caractère avec le temps du trajet indiqué
en minutes.
(3)nombreCorrespondance : Elle permet de compter le nombre de correspondance en
parcourant la liste et en regardant s’il y a des changements de lignes.

II.e) L’interface graphique

L'interface graphique se décompose en trois classes :

(1) interfaceGraphiqueRecherche : celle-ci gère l'affichage de la fenêtre (fond gris) et des 2
menus déroulants, puis ajoute les autres composants à l'intérieure. Elle fait intervenir 2 autres
classes pour afficher le plan du réseau (partie centrale de l'interface) et une autre pour le reste des
inscriptions et des boutons.
(2) PlanGraphique : cette classe permet après avoir récupérer dans son constructeur la liste des
arrêts successifs à parcourir pour optimiser le trajets, trace le plan du réseau en blanc puis trace en
vert le trajet demandé par l'utilisateur.
(3) RecherchePanneau : cette classe permet de construire un panneau contenant les différents
textes (trajet, temps, ...).

III - Jeux de tests

Voici quelques exemples-tests de l'interface :
IV - Mode d’emploi
Votre rôle est de choisir votre gare de départ et votre gare d’arrivée. Pour cela il faut
procéder par étape :
Étape 1 : Lancez le programme fournit par le constructeur. Une fenêtre s’affiche avec le nom
de la compagnie « Transport Bus ».

Étape 2 : Utilisez les menus déroulants situés sous les titres Départ et Arrivée pour choisir
votre arrêt de départ et votre arrêt d’arrivé.
Étape 3 : Cliquez sur le bouton Recherche situé en bas de la fenêtre pour procéder à votre
recherche.
Étape 4 : Un écran s’affiche avec l’itinéraire conseillé pour arriver à votre destination le plus
rapidement possible. Vous voyez aussi apparaître en-dessous de la carte du réseau :
Trajet : affiche le trajet effectuer entre chaque gare (ex : A1—>B4—>B5)
Temps de trajet : affiche le temps du trajet optimal (ex : 2m34s)
Nombre de correspondance : affiche le nombre de correspondance (ex : 1)
Étape 5 : Vous pouvez effectuer une nouvelle recherche en repartant de l’étape 2. Sinon
vous pouvez fermer la fenêtre si vous avez fini.
V - Bilan
V.a) Problèmes rencontrés
Un des problèmes rencontré concerne l’algorithme du plus court chemin, la compréhension
de son fonctionnement et de son implémentation fut difficile. Cependant, nous avons réussit à faire
face à ce problème et donc programmer cet algorithme en essayant de procéder de la meilleure des
manières. Un second problème rencontré était sur le temps de correspondance entre chaque ligne
car ces temps ne peuvent pas être inclus directement sur le graphe.

V.b) Solutions trouvées

Pour résoudre ce second problème il suffit de connaître le chemin optimal. Cependant, pour
le connaître il faut également les temps de correspondance entre chaque ligne. Ainsi pour pouvoir
remédier à ce souci, nous avons crée des temps additionnels correspondant à ces changements de
ligne dans la méthode changementLigne. En effet, lors du déroulement de l’algorithme, il y a un
recalcule du trajet en prenant en compte ces changements par l’intermédiaire du sommet
précédent, actuel et suivant.

V.c) Limite du programme

La limite de notre programme concerne également les calculs de correspondance. En effet,
nous ajoutons les 300 secondes lorsque le sommet qui est observé par le programme est celui qui
précède le sommet contenant des correspondances. Or, notre algorithme a déjà procédé au calcul
du chemin optimal précédent avant de reconnaître des niveaux d’arêtes plus élevés ce qui remet en
doute le calcul du trajet idéal.

V.d) Améliorations
Pour être proche d’une solution parfaite, il faudrait savoir à chaque croisement entre ligne, si
il y a des correspondances de croisement sur la station suivante. Il suffirait donc d’implémenter un
code qui regarde si il y a des correspondances au prochain croisement.

VI – Annexes

VI.a) Classe « Arret »

public class Arret {

public String nom;

public int coordX;
public int coordY;

Arret(String nom, int coordX, int coordY) {

[Link] = nom;
[Link] = coordX;
[Link] = coordY;
}
 public double distance2Arets(Arret A) {
double a = [Link]([Link]([Link] - [Link] ,
2)+[Link]([Link]- [Link],2));
return a;
}

public String getNom() {

return nom;
}

public int getCoordX() {

return coordX;
}

public int getCoordY() {

return coordY;
}

VI.b) Classe « Element »

public class Element {
int sommet; //on code le numéro d'un sommet par un entier
int distance; //distance vers le sommet source
int predecesseur;

Element(int s, int d,int p){

sommet=s;
distance=d;
predecesseur=p;
}
}

VI.c) Classe « Liste»

public class Liste {

int num_noeud; //pour représenter le numéro d'un sommet

int valeur; //pour représenter la valeur de l'arc
String ligne;
Liste suivant;

Liste ( int n, Liste t, int v, String l) {

num_noeud=n;
suivant= t;
valeur=v;
ligne=l;
}
}

VI.d) Classe « Fichier»

import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];

public class Fichier {

private BufferedWriter fW;

private BufferedReader fR;
private char mode;

public Fichier(String nomDuFichier, String s) throws IOException{

mode = ([Link]()).charAt(0);
File f = new File(nomDuFichier);
if (mode == 'R' || mode == 'L')
fR = new BufferedReader(new FileReader(f));
else if (mode == 'W' || mode == 'E')
fW = new BufferedWriter(new FileWriter(f));
}

public void fermer() throws IOException {

if (mode == 'R' || mode == 'L') [Link]();
else if (mode == 'W' || mode == 'E') [Link]();
}

public String lire() throws IOException {

String chaine = [Link]();
return chaine;
}

public void ecrire(int tmp) throws IOException {

String chaine = "";
chaine = [Link](tmp);
if (chaine != null) {
[Link](chaine,0,[Link]());
[Link]();
}
}
}
VI.e) Classe « Methodes»
import [Link];
import [Link];
import [Link];
import [Link];

public class Methodes {

public static Vector<Arret> listeArrets() throws IOException{

Fichier graphe = new Fichier("kelkonk_bus.geo","R");
String l;
String s[];
Vector<Arret> vecArrets = new Vector<Arret>();
while((l = [Link]()) != null){
if(!([Link](0,1).equals("#"))) {
s = [Link]("\t");
[Link](new
Arret(s[0],[Link](s[1]),[Link](s[2])));
 }
}
return vecArrets;
}

public static ArrayList<String> listeNomArrets() throws IOException{

Fichier graphe = new Fichier("kelkonk_bus.geo","R");
String l;
String s[];
ArrayList<String> listeNomsArrets = new ArrayList<String>();
while((l = [Link]()) != null){
if(!([Link](0,1).equals("#"))) {
s = [Link]("\t");
[Link](s[0]); }
}
return listeNomsArrets;
}

public static int tempsTrajet2Arets(double distance , String ligneBus) {

int tempsTrajet = 0;
int vitesse = 10;
switch (ligneBus) {
case "A":
vitesse = 10;
break;
case "B":
vitesse = 10;
break;
case "C":
vitesse = 20;
break;
}
tempsTrajet = (int) (distance/ vitesse);
return tempsTrajet;
}

public static String afficherTrajet(ArrayList ListChemin , ArrayList<String>

listeNomArrets)
{
String trajet="";
for(int i=0; i < [Link]()-1; i++) {
trajet += [Link]((int) [Link](i)) + " -> ";
}
trajet += [Link]((int) [Link]([Link]()-1));
return trajet;
}

public static String tempsTrajetMinute(int tempsTrajet) {

String tempsMinutes = tempsTrajet/60+"min "+tempsTrajet % 60+"s";
return tempsMinutes;
}

VI.f) Classe « GrapheParListe»

import [Link];
import [Link].*;
import [Link].*;

public class GrapheParListe {

public Liste adj [];

GrapheParListe(Fichier graphe , ArrayList listeNomArrets , Vector ListeArets)

throws IOException {

String l="";
String []s;
String lprec ="";
String [] sprec;
String ligneBus;

int numAret , numAretPrec ,tempsTrajet;

double distance;

l = [Link]();

adj = new Liste[[Link]()];

for(int i = 0; i < [Link](); i++) {

adj[i] = null;
}

while(l != null)
{
lprec = l;
l = [Link]();
if(l != null && !([Link]("")) && !([Link](0,1).equals("#")))
{

s = [Link](":");

if(!([Link]("")) && !
([Link](0,1).equals("#"))) {

sprec = [Link](":");
numAret = [Link](s[1]); //Numero de
l’arret courant.
numAretPrec = [Link](sprec[1]); //
Numero de l’arret precedent.
ligneBus = s[0].substring(0, 1); //Ligne de bus entre
l’arret courant et l’arret precedent.
distance =
((Arret)[Link](numAretPrec)).distance2Arets((Arret)[Link](n
umAret));
//On calcule la distance entre les deux arrets.

tempsTrajet = Methodes.tempsTrajet2Arets(distance,
ligneBus);

//On calcule le temps de trajet entre les deux arrets

en fonction de la ligne de bus sur laquelle on est.
adj[numAretPrec] = new
Liste(numAret ,adj[numAretPrec],tempsTrajet, ligneBus);
}
}
}
 }

public void afficherGraphe(){

for(int i = 0; i < [Link]; i++) {
[Link]("sommet "+i+": ");
if(adj[i]!= null) {
Liste a = adj[i];
while(a!=null) {

[Link]("s"+a.num_noeud+ " " + [Link]+ " " +

[Link]);

if([Link]!= null) {
[Link]("|"+a. suivant.num_noeud+"
->");
}
a = [Link];
[Link](" null");
}
}
}
}

//tester s'il existe un arc entre deux sommets

public boolean arc (int source, int dest){
boolean arcExiste= false;
if( adj[source]!=null) {
Liste a = adj[source];
while(a !=null) {
if(a.num_noeud== dest) arcExiste =true;
if(arcExiste) a=null;
else
a = [Link];
}
}
return arcExiste;
}

//retruner la valeur de l'arc entre deux sommets

public int valeurArc(int source,int dest){
int val = 9999;
boolean arcExiste=false;
Liste a = adj[source];
while(a !=null) {
if(a.num_noeud== dest) {
val = [Link];
arcExiste =true;
}
if(arcExiste) a=null;
else a = [Link];
}
return val;
}

public Vector<Element> plusCourtChemin(int num_sommet){

final int INFINI = Integer.MAX_VALUE;
Vector<Element> S = new Vector<Element>(); //vector de solution
Vector<Element> D = new Vector<Element>(); //vector du départ
 //initialiser l'ensemble D
for(int i = 0; i <[Link]; i++){
if(i!=num_sommet)[Link](new Element(i,INFINI,num_sommet));
else
[Link](new Element(i,0,num_sommet));
}

//construire l'ensemble S selon Dijkstra

while([Link]()!=0){
//on cherchel'élément qui a la plus petite distance
int indice_min=0;
int dm=INFINI;
int sm=((Element) [Link](0)).sommet;
int prede = ((Element) [Link](0)).predecesseur;
for (int i = 0; i < [Link](); i++){

if(dm > ((Element) [Link](i)).distance){

dm = ((Element) [Link](i)).distance;
sm = ((Element) [Link](i)).sommet;
prede = ((Element) [Link](i)).predecesseur;
indice_min = i;

Element m = new Element(sm,dm,prede);

//on l'ajoute dans S puis on le supprime de D
[Link](m);

[Link](indice_min);

// if ([Link]((Element) m)==false)

//on recalcule dx pour tout sommet x de D qui possède un arc avec m

for(int i = 0; i < [Link](); i++){
Element x = (Element) [Link](i);
if(arc([Link],[Link])) {
int d=[Link]+valeurArc([Link] ,[Link]);
if (d < [Link]) {
[Link]=d;
[Link]=[Link];
[Link](x,i);
}
}
}
}
/*[Link]("\nVecteur Solution :");
for(int i = 0; i < [Link](); i++){
[Link]("\t"+((Element)[Link](i)).predecesseur+","+
((Element)[Link](i)).sommet+","+((Element)[Link](i)).distance);
}
*/
return S;
}

public Vector<Element> cheminOptimal(int source, int dest, Vector S/*, List

nomArets*/)
{
 Vector cheminEtTemp = new Vector();
int tempsTrajet =0;
List ListChemin = new ArrayList();

[Link](0,dest); //On ajoute la destination à la liste des arrets

du parcours.
// Calucul du temps de trajet :

for(int i=0; i<[Link](); i++) {

if(((Element)[Link](i)).sommet == dest) {

//On calcule le temps de trajet (en rajoutant les 180

secondes d’attente au depart et en substituant les 60 secondes à l’arrivee.
//(On considere que des que l’on arrive, le trajet est
termine)

tempsTrajet = ((Element)[Link](i)).distance+180-60;
}
}
//Calcul des arrets successifs: On remonte la liste S tant qu’ on est pas
à la source.

while(source != dest) {
for(int i=0; i<[Link](); i++) {
if(((Element)[Link](i)).sommet == dest) {
dest = ((Element)[Link](i)).predecesseur;
[Link](0,dest);
}

}
[Link](ListChemin);
[Link](tempsTrajet);
return cheminEtTemp;
}

public boolean changementLigne(int sommet1, int sommet2, int sommet3){

if (sommet1== 0 && sommet2 != 1) {

return false;
}
String ligne1="";
String ligne2="";
Liste a = adj[sommet1];
while(a!=null) {
if(a.num_noeud == sommet2)
ligne1 = [Link];
a = [Link];
}
a = adj[sommet2];
while(a!=null) {
if(a.num_noeud == sommet3)
ligne2 = [Link];
a = [Link];
}
return ();
}

public int nombreCorrespondance(ArrayList ListChemin) {

int compteur =0;
 int a=0, b=0, c=0;
if([Link]() <= 2) //Si le trajet est inferieur à 2 stations, on
sait qu’il n’y aura pas de changement de bus.
return 0;
else //Sinon, on verifie les arrets de la liste des sommets du trajet pour
verifier s’il y a des changements.
{
for(int i=0;i<[Link]()-2;i++) {

a=(int) [Link](i);
b=(int) [Link](i+1);
c=(int) [Link](i+2);
if(changementLigne(a,b,c))
compteur ++;
}
}
return compteur;
}
}

VI.g) Classe « RecherchePanneau»

import [Link];
import [Link];
import [Link];
import [Link];

import [Link];

public class RecherchePanneau extends JPanel {

private Graphics g;
private ArrayList arretSuc;
private String temps;
private int corresp;
private String trajet = "A1";
private ArrayList listeNomArrets;
private ArrayList stationSuccessive;

public RecherchePanneau(Graphics g, ArrayList stationSuccessive, ArrayList

listeNomArrets) {
this.g=g;
[Link]=stationSuccessive;
[Link]=listeNomArrets;

public void paintComponent(Graphics g) {

// Titre
[Link](new Font("Helvetica Neue", [Link], 35));
[Link]([Link]);
[Link]("Votre itinéraire", 50, 50);

//Fleche
[Link](new Color(10, 220, 100));
[Link](50, 60, 330, 5, 2, 2);

for(int i=30;i>0;i--) {
[Link](375, 63+(30-i), i, 1, 1, 1);
 [Link](375, 62-(30-i), i, 1, 1, 1);
}

//Affichage trajet + temps + nb correspondances

[Link]([Link]);
[Link](new Font("Helvetica Neue", [Link], 18));

[Link]("Départ", 100, 100);

[Link]("Arrivée", 600 , 100);

[Link]("Trajet : "+trajet, 100, 600);

[Link]("Temps de trajet : "+temps, 100 , 636);
[Link]("Nombre de correspondances : "+corresp, 100, 672);

public void setArretSuc(ArrayList arretSuc) {

[Link] = arretSuc;
}

public void setTemps(String temps) {

[Link] = temps;
}

public void setCorresp(int corresp) {

[Link] = corresp;
}

public void setTrajet(String trajet) {

[Link] = trajet;
}

VI.h) Classe « PlanGraphique »

import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];

import [Link];
import [Link];

public class PlanGraphique extends JPanel {

private Graphics g;
private ArrayList stationSuccesive;
private Liste a;
 public PlanGraphique(Graphics g, ArrayList stationSuccesive) {
this.g=g;
[Link]=stationSuccesive;
}

public void paintComponent(Graphics g) {

try {
int size = 30;
Vector Q = [Link]();
ArrayList listeNomArrets = [Link]();
Fichier graphe = new Fichier("kelkonk_bus.graph","R");
GrapheParListe graph = new GrapheParListe(graphe , listeNomArrets ,
Q);

int numArret1 , numArret2 , distance12;

for(int i = 0; i < [Link]; i++){

if([Link][i]!= null) {
numArret1 = i;
a = [Link][i];

while(a!=null)
{
numArret2 = a.num_noeud;
distance12 = [Link];
String lignebus = [Link];
int x1 =
((Arret)[Link](numArret1)).coordX ;
int y1 =
((Arret)[Link](numArret1)).coordY ;
int x2 =
((Arret)[Link](numArret2)).coordX ;
int y2 =
((Arret)[Link](numArret2)).coordY ;
//Si les arrets adjacents sont dans la liste des
sommets du trajet, on peint l’arrete en rouge

if([Link](numArret1) &&
[Link](numArret2))
[Link](new Color(10, 220, 100));
else //Sinon on la peint en noir.
[Link]([Link]);
[Link]((int)(x1/5)+45,(int) (y1/5)+130,(
int)(x2/5)+45,(int) (y2/5)+130);
[Link]("d="+[Link](distance12),
(int)(((x1/5)+30 + (x2/5) +30)/2), (int) (((y1/5)+128 +(y2/5)+128) /2));
a = [Link];
}
}
}
//on affiche les sommets:
for(int i=0; i<[Link](); i++) {
int x = ((Arret)[Link](i)).coordX;
int y = ((Arret)[Link](i)).coordY;
String nom = ((Arret)[Link](i)).nom;
int numArret = [Link](nom);
//On peint le fond des arrets

[Link]([Link]);
[Link]((int)(x/5)+30, (int)(y/5)+115, size, size);
if([Link](numArret)) {
[Link](new Color(10, 220, 100));
 [Link]((int)(x/5)+30, (int)(y/5)+115, size, size);
[Link]([Link]);
[Link](nom, (int)(x/5) + 37, (int)(y/5) + 135);
}
else {
[Link]([Link]);
[Link](nom, (int)(x/5) + 37, (int)(y/5) + 135);
}

}
} catch
(IOException e) {
// TODO Auto-generated catch block
[Link]();
}
}

public void setStationSuccesive(ArrayList stationSuccesive) {

[Link] = stationSuccesive;
}

VI.i) Classe « InterfaceGraphique»

import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];

import [Link];
import [Link];
import [Link];
import [Link];

public class interfaceGraphique {

static JComboBox cBDepart = new JComboBox();

static JComboBox cBArrivee = new JComboBox();
static String provenance="A1";
static String destination="A1";
static ArrayList listeNomArrets;
static Vector Q;
static Fichier graphe;
static GrapheParListe g;
static RecherchePanneau pan;
static JFrame fenetre = new JFrame();
static JPanel pan2 = new JPanel();
static PlanGraphique plan;

public static void main(String[] args) throws IOException

{
 listeNomArrets = [Link]();
Q = [Link]();
graphe = new Fichier("kelkonk_bus.graph","R");

g = new GrapheParListe(graphe, listeNomArrets ,Q);

int provId = [Link](provenance);

int destId = [Link](destination);

Vector S = [Link](provId);
Vector trajetFinal = [Link](provId , destId , S);
ArrayList stationSuccessive = (ArrayList) [Link](0);

Graphics gF = [Link]();

//Initialisation de la fenetre
[Link](800,750);
[Link]([Link]);
[Link]((new BorderLayout()));
[Link]("Recherche d'un itinéraire - Transport Bus");
[Link](null);
[Link](JFrame.EXIT_ON_CLOSE);

//Creation d'un conteneur Panneau de Recherche

pan = new RecherchePanneau(gF,stationSuccessive,listeNomArrets);
[Link]((new BorderLayout()));

int correspondance = [Link](stationSuccessive);

[Link](correspondance);
[Link]([Link]((int)
[Link](1)+300*correspondance));

[Link]([Link]);

//Ajout Bouton recherche

JButton but1 = new JButton("Recherche");
[Link](new RechercheListener());
[Link](but1);
[Link]([Link]);

[Link](pan2,[Link]);

//Ajout du plan du réseau

plan = new PlanGraphique(gF, stationSuccessive);
[Link](plan,[Link]);

//Ajout des 2 menus déroulants

[Link](85, 107, 88, 28);
[Link]([Link]);

for(int i=0; i<[Link](); i++) {

[Link]([Link](i));
}

//On ajout un Listener pour ecouter les changements de depart et

d'arriver de l'utilisateur
[Link](new DepartListener());

[Link](586, 107, 88, 28);

 [Link]([Link]);

for(int i=0; i<[Link](); i++) {

[Link]([Link](i));
}
[Link](new ArriveeListener());

//Ajout des 2 menus et du panneau de recherche dans la fenetre

[Link](cBDepart);
[Link](cBArrivee);
[Link](pan,[Link]);
[Link](true);

//Classe interne implémentant l'interface ItemListener

static class DepartListener implements ActionListener{

@Override
public void actionPerformed(ActionEvent arg0) {
provenance=[Link]().toString();
}
}

static class ArriveeListener implements ActionListener{

@Override
public void actionPerformed(ActionEvent arg0) {
destination=[Link]().toString();
}
}

static class RechercheListener implements ActionListener{

@Override
public void actionPerformed(ActionEvent arg0) {

int provId = [Link](provenance);

int destId = [Link](destination);

Vector S = [Link](provId);
Vector trajetFinal = [Link](provId , destId , S);
ArrayList stationSuccessive = (ArrayList) [Link](0);

[Link]();
[Link]().removeAll();

[Link](stationSuccessive);
[Link]();

[Link](plan, [Link]);
[Link](pan2,[Link]);

int correspondance = [Link](stationSuccessive);

[Link](correspondance);
[Link]([Link]((int)
[Link](1)+300*correspondance));
[Link]([Link](stationSuccessive,
listeNomArrets));

[Link]();
 [Link](pan);
[Link](cBDepart);
[Link](cBArrivee);
[Link]();
}
}