Example Graph: origine node 2, searching for destination node 8
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 TD8. We give you partial code, available at td8.zip. Download it and unzip it within the TD8 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 TD8 and modify the field chemin in Test.java to "". 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 rooted at origine with paths to every city visited so far. This tree data structure is implemented by the class PathTree as follows. It contains a field root of type Ville and 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 root. For example, the picture depicts a partial path tree rooted at node 2.
Example Path Tree: root node 2, searching for destination node 8
public class PathTree {
// The root of the tree
private Ville root;
// A map from Ville to the Arc through which it is connected to its parent
private Map<Ville,Arc> fromParent;
// Constructor, initializes root, fromParent
public PathTree(Ville o) {...}
// The root
public Ville root() {...}
// 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 Iterable<Ville> allVilles() {...}
// All the Arcs in the tree
public Iterable<Arc> allArcs() {...}
// The arc to Ville v from its parent in the tree
public Arc fromParent(Ville v) {...}
// Add a new arc reaching a new leaf
public void addArc(Arc a){...}
// Compute the path from the root 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, we have carefully defined the equals and hashCode methods for the index (Ville) to ensure that distinct indices are mapped to distinct entries in the map. 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 the root 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.
For now, the body of method connectNeighbours must be left empty.
Test with the method test2 in Test.java. The result should look like the follows:
There are 87 nodes in this graph. 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.1913889 There are 86 arcs in this graph.and the window:
Upload GrapheVille.java.
Next, we construct graphs where neighbours are any two cities within a certain distance of each other. Now fill in the method connectNeighbours that takes an argument maxDistance and adds an Arcs between any two distinct Ville (using equals) that are less than or equal to maxDistance away from each other.
public void connectNeighbours(double maxDistance){...}
You can assume that the graph already contains all cities as nodes but no arc. You will use the method double distance(Ville dest) of the class Ville that computes the distance between the current Ville and any other Ville. You will also use the method ajouterArc of the class GrapheVille to add a new Arc between neighbouring Ville.
Test with test3. The result should be:
There are 166 arcs in this graph.and you should obtain the following window, where the color of each arc is a function of its length field:
To compute the proximity graph for France, replace mf.txt in initMayotte with fr.txt (and the two cities with Palaiseau and Montanceix). What do you obtain? Since the time taken by connectNeighbours is quadratic in the number of cities, you will find that constructing this graph takes 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.
Depending on the speed of your machine, the time taken in the test for 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 match those given here.
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 recursive 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 never explore the same node twice; so, use history to check if a node has been seen before. 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 : 1 ms Palaiseau is reachable from Palaiseau 1 explored cities path is of length 0 steps length is 0.0 km -------------------------- dfs : 3 ms Champlan is reachable from Palaiseau 2 explored cities path is of length 1 steps length is 2.6208947972423045 km -------------------------- dfs : 54 ms Chilly-Mazarin is reachable from Palaiseau 4131 explored cities path is of length 2815 steps length is 7878.342507674686 km -------------------------- dfs : 27 ms Epinay is reachable from Palaiseau 4113 explored cities path is of length 2806 steps length is 7847.155269004612 km -------------------------- dfs : 25 ms Lisses is reachable from Montbran 4577 explored cities path is of length 2991 steps length is 8367.831618027207 km -------------------------- dfs : 82 ms Montanceix is reachable from Palaiseau 7008 explored cities path is of length 3909 steps length is 10999.484760421541 km -------------------------- dfs : 78 ms Echou is not reachable from Palaiseau
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; use history to enforce this.
The method must return true as soon as
it finds the destination and false otherwise.
Test your code with the function test5 in the Test class. The result should be:
bfs : 1 ms Palaiseau is reachable from Palaiseau 1 explored cities path is of length 0 steps length is 0.0 km -------------------------- bfs : 3 ms Champlan is reachable from Palaiseau 2 explored cities path is of length 1 steps length is 2.6208947972423045 km -------------------------- bfs : 1 ms Chilly-Mazarin is reachable from Palaiseau 6 explored cities path is of length 2 steps length is 6.32738864556335 km -------------------------- bfs : 0 ms Epinay is reachable from Palaiseau 31 explored cities path is of length 4 steps length is 13.740376342205787 km -------------------------- bfs : 1 ms Lisses is reachable from Montbran 23 explored cities path is of length 4 steps length is 10.033893613377847 km -------------------------- bfs : 82 ms Montanceix is reachable from Palaiseau 16325 explored cities path is of length 279 steps length is 873.320506245472 km -------------------------- bfs : 59 ms Echou is not reachable from Palaiseau
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
Upload DistanceComparator.java.
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
remove(anObject) carries a sequential search that would be of
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 : 4 ms Palaiseau is reachable from Palaiseau 1 explored cities path is of length 0 steps length is 0.0 km -------------------------- dijkstra : 3 ms Champlan is reachable from Palaiseau 10 explored cities path is of length 1 steps length is 2.6208947972423045 km -------------------------- dijkstra : 0 ms Chilly-Mazarin is reachable from Palaiseau 23 explored cities path is of length 2 steps length is 6.32738864556335 km -------------------------- dijkstra : 1 ms Epinay is reachable from Palaiseau 72 explored cities path is of length 5 steps length is 12.654772685282524 km -------------------------- dijkstra : 1 ms Lisses is reachable from Montbran 27 explored cities path is of length 4 steps length is 10.033893613377847 km -------------------------- dijkstra : 179 ms Montanceix is reachable from Palaiseau 16445 explored cities path is of length 289 steps length is 847.2658979768914 km -------------------------- dijkstra : 113 ms Echou is not reachable from Palaiseau
Dijkstra route from Palaiseau to Montanceix
Upload 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* : 5 ms Palaiseau is reachable from Palaiseau 1 explored cities path is of length 0 steps length is 0.0 km -------------------------- A* : 26 ms Champlan is reachable from Palaiseau 4 explored cities path is of length 1 steps length is 2.6208947972423045 km -------------------------- A* : 0 ms Chilly-Mazarin is reachable from Palaiseau 6 explored cities path is of length 2 steps length is 6.32738864556335 km -------------------------- A* : 1 ms Epinay is reachable from Palaiseau 18 explored cities path is of length 5 steps length is 12.654772685282524 km -------------------------- A* : 1 ms Lisses is reachable from Montbran 10 explored cities path is of length 4 steps length is 10.033893613377847 km -------------------------- A* : 159 ms Montanceix is reachable from Palaiseau 10970 explored cities path is of length 290 steps length is 847.2658979768914 km -------------------------- A* : 128 ms Echou is not reachable from Palaiseau
A* route from Palaiseau to Montanceix
Upload GraphSearch.java.