Dans le cadre de mes travaux de thèse, j'implémente une méthode d'annotation d'image basée sur des graphes et un modèle markovien.
J'ai codé un premier prototype en Java, je construis mon graphe avec la bibliothèque Jung, et obtiens ma matrice d'adjacence ainsi:
SparseDoubleMatrix2D matrix = GraphMatrixOperations.graphToSparseMatrix(g);
où
SparseDoubleMatrix2D est un objet de la bibliothèque Colt du CERN.
Cependant:
RWR.runRWR: begin.
RWR.runRWR: loading the graph.
RWR.runRWR: loading the LIRE index associated to the graph.
RWR.runRWR: loading the query image in a BufferedImage.
RWR.runRWR: search by similarity in the LIRE index.
RWR.runRWR: we search the vertex which is the NN in the graph.
RWR.runRWR: retrieve the indice of the image query for building the restart vector.
RWR.runRWR: preparing the RWR computing.
RWR.runRWR: the graph contains 49197 nodes, 144484 edges.
Exception in thread "main" java.lang.IllegalArgumentException: matrix too large
at cern.colt.matrix.impl.AbstractMatrix2D.setUp(Unknown Source)
at cern.colt.matrix.impl.AbstractMatrix2D.setUp(Unknown Source)
at cern.colt.matrix.impl.SparseDoubleMatrix2D.<init>(Unknown Source)
at cern.colt.matrix.impl.SparseDoubleMatrix2D.<init>(Unknown Source)
at edu.uci.ics.jung.algorithms.GraphMatrixOperations.graphToSparseMatrix(GraphMatrixOperations.java:244)
at edu.uci.ics.jung.algorithms.GraphMatrixOperations.graphToSparseMatrix(GraphMatrixOperations.java:223)
at net.trevize.cbiaproto.dataformer.RWR.runRWR(RWR.java:155)
at net.trevize.cbiaproto.dataformer.RWR.main(RWR.java:382)
Ce qui me parait assez étrange, le graphe fait environ 50.000 nœuds mais la matrice d'adjacence est très creuse, et la matrice demandée est sparse...
Apparemment ce n'est pas un problème de mémoire.
A propos de Colt:
http://www.semiophore.net/v4/index.php?option=com_myblog&show=Extension-pour-librairie-Colt.html&Itemid=1&lang=en.
Dans le cadre de mes travaux de thèse, je construis des graphes à l'aide de la bibliothèque Java
Jung (la 1.7 cependant, pas la 2.x qui inclus les generics et encore en beta), et qui utilise
Colt pour les opérations sur les matrices.
Pour les formats de stockage des graphes, il existe de nombreux standards:
- dot graphviz
- GML, Graph Modelling Language, non XML
- GML-XML
- GraphML
Jung ne permet de sérialiser les graphes que dans le format
GraphML, donc pas de
Graphviz dot, c'est assez embêtant car les applications de visualisation de graphe prennent en entrée du Graphviz dot ou du GML, et assez rarement du GraphML.
C'est un point de vue personnel, mais le GraphML est vraiment un format de stockage pour les graphes au sens type de donnée abstrait, comparé à Graphviz dot ou GML qui attaquent aussi directement le rendu du graphe. De plus, les détracteurs du GraphML peuvent dire que c'est du
XML donc verbeux et coûteux en parsing mais GML n'est pas moins verbeux...
Cependant, il est intéressant de convertir du GraphML en Graphviz dot, par exemple pour illustrer un article car il existe de nombreuses macros latex pour importer du Graphviz dot.
Pour la conversion de standard, par exemple convertir de GraphML vers Graphviz dot
- avec graph-easy, un script perl, cependant j'ai un problème avec graph-easy, il semble qu'il n'aime pas les GraphML en input.
Il imprime sur la sortie d'erreur mon fichier GraphML suivi de:
not recognized by Graph::Easy::Parser::Graphviz at /usr/local/bin/graph-easy line 87
nicolas@trantor:~/Desktop$ graph-easy --from graphml graph.xml graph.dot
Unknown input format 'graphml' at /usr/local/bin/graph-easy line 332.
- graph-tool: Très long à compiler, comme indiqué sur la page d'accueil du projet.
Si un
prefix est précisé dans le configure, il faut modifier le script python graph-tool,
car il ne trouve pas la library, alors ajouter dans le script:
sys.path.append("../lib/python2.5/site-packages")
Visualisation
- avec GraphViz:
dot -Tps graph.dot -o graph.ps
Visualisation interactive
- tulip, très intéressant celui là.
- zgrviewer: voir http://zvtm.sourceforge.net/zgrviewer.html#download (mais bug sous linux, probablement à cause de la JVM et le forwarding sous X, j'avais vu une exception là dessus, mais j'arrive pas à la reproduire).
Mais en le recompilant, ça fonctionne bien http://zvtm.sourceforge.net/zgrviewer/doc/build.html.
Le problème vient probablement du bug dans Java 1.6 pour Linux à propos de Xlib/XCB qui a été corrigé depuis.
Voir aussi
- gephi
- InfoVis cyberinfrastructure, ivc (s'appuie très largement sur Jung, je pense que ce n'est pas adapté aux large graphs).
- InfoVis Toolkit, ivtk (INRIA futurs, LRI, IN-SITU project)
- Walrus
- Pajek
Remarques
- visualiser des Graphviz dot avec une application web, http://ashitani.jp/gv/.
- il existe un plugin Eclipse pour écrire des Graphviz dot, Graphviz Eclipse Plugin. Cependant la présence de ce plugin fait que les icônes de certains types d'images, dans l'arborescence d'un projet, sont remplacées par l'icône "fichier texte" (notamment les jpg et png)... un bug ?
