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
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:

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:

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:

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:

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, destination node 8
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 km
and the window:

Upload PathTree.java.

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.

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:

resultat mf aretes

Upload GrapheVille.java.

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:

Proximity graph for Mayotte

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.

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
DFS route from Palaiseau to Montanceix

Upload GraphSearch.java.

Breadth-first Search

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
BFS route from Palaiseau to Montanceix

Upload GraphSearch.java.

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

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
Dijkstra route from Palaiseau to Montanceix

Upload DistanceComparator.java et GraphSearch.java.

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
A* route from Palaiseau to Montanceix

Upload GraphSearch.java.