TD 4 - Graph drawing and network visualization

Introduction:

The goal of this exercice session is to implement two algorithms for computing graph layouts.

Before starting to code

You can download here a few datasets (3D meshes in OFF format and graphs, and networks in MTX format) for testing your code.
Download the following classes for this TD (skeleton to be completed and programs for testing): src.zip
As in previous TDs you need the following Java libraries: TC.jar, core.jar (Processing library, v 1.51), Jcg.zip (source code of the Jcg library)
Here are: the Javadoc for this TD and the Javadoc of the Jcg library.

In order to test your code, you can run (as Java application) the classes MeshParameterization and SpringDrawing which provides methods for rendering the original mesh and computing the corresponding 2D and 3D layouts.
Remarks:

you can perform one iteration of the iterative methods with the touch c
you can change the rendering mode with the touch r

1. Planar Parameterization

The pictures below show the planar parameterization of a 3D spherical mesh (162 vertices).

Exercice

Tasks: The goal of this exercice is to implement the iterative computation of the Tutte's barycentric embedding
By default, we set as outer face an arbitarty triangle face 0 (e.g. having index 10): the k vertices belonging to the outer face are classified as boundary vertices, while all remaining n-k vertices are called inner vertices.

complete the class IterativeTutteLayout that allows to compute a planar layout of the mesh; you will be asked to complete the method oneIteration() that perform one iteration of the Tutte algorithm to compute the 2D coordinates of the vertices (they are stored in the field Point_2[] points).

2. Force-directed layouts of network:

Implement the force-directed paradigm illustrated in the lecture in order to compute a 2D layout of the input network

complete the class FR91Layout that allows you to compute a (2D) layout of the input network obtained with the FR91 algorithm (for more details, see the slides the lecture 4). You will be asked to complete the method oneIteration().