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 (avec java 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.txt
      
Il 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

Retour à la page principale d'ift1020
Last modified: Thu Dec 2 07:47:21 EST 2004 par Douglas Eck [douglas D0T eck AT umontreal D0T ca]