TD - Compression de graphes et maillages

(codage de la connectivité)


Votre opinion sur le cours :

Introduction:

Dans ce TD nous allons implanter et tester un certain nombre de méthodes pour coder graphes en 2D et 3D. Pour faciliter votre travail, un certain nombres de primitives pour la manipulation de graphes 2D et 3D ont été fournies à la librairie Jcg.
La documentation de la bibliothèque Jcg est consultable ici

Fichiers à télécharger pour le TD d'aujourd'hui:

0. Ce qu'il faut savoir sur les graphes et leur implementation en Jcg

Un graphe est donné par un ensemble de sommets V et une collection E d'arêtes (paires de sommets de V). De manière intuitive, un graphe décrit les connections ou relations d'adjacences entre objets de l'ensemble V. 


Figure 1 : (Gauche) Exemple de représentation d'un graphe à l'aide de listes d'adjacence. (Droite) Exemple de représentation utilisant la matrice d'adjacence.

Dans ce TD nous considérons des graphes correspondant à des maillages 2D et 3D triangulés: néanmoins, l'implementation fournie par Jcg permet de représenter des graphes généraux.

Implementation d'un graphe en Jcg

En ce qui concerne la représentation d'un graphe, il est à remarquer qu'il en existe de nombreuses: aujourd'hui nous allons considérer ici juste une représentation, celle basée sur une des Listes d'adjacences: pour cela on a les classes

La classe GeometricGraph met à disposition

On vous conseille de jeter un coup d'oeuil à la doc de Jcg.

Compression de graphes: codage des références par différences


L'idee est tres simple: on represente un graphe avec des listes d'adjacences (la liste des voisisin pour chaque sommet).
Mais la strategie qu'on va mettre en place consiste à coder les références (numéros des voisins), avec des différences:


Pour éviter dàavoir à manipuler des nombres négatifs, on va utiliser un vecteur sign[], de taille n, qui nous dit si le premier index est positif ou pas.


0. Pour commencer, quelques tests


Comment créer un graphe à partir d'un maillage 2D ou 3D?

On va commencer par tester la classe CompactGraph: il y a plusieurs type de testes à éffectuer, il suffira de supprimer/ajouter des commentaires, dans la fonction main.
	public static void main(String[] args) {
		System.out.println("TD5: mesh compression");
		//testCreate2DGraph();
		//testCreate3DGraph();
		//testEncoding2D();
		//test1a();
		//test1b();
		//test2();
		//test3();
		//testEncodingFinal();
		System.out.println("end");
	}
En testant avec la fonction 
testCreate2DGraph();
on devrait pouvoir créer un graphe géométrique en 2D, par exemple (avec n=1000):
Triangulation de Delaunay
 Triangulation non Delaunay


En testant avec la fonction 
testCreate3DGraph();
on devrait pouvoir créer un graphe géométrique en 3D, à partir d'une triangulation de Delaunay 3D

Voici un possible output.

Comment coder un graphe ?

Pour faciliter votre travail, on a déjà codé un ensemble de méthodes permettant de coder, et écrire dans un fichier, nu graphe géométrique (2Dou 3D). C'est fait pas la classe Encoding.

On peut commencer à tester avec  la fonction 
testEncoding2D();
Cela encode un graphe 2D, et écrit le résultat dans 2 fichiers .txt:

Voici un exemple:
-rwxrwxrwx 1 amturing Nessuno 67594 Feb  1 12:18 delaunay.off
-rwxrwxrwx 1 amturing Nessuno 24889 Feb  1 12:18 graphCompressed.txt
-rwxrwxrwx 1 amturing Nessuno 25048 Feb  1 12:18 graphNotCompressed.txt

Et un autre: triangulation de Delaunay 2D, avec 100.000 sommets

 8009402 Feb  1 12:53 delaunay100000.off

 3703680 Feb  1 12:53 graphCompressed.txt
 3732505 Feb  1 12:53 graphNotCompressed.txt

Comment compresser un graphe ?


On remarque tout suite, en regardant la taille (en Byte) des fichiers construits, que:
Remarque: sans ou avec codage, la taille des fichiers (non compressés) est à peu près la meme.

Peut-on faire mieux?
Vous pouvez essayer à compresser les fichiers .txt et .off avec le programme "zip" (ou autre), ce qui nous donne une mésure de la redondance (compressibilité) des données représentant un graphe.

Voici un exemple: triangulation de Delaunay 2D, avec 100.000 sommets
 8009402 Feb  1 12:53 delaunay100000.off

 3703680 Feb  1 12:53 graphCompressed.txt
 3732505 Feb  1 12:53 graphNotCompressed.txt

 1546521 Feb  1 12:54 graphCompressed.zip
 1691599 Feb  1 12:54 graphNotCompressed.zip

Les choses sont similaires si on considère une triangulation non Delaunay (100.000 points):

 7764400 Feb  1 13:11 triangulation100000.off

 3547338 Feb  1 13:11 graphCompressed.txt
 3496664 Feb  1 13:11 graphNotCompressed.txt

 1442171 Feb  1 13:13 graphCompressed.zip
 1557192 Feb  1 13:13 graphNotCompressed.zip


Ce qui nous qu'il y a du boulot à faire, si on veut bien coder un graphe...
Votre travail au cours de ce TD?
Il vous reste à compléter les classes suivantes:

1. Partitionnement de graphes et séparateurs géométriques (en 2D)

Dans cet exercice on vous demande de compléter la classe Separator_2, qui permet de calculer un partitionnement d'un graphe à l'aide des séparateurs géométriques

L'idée à la base de cet approche est très simple, vue en cours aujourd'hui, et illustrée par la figure ci-dessous.
Le but est de renumeroter les sommets, en effectuant un partitionnement récursif du graphe à l'aide des séparateurs géométriques. Cette décomposition peut se représenter à l'aide dàun arbre de séparation (ici à gauche):
  • les feuilles contiennent des points isolés
  • la racine est le graphe initial G
  • pour tout sommet, ses descendants sont les deux sous-graphes obtenus avec découpage à l'aide dàun séparateur (edge séparateur)

La numéroration des sommets du graphe G est induite directement de l'ordre (préfixe, en profondeur) des noeuds de de l'arbre de séparation.

Si le graphe a les bonnes propriétés esperées (petits séparateurs), alors on aura

  • des sommets proches dans le graphes auront des étiquettes (numéros) proches.

ce qui permet d'obtenir un codage compacte, facile à calculer, et éfficace dans la pratique.
(image de Clément Maria)


Dans cet exercice on vous demande de compléter les classes Separator_2 et Separator, qui permet de calculer un partitionnement d'un graphe 3D à l'aide des séparateurs géométriques

Partitionner les sommets d'un graphe en 2

	/**
     * compute a "geometric" edge separator of a given graph.
     * The cut is computed accordingly to a given random plane.
     * Return the two (disjoint) corresponding sub-graphs, stored in a table.
     */		
    public GeometricGraph[] geometricCut(GeometricGraph_2 g, Line_2 randomLine)


Elle prend un entré un graphe géométrique 2D G et une droite aléatoire L, et renvoie deux nouveaux sous-graphes G1 et G2 séparés par L, dont les sommets constituent une partition des sommets de G.
Remarque (important): les graphes G1 et G2 sont nouveaux, mais ils partagent les sommets avec G... donc pas besoin de créer de nouveaux sommets.
Vous avez tout ce quàil faut pour manipuler les graphes dans la classe GeometricGraph.

Suggestion pour l'instant on ne vas pas traiter les aretes, juste les sommets (pas obligatoire, si vous le souhaitez vous pouvez faire tout ensemble)

Voici le résultat



Décomposer un graphe en deux sous-graphes

Remarque (important): le graphe originale G est ainsi modifié... mais ce n'est pas grave.

Voici le résultat:



Choisir un plan aléatoire et décomposer le graphe

de manière à choisir un plan aléatoire, et effectuer le partitionnement de G, juste en appelant la méthode ci-dessus.

Remarque: il vous faudra peut-etre calculer une Bounding Box, pour l'ensemble des sommets de G (déjà codé dans GeometricGraph_2)

Voici le résultat:

"Construction" de l'arbre de séparation

    // Compute a graph partitioning and return the list of nodes reordered
    public List<GraphNode> computeGraphSequence(GeometricGraph g) {

Le résultat de la fonction doit etre une liste contenant des sommets... ce sont les feuilles de l'abre de séparation, listées en ordre préfixe.

Cette fonction, en faisant appel à la fonction Cut(), doit effectuer le "calcul" de l'arbre de séparation: attention, il n'est pas vraiment nécésaire de construire un véritable arbre.

Il suffit de souvenir que l'ordre préfixe d'un arbre correspond à un parcours un profondeur.
Quelle structure de donnée vaut-il mieux utiliser?


Codage du graphe... avec séparateurs

Maintenant on peut tester avec la fonction
testEncodingFinal();
qui permet de comparer le codage "normal" d'un graphe, avec celui qu'on peut obtenir à l'aide des séparateurs.

Voici un exemple: triangulation de Delaunay 2D, avec 30.000 sommets
-rwxrwxrwx 1 amturing Nessuno  571496 Feb  2 01:12 compactGraphEncoding.txt // avec séparateurs
-rwxrwxrwx 1 amturing Nessuno 1072460 Feb  2 01:12 graphNotCompressed.txt 
-rwxrwxrwx 1 amturing Nessuno 1013849 Feb  2 01:12 normalGraphEncoding.txt // normal, sans séparateurs

-rwxrwxrwx 1 amturing Nessuno  177512 Feb  2 01:13 compactGraphEncoding.zip
-rwxrwxrwx 1 amturing Nessuno  457842 Feb  2 01:13 graphNotCompressed.zip
-rwxrwxrwx 1 amturing Nessuno  413181 Feb  2 01:13 normalGraphEncoding.zip

On voit bien qu'on a reduit la rédondance de manière considérable.
Ce qui nous nous confirme qu'on pouvait faire un effort...

2. Partitionnement de graphes et séparateurs géométriques (en 3D)

Dans cet exercice on vous demande de compléter la classe Separator_3, qui permet de calculer un partitionnement d'un graphe 3D à l'aide des séparateurs géométriques

On va repeter le travail déjà effectué à l'exercice 1: cette fois il faudra modifier la classe Separator_3, comme suit:

    public GeometricGraph[] Cut(GeometricGraph g) {
    	throw new Error("a' completer");

    	// exo: creer un plan aleatoire
    	//Plane_3 randomPlane=new Plane_3();

    	//return geometricCut((GeometricGraph_3)g, randomPlane);
    }

    public GeometricGraph[] geometricCut(GeometricGraph_3 g, Plane_3 plane) {
    	throw new Error("a' completer");
    }

Il ne vous qu'à tester avec la classe CompactGraph: il suffira d'utiliser les fonctions
test1b3D();

testEncodingFinal3D();
de manière à ce que le graphe à coder soit un graphe plongé en 3D.

3. Partitionnement spectrale en 2D et 3D (Facultatif): on utilise les matrices laplaciennes (comme au TD3)

Dans cet exercice on vous demande de modifier les classes Separator_2 et Separator_3, de manière à calculer le partitionnement d'un graphe à l'aide des vecteurs propres de la matrice laplacienne: maintenant il vous faut la librairie Jama.

Comme il est désormais évident, la seule chose à faire est: