IFT1020 - Automne 2004
TP4 - Implantation d'un Graph
 
But: Implanter un graphe et utliser une recherche de "A*" pour trouver le plus court chemin
Date limite: 7 décembre, 12h00 (midi)
Étape 1: Implanter interface Graph, interface Node et interface Edge
Vous devez implanter trois Interfaces,Graph
, Node
, et Edge
. Voici les interfaces:
 
interface Graph Graph.java
import java.util.*; interface Graph { // Return the number of nodes public int nodeCount(); // Return the number of edges public int edgeCount(); // Clears graph public void clear(); // Return a list of all nodes public List getNodes(); // Return the list of all edges public List getEdges(); // Add a node public void addNode(String k, Object n); // Add an edge public void addEdge(String k1, String k2); // Add an edge with cost public void addEdge(String k1, String k2, int cost); // Does node exist in graph public boolean hasNode(String key); // Does edge exist connecting n1 to n2 public boolean hasEdge(String k1, String k2); // Return edge public Edge getEdge(String k1, String k2); // Return node public Node getNode(String k); public double getEstimatedCost(Node n1, Node n2); }interface Node Node.java
import java.util.*; interface Node { public String getKey(); public Object getObject(); public List getEdges(); public boolean equals(Object o); public String toString(); }interface Edge Edge.java
interface Edge { public Node getSource(); public Node getDest(); public int getCost(); public boolean equals(Object o); public String toString(); }
Étape 2: Implanter A* et le Tester
Téléchargez et compilez les fichiers AStar.java AStarNode.java et AStarSearch.java.
Avec ces classes vous pouvez trouver le plus court chemin entre deux noeuds
dans un graphe. Utilisez le méthode List = AStar.findShortestPath(Node, Node, Graph)
.
Testez votre code avec Test1.java qui implante le graphe suivant:
import java.util.*; public class Test1 { public static void main(String[] args) { Graph g = new MapGraph(); int i=0; g.addNode("a","A"); g.addNode("b","B"); g.addNode("c","C"); g.addNode("d","D"); g.addNode("e","E"); g.addNode("f","F"); g.addNode("g","G"); g.addNode("h","H"); g.addEdge("a","b",7); g.addEdge("b","c",4); g.addEdge("c","d",8); g.addEdge("d","e",22); g.addEdge("e","f",9); g.addEdge("g","h",2); g.addEdge("h","a",9); g.addEdge("g","b",4); g.addEdge("a","d",19); g.addEdge("h","d",3); System.out.println(g); System.out.println("Shortest path from a to d"); List nodesPath = AStar.findShortestPath(g.getNode("a"),g.getNode("d"),g); System.out.println(nodesPath); } }Pour imprimer le graph vous pouvez utilizer cette toString dans votre implementation del Graph:
public String toString() { StringBuffer b = new StringBuffer(); b.append("Nodes--------------------\n"); List nodeList = getNodes(); ListIterator lIt = nodeList.listIterator(); while (lIt.hasNext()) { Node tmpNode = (Node) lIt.next(); // remember: It automatically calls toString of the given object! b.append(tmpNode + "\n"); } b.append("Edges--------------------\n"); List edgeList = getEdges(); lIt = edgeList.listIterator(); while (lIt.hasNext()) { Edge tmpEdge = (Edge) lIt.next(); // remember: It automatically calls toString of the given object! b.append(tmpEdge + "\n"); } return b.toString(); }Le résultat de
java Test1
devrait être:
1008 pift1020@bor ~/HTML/tp4>java Test1 Nodes-------------------- Node[d]: D Node[a]: A Node[h]: H Node[c]: C Node[f]: F Node[g]: G Node[b]: B Node[e]: E Edges-------------------- Edge[h <--> a]: 9 Edge[d <--> e]: 22 Edge[g <--> b]: 4 Edge[h <--> d]: 3 Edge[a <--> b]: 7 Edge[g <--> h]: 2 Edge[b <--> c]: 4 Edge[e <--> f]: 9 Edge[a <--> d]: 19 Edge[c <--> d]: 8 Shortest path from a to d [Node[a]: A, Node[h]: H, Node[d]: D]
Étape 3: Test "Generique"
On vous donne aussi un autre ficher java qui va tester la structure du Graph au fond. Ce ficher s'appelle GraphTest.java. Vous devez le compiler et l'exécuter dans votre projet (avecjava GraphTest
) et l'output qu'il va donner devrait être:
----------- Nodes Info ---------- Node[Denver]: Rain, 12.0°C, 1100.0 mbar Node[Montreal]: Snow, -1.0°C, 1012.0 mbar Node[Boston]: Sunny, 10.0°C, 1023.0 mbar Node[Washington DC]: Cloudy, 10.0°C, 1010.0 mbar Node[New York]: Sunny, 15.0°C, 980.0 mbar ----------- Edges Info ---------- Edge[Montreal <--> Boston]: 30 Edge[Denver <--> Montreal]: 50 Edge[New York <--> Boston]: 35 Edge[New York <--> Washington DC]: 40 ---------- General Tests --------- Node count: 5 Edge count: 4 Node[Denver] exists: true Node[Montreal]: Snow, -1.0°C, 1012.0 mbar Edges of Node[Montreal]: [Edge[Denver <--> Montreal]: 50, Edge[Montreal <--> Boston]: 30] Edge[Denver <--> Montreal] exists: true Edge[Montreal <--> Denver] exists: true Source: [Denver] - Dest: [Montreal] - Cost: 50 Clearing.. Node count: 0 Edge count: 0
Étape 4: Interface Usager
Voir le fichier aust_cities.txt.%%CITY,LATITUDE_DEGREE,LATITUDE_MINUTES,LONGITUDE_DEGREE,LONGITUDE_MINUTES Adelaide,34,55,138,36 Alice Springs,23,42,133,53 Brisbane,27,29,153,8 Broome,17,58,122,14 Cairns,16,51,145,43 Canberra,35,17,149,08 Darwin,12,28,130,51 Melbourne,37,47,144,58 Perth,31,57,115,52 Sydney,34,0,151,0 %%FROM http://www.australianexplorer.com/driving_distances.htm %%FULL DISTANCE MATRIX (Perth to Broome = 2415; Adelaide to Alice Springs = 1690) %%1690 %%2130,3060 %%4035,2770,4320 %%2865,2418,1840,4125 %%1210,2755,1295,5100,3140 %%3215,1525,3495,1965,2795,4230 %%0755,2435,1735,4780,3235,0655,3960 %%2750,3770,4390,2415,6015,3815,4345,3495 %%1430,2930,1030,4885,2870,0305,4060,0895,3990 1690 ,3060 4035,,4320 ,2418,,4125 ,,,5100, ,1525,,1965,,4230 0755,2435,,,,0655,3960 ,3770,4390,,,,,3495 1430,,,4885,,,,,Le fichier contient 10 villes australiennes avec leur longitude et latitude. Le fichier contient aussi les distances entre certaines villes. Les lignes commençant par %% sont des commentaires.
Creez un programme qui s'appelle TP4.java
. Votre programme doit afficher les villes sur un panneau comme dans la figure suivante:
Lorsque vous cliquez sur deux villes, le chemin plus court est indiqué avec un grand trait rouge:
Détails
Vous pouvez voir un exemple du programme en faisant les commandes suivantes. Il est normal que vous ne puissiez pas lire le contenu de ce répertoire, mais vous pouvez accéder quand même au programme en tapant ces commandes telles quelles.
inclure jdk-1.4 cd ~pift1020/HTML/tp4 java TP4 aust_cities.txtIl faut ensuite envoyer, par la procédure de remise électronique habituelle, les fichiers nécessaires à l'éxécution de votre programme avant le 7 decembre 2004 à 12:00 (midi). Vous remettrez également une copie papier d'un court rapport et de votre programme Java lors de la séance du cours du 7 decembre.
Ce TP sera noté sur 10.
Résultats corrects | 3 |
Implantation des Interfaces | 3 |
Interface usager | 2 |
Lisibilité du code | 1 |
Rapport | 1 |
bonne chance
Doug Eck