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 (adjacencies are not determined by road connections, but instead by the geodesic distance, precisely two cities are considered as adjacent if their geodesic distance is smaller than a certain maximal value). We will then implement two classical (greedy) algorithms, Kruskal's algorithm and Prim's algorithm, to find the minimum spanning tree in each connected component of the graph of cities, whose arcs are weighted by the geodesic distance. (You will normally be expected to complete at least up to question 6.)
Left: a graph with two connected components. Right: the arcs of the graph are assigned weights; the arcs of the two minimum spanning trees (one for each connected component) are shown bolder.
We will use different interfaces and classes coming from the Java standard library:
To begin with, create a new project TD5. We give you partial code, available at td_5.zip. Download it and unzip it within the TD5 project (in the src/ folder if the project has one). This will create three packages called arbres, carte and graphe, and a Test class (remember to refresh within Eclipse using "F5").
The package arbres contains the squeletons of three classes: ArcComparator, UnionFind, and SpanningTree, which will have to be completed in exercises 3 to 8 (in order to compute minimum spanning trees of proximity graphs of cities).
The package carte contains two classes, Carte and Visualisation, which are used to load and visualise a map in a graphical window. These classes should not be modified.
The package graphe contains four classes:
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; } ... }
We will test the programs on the maps of Mayotte and France. Download the files mf.txt and fr.txt, and install these two files in the main directory TD5 of the TD. If you would like to work on files for other countries, you can find them here.
We will construct graphs of cities, 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 class 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 test1 in Test.java. The result should look as 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 test2. 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.
Test with test3. The result should be:
-1 1 1 0
Upload ArcComparator.java.
Remark: the union operations will be applied to arcs of a geographic map that are considered in the order given by the geodesic distance; it is reasonable to assume that the components along the way will look quite "random", so that the underlying trees of the union-find structures are expected to be quite well balanced. Therefore you do not have to use size comparison as in TD2, but you should use iterative path compression in the find method.
Test with test4. The result should be:
true true false
Upload UnionFind.java.
We can now implement a first version of Kruskal's algorithm. At first we remind you how Kruskal's algorithm works:
Upload GrapheVille.java.
Fill in the method public static Collection<Arc> kruskal(UnionFind u, GrapheVille g) in the class SpanningTree.java, which is to return the collection of the arcs that forms the minimum connecting spanning forest. The UnionFind argument u is initially empty and, at return time, it should contain a description of the non-trivial connected components of g. This side-effect will be useful in the next exercise.
Remark: beware that Collection<E> (with E the type of elements in the collection) is not a class but an interface. Therefore, it has to be instantiated using an implementing class, for instance with an instruction such as Collection<E> col=new LinkedList<E>().
Test with test5. The result should be (the computation time depending on device/implementation):
Computation time (Kruskal first version) : 613 ms Total length: : 110191528 m 49390 connected citiesand you should obtain the following window, where the arcs in the minimum connecting spanning forest F are colored orange, and arcs not in F are light gray:
Upload SpanningTree.java.
Remark: it is recommended to use a HashMap<Ville,Collection<Arc>> listes that maps each root of the UnionFind (a root for each connected component) to the list of arcs of the minimum spanning tree of the corresponding connected component, and to return listes.values() at the end of the method.
Test with test6. The result should be:
Computation time (Kruskal second version) : 707 ms Total length : 110191528 m 49390 connected cities 3330 components in the forestand you should obtain the following window, where the arcs in the minimum connecting spanning forest F are colored (a color is randomly assigned to each tree-component), and arcs not in F are light gray:
Upload SpanningTree.java.
At first we recall how Prim's algorithm works. It uses a priority queue q (here, a queue of arcs, with the priority given by having smaller distance) as an auxiliary structure. One starts at a Ville v, puts all arcs at v into q, and remove v from the set of non-visited elements. Then as long as q is not empty,
Fill in the method public static Collection<Arc> primTree(HashSet
Test with test7. The result should be:
Computation time (Prim first version) : 109 ms Total length: : 44973288 m 20002 connected citiesand you should obtain the following window, where the arcs in the minimum spanning tree T of the component containing ''Palaiseau'' are colored orange, and arcs not in T are light gray:
Upload SpanningTree.java.
To peek (without removing) one element from a collection or a set, one can paste the following generic method inside class SpanningTree and use it properly:
public static <E> E peekOne(Collection<E> c) { for (E e : c) return e; return null; }
Test with test8. The result should be:
Computation time (Prim second version) : 506 ms Total length : 110191528 m 49390 connected cities 3330 components in the forestand you should obtain the following window, where the arcs in the minimum connecting spanning forest F are colored (a color is randomly assigned to each tree-component), and arcs not in F are light gray:
Upload SpanningTree.java.
Upload SpanningTree.java.