In this TD, we will implement a particular type of graph, where nodes represent cities on a map and arcs are drawn between neighbouring cities. We will then implement several path search algorithms on the graph: each search algorithm will attempt to find a path from a given origin node (origine) to a given destination node (destination), passing through intermediate nodes. For example, consider the following graph with 9 nodes, where each line between nodes represents two arcs, one in each direction.
Example Graph: origine node 2, searching for destination node 8
In this graph, there are several paths from node 2 to 8. For example, the path 2 → 5 → 7 → 8 consists of three arcs, and is shorter than an alternative path that passes through node 4. We will see that different search algorithms often produce different paths and their performance may vary depending on the structure of the graph. To begin with, we will implement two data structures:
We will use different interfaces and classes coming from the Java standard library:
To begin with, create a new project TD7. We give you partial code, available at td7.zip. Download it and unzip it within the TD7 project (in the src/ folder if the project has one). This will create two packages called carte and graphe, and a Test class (remember to refresh within Eclipse using "F5").
Classes of the carte package should not be modified. They are:
public class Ville { // Donne le nom public String getNom(); // Calcule la distance en metres entre la ville courante et dest public double distance(Ville dest); ... }
public class Arc { public final Ville source, target; public int length; public Arc(Ville o,Ville d, int l){ source=o; target=d; longueur=l; } ... }
Classes of the graphe package are incomplete and will be modified throughout the TD. They are:
We will test the programs on the maps of Mayotte and France. We shall be using the files mf.txt (link for laptops: mf.txt) and fr.txt (link for laptops: fr.txt). If you are working on the workstations in the lab, it is not necessary for you to download these files, they are already installed. If you are working on your own computer, download and install these files in the project TD7. If you would like to work on files for other countries, you can find them here.
Our goal is to construct a path from a given origine to a given destination. In the process of finding this path, we will construct a tree of paths from origine to every city visited so far. This tree data structure is implemented by the class PathTree as follows. It contains a field fromParent of type Map<Ville,Arc> that maps every Ville visited so far to the last Arc through which it was reached from the origin. For example, the picture depicts a partial path tree starting from the origine node 2.
Example Path Tree: origine node 2, searching for destination node 8
public class PathTree { // The root of the tree Ville root; // A map from Ville to the Arc through which it is connected to its parent Map<Ville,Arc> fromParent; // Constructor, initializes root, fromParent public PathTree(Ville o) {...} // The root public Ville root() {...} // The arc to Ville v from its parent in the tree public Arc fromParent(Ville v) {...} // Is the Ville v in the tree? public boolean member(Ville v){...} // The number of Villes in the tree public int size() {...} // All the Villes in the tree public Set<Ville> allVilles() {...} // Add a new arc reaching a new leaf public void addArc(Arc a){...} // Compute the path from the origine to a given destination public List<Arc> pathToDestination(Ville destination){...} }
This class uses LinkedHashMap<Ville,Arc> to implement the Map type for fromParent. To use LinkedHashMap in this way, one needs to carefully define the equals and hashCode methods for the index (Ville) to ensure that distinct indices are mapped to distinct entries in the map. We have already provided these methods in Ville.java. In the rest of this TD, you can assume that all such maps (LinkedHashMap<Ville,...>) work correctly.
Complete the method addArc that needs to add the given Arc in the tree by modifying fromParent. If the source of the Arc is not already in the tree, you should throw an IllegalArgumentException.
Complete the method pathToDestination that uses fromParent to compute the path from origine to a given destination. The result of the method has type List<Arc> which you may implement using LinkedList<Arc>. Here, the List interface indicates the semantics of an ordered collection.
Test your code with the function test1 in the Test class. You will see the result:
Path tree with root Accua Latitude: -12.7225 Longitude: 45.0563889 87 cities in tree Path to Pamandzi: Accua -> M'Tsangadoi -> Mtsamboro -> Hamjago -> Mtsahara -> Andrema -> M'Tsangamboi -> Bandraboua -> Gnambo -> Dzoumogne -> Bouilloni -> Longoni -> Kangani -> Kongo -> Majikavo Koropa -> Bandrajou -> Majikavo Lamir -> Kaoueni -> Kavani -> Mambutzou -> Dzaoudzi -> Foungoujou -> Labattoir -> Pamandzi path is of length 23 steps length is 39.55333607500388 kmand the window:
Upload PathTree.java.
We will now construct graphs that represent the map, where each Ville will be connected by an Arc to a number of other Ville that we call its neighbours. First, consider the incomplete class GrapheVille given in package graphe. It contains a field toNeighbours of type Map<Ville, List<Arc>> that maps each ville v to an ordered collection of Arcs, each of which has v as source and one of v's neighbours as target.
public interface GrapheVille { private Map<Ville, List<Arc>> toNeighbours; // Initialize toNeighbours public GrapheVille() {...} // Is Ville v in the graph? boolean contient(Ville v){...} // All the Villes in the graph Set<Ville> villes(){...} // Add a Ville to the graph void ajouterVille(Ville v){...} // Add an Arc to the graph void ajouterArc(Arc arc){..} // All the arcs that go out from Ville v to its neighbours List<Arc> arcsSortant(Ville v){...} }
Complete the class GrapheVille by implementing the methods shown here.
Test with the method test2 in Test.java. The result should look like the follows:
Le graphe a 87 sommets Accua Latitude: -12.7225 Longitude: 45.0563889 Andrema Latitude: -12.6786111 Longitude: 45.0977778 Apandzo Latitude: -12.8305556 Longitude: 45.1302778 Bambo Est Latitude: -12.9261111 Longitude: 45.1738889 Bambo Ouest Latitude: -12.9219444 Longitude: 45.0872222 Bandraboua Latitude: -12.7016667 Longitude: 45.1205556 Bandrajou Latitude: -12.7452778 Longitude: 45.2186111 Bandrani Latitude: -12.845 Longitude: 45.1019444 Bandrele Latitude: -12.9066667 Longitude: 45.1913889and the window:
Upload GrapheVille.java.
Next, we construct graphs where neighbours are any two cities within a certain distance of each other. Add a method connectNeighbours to GrapheVille that takes an argument maxDistance and adds an Arcs between any two distinct Ville that are less than maxDistance away from each other.
public void connectNeighbours(double maxDistance){...}
We will use the method double distance(Ville dest) of the class Ville that computes the distance between the current Ville and any other Ville. We will also use the method ajouterArc of the class GrapheVille to add an Arc between neighbouring Ville.
Test with test3. You should obtain:
To compute the proximity graph for France, replace mf.txt in initMayotte with fr.txt (and the two cities with Palaiseau and Montanciex). What do you obtain? Since the time taken by connectNeighbours is quadratic in the number of cities, constructing this graph will take a long time. Instead, from this exercise onwards, all our tests will use the function initFrance that uses a more efficient graph construction (implemented by the GrapheEuclidean in package graphe).
Upload GrapheVille.java.
We will now implement search algorithms on the GrapheVille data structure to construct paths from one Ville to another. Our intermediate search results (or search history) will be stored using the PathTree structure seen earlier.
We will now program a depth-first search on the graph data structure GrapheVille using the PathTree class above. We have defined a class GraphSearch in package graphe. Add a method that performs depth-first search as follows:
public static boolean dfs(GrapheVille g, Ville origine, Ville destination, PathTree history) {
As the method visits new Villes it adds them to history. Attention: The method dfs should be recursive, and it should never explore the same node twice. It must return true as soon as it finds the destination and false otherwise.
Test your code with the function test4 in the Test class. The result should be (according to the destination city):
dfs : 27 ms Montanceix is reachable from Palaiseau 7008 explored cities path is of length 3909 steps length is 10999.484760421541 kmDepending on the speed of your machine, the time taken in this test and the following exercises may vary, and depending on the structure of your code, the number of explored cities may be a few more or less, but if your code uses LinkedHashMap correctly in both PathTree and GraphSearch, your results should not be too far from those given here.
DFS route from Palaiseau to Montanceix
Upload GraphSearch.java.
public static boolean bfs(GrapheVille g, Ville origine, Ville destination, PathTree history, Queue<Ville> queue) { ... }Attention: A same node should not be enqueued twice.
Test your code with the function test5 in the Test class. The result should be:
bfs : 62 ms Montanceix is reachable from Palaiseau 16325 explored cities path is of length 279 steps length is 873.320506245472 km
BFS route from Palaiseau to Montanceix
Upload GraphSearch.java.
Breadth-first search looks at cities in the order in which they were encountered, but this is not the most efficient algorithm if we are only interested in the shortest path. Dijkstra's search algorithm finds the shortest path first by ordering the cities in the queue (that is, the cities that have not been considered yet) in the order of their distance from the origin. This distance is a rough estimate of the total path length (the closer a city is to the origin, the shorter the eventual path to the destination is likely to be).
To perform Dijkstra's search, we first define a class Distances (in graphe) that keeps track of the current estimate of the length of the shortest path between visited nodes and the origin.
public class Distances{ // Origin of the search final Ville origine; // Distance from each visited Ville to the origin private final Map<Ville, Double> distances; // Maximum distance public static final double INFINITY = Double.MAX_VALUE; // Constructor, initializes distances public Distances(Ville o){...} // Set the distance to a particular destination public void setDistance(Ville destination, double d){...} // Get the distance to a particular destination public double getDistance(Ville destination){...}
We define a class Estimate that represents a city with a distance. For Dijkstra's algorithm it is an estimate of the distance to the origin, that is, the length of the shortest path from the origin to the city.
public class Estimate { public final Ville city; public final double distance; public Estimate(Ville v, double d) { city = v; distance = d; } }
We would like to sort cities in order of increasing estimates. To compare two estimates, we define a new class DistanceComparator that implements the Comparator<Estimate> interface:
public class DistanceComparator implements Comparator<Estimate>{ // Ex.6: Compare distances stored in two Estimates public int compare(Estimate dest1, Estimate dest2){ ... } }
Complete the method compare. This method must return
Then add a function dijkstra to GraphSearch.java that uses Distances to optimize the search order. Instead of using a LinkedList<Ville> as the queue, as for BFS, you will now use the given PriorityQueue<Estimate> that uses a DistanceComparator to order the estimates in the queue. Then, a PriorityQueue<Estimate> is built by the caller and passed to dijkstra that uses it through the Queue<Estimate> interface.
public static boolean dijkstra(GrapheVille g, Ville origine, Ville destination, PathTree history, Queue<Estimate> queue) { ... }Note: The standard formulation of the Dijkstra's algorithm assumes a queue having an decreaseKey operation which can be done in O(log(n)) time. When the key, here the distance, is reduced the queue must adjust itself to maintain its invariant. This feature is not supported by java.util.PriorityQueue. It would be a very bad idea to try to replace it with a sequence remove(oldEstimate); add(newEstimate); since it would be in O(n) time. Here, we will simply add the new estimate, which would normally pass before the former. This does not change much the usual complexity of the algorithm.
Test your code with the function test6 in the Test class. The result should be:
dijkstra : 130 ms Montanceix is reachable from Palaiseau 16445 explored cities path is of length 289 steps length is 847.2658979768914 km
Dijkstra route from Palaiseau to Montanceix
Upload DistanceComparator.java et GraphSearch.java.
In the A* algorithm, we will further optimize the ordering in which estimates are stored in the PriorityQueue. Instead of just considering the distance from the origin, we also consider an estimated distance to the destination. In particular, each Estimate should now contain a distance estimate calculated as the sum of the current distance to the origin with the geographical distance to the destination.
Then, add a method aStar in GraphSearch that uses this new estimate:
public static boolean aStar(GrapheVille g, Ville origine, Ville destination, PathTree history, Queue<Estimate> queue) { ... }Test your code with the function test7 in the Test class. The result should be as follows:
A* : 63 ms Montanceix is reachable from Palaiseau 10970 explored cities path is of length 290 steps length is 847.2658979768914 km
A* route from Palaiseau to Montanceix
Upload GraphSearch.java.