Graphs and Graph Search
par Karthikeyan Bhargavan et Philippe Chassignet

Login :  Mot de passe :

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:

• a tree representing the paths from origine to a number of other cities (Exercise 1);
• a graph representing all the cities on a map and their interconnections (Exercises 2 and 3).
Relying on this, we will implement four different path search algorithms: Depth-first Search (Exercise 4), Breadth-first Search (Exercise 5), Dijkstra (Exercise 6) and A* (Exercise 7), and see how they compare.

Java standard library

We will use different interfaces and classes coming from the Java standard library:

• the Map interface, associating values to objects. We use its LinkedHashMap implementation, based on hash tables;
• the Collection interface, representing finite multisets. It is implemented in particular by LinkedLists;
• the List interface, representing ordered collections. It is implemented in particular by LinkedLists;
• the Set interface, representing finite sets. We do not care about its implementations;
• the Queue interface, representing first-in-first-out collections. It is implemented using LinkedLists and PriorityQueues;
• the Comparator interface, which gives a total ordering between objects of a certain type. We are going to give an implementation of it.
You are encouraged to look at those libraries to see which methods are available on each data structure.

Getting started

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:

• Ville: This class represents a city, that is, its name and coordinates (latitude, longitude).
```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);

...
}
```
• Arc: This class represents a link between two neighbouring cities.
```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;
}
...
}
```
• Carte, Etiquettes, IndexParNom and Visualisation, used in the Test file to perform inputs and outputs.
You are encouraged to look at the Ville and Arc classes before starting.

Classes of the graphe package are incomplete and will be modified throughout the TD. They are:

• PathTree, representing a tree of paths from origine to a number of other cities;
• GrapheVille, representing a graph of all the cities on a map and their interconnections;
• GraphSearch, containing the different path search algorithms you will implement;
• Distances, computing the distance from each city to origine;
• Estimate, an estimate of the distance from a city to a destination;
• DistanceComparator, comparing two cities according to their estimated distance to the destination;
• GrapheEuclidean, an auxiliary class for efficiently computing proximity graphs.
You will discover them during the different questions.

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.

A Tree of Paths

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

// 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.

• If the destination is not in the tree, the method should return an empty list.
• If the destination is the root, the method also returns an empty list. Remember to use v1.equals(v2) to compare two Ville objects, not v1 == v2.
• In all other cases, the method reconstructs the path by going up the tree from the destination to the origine. Since the path is retrieved in reverse order, remember to ensure that the returned List contains the path in the correct order: the first Arc must have origine as the source, and the last Arc must have destination as the target.

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 km
```
and the window:

Proximity Graphs

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.

• The constructor must initialize toNeighbours using a class that implements Map: use LinkedHashMap<Ville,List<Arc>> to obtain the same results as the tests below.
• The toNeighbours map contains all the Villes and Arcs of the graph: each Ville in the graph is a key in the map. So contient and villes simply use the appropriate methods of the Map interface.
• To add a new Ville v to the graph, ajouterVille adds an entry to toNeighbours that maps v to the empty list of Arcs. If a Ville is already in the graph, ajouterVille does nothing.
• If the source of a given Arc is not defined in the graph, ajouterArc must throw an IllegalArgumentException, otherwise it retrieves the list of Arcs that the source is mapped to and appends the arc to the end of this list.
• If the given Ville is not defined in the graph, arcsSortant must throw an IllegalArgumentException, otherwise it returns the arcs that the Ville is mapped to.

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.1913889
```

and the window:

Connecting Neighbours

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).

Searching for Path in the Graph

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.

Depth-first Search

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 km
```
Depending 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

Add a method to perform breadth-first search. Use the given Queue to store the Villes that are waiting to be explored.
```  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

Dijkstra

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

• 0 if both dest1 and dest2 have the same distance,
• -1 if dest1 has a smaller distance than dest2, and
• +1 if dest1 has a larger distance than dest2.

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

A*

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