First of all, get the file graphestp2.tar.gz and uncompress it:
gunzip graphestp2.tar.gz
tar xvf graphestp2.tar
rm graphestp2.tar
cd GraphesTp2; ls
This archive contains C programs for manipulating graphs. Documentation of
these programs can be found here:
Reminder on the first practical sessions: description of the data structures used to represent a graph by Γ (its successors map). Also remind to refer to the documentation of the source code, including:
|
|
The image above on the left (source CERN) is taken from a picture of bubble chamber. On the right, the image was thresholded to detect the brightest regions (image bs0). The file bs0.list contains the coordinates of the centroids of these regions (the first line of the file indicates the number of points). Two other images are available: bs1 and bs2, whose coordinates files are respectively bs1.list and bs2.list. The goal of this session is to reconstruct, at best, particle trajectories (sets of points more or less aligned) by ignoring the isolated points.
1. Write a program that reads a file containing centroids, and that builds an asymmetric graph (1) ( thus also a graph without loop (2)) such that:
For further work, this graph should be represented in memory, both with a "successors" map (use the provided function AjouteArc) and with a "list of arcs" (use the tete -standing for head in French- and queue -standing for tail in French- fields of the graphe data structure). Moreover, we associate to each arc (in the field v_arcs of the graphe data structure) the distance between the points corresponding to its ends .
To help,we provide a program that reads a file containing points, builds a trivial graph (vertices only, no arc) whose vertices correspond to the points of the file, and allows this graph to be visualized as a PostScript file. The vertex coordinates are stored in the x and y fields of the graphe data structure).
(1) : G is an asymmetric graph if for any two vertices x and y of G, [ (x,y) is an arc of G ] implies [ (y,x) is not an arc of G ].
(2) : G is a graph without loop (or anti reflexive) if for any vertex x of G, (x,x) is not an arc of G.
2. Visualize the graphs obtained for different values of t. Can you find a value of t that allows "noise points" to be isolated from "trajectories of particles" in the three images bs0, bs1, bs2?
3. What is (approximately) the minimum value tmin of t such that the graph obtained from bs0.list is connected?
Propose a method (without implementing it) to automatically find the exact value of tmin, for any set of points. What is the time complexity of your method?
4. Assume that the trajectories do not intersect each other and that they do not contain cycle. Compute a minimum spanning tree of the graph weighted by the distances. To this end, use the algorithm studied in class (Kruskal algorithm, see slide 13 of lecture 9). An implementation of this algorithm for computing maximum spanning trees is provided here. Before using it, take enough time to be sure that you understand it. Discuss the results obtained on the three images bs0, bs1, bs2. In particular: what are the drawbacks of the method? Illustrate these drawbacks by specific examples.
Remark: The sorting is not performed on the values in table v_arcs of the graphe data structure, otherwise the weights of the arcs would no longer fit the data in tables tete and queue. The function TriRapideStochastique performs the sorting in an auxiliary table, which plays the role of an index to table v_arcs.
5. One can see in some configurations that it is necessary to consider the fact that points belonging to a same trajectory are approximately aligned.
We propose to redefine the weighting of the arcs, in order to favor the selection of arcs that are not only short, but that are also aligned with adjacent arcs. Moreover, this definition should be relatively simple to implement.
Propose several ideas, discuss them with your neighbors and submit them to the professor in charge of session. Implement the best one. Results?
