Manipulation et visualisation de graphes :
bibliothèques et logiciels

TODO

Table des matières

1. Bibliothèque de gestion de graphes
2. Format de stockage sur disque
3. Algorithmes de positionnement
4. Logiciels de visualisation et manipulation de graphes
5. Liens

1. Bibliothèque de gestion de graphes

Il y a deux grandes méthodes de stucture mémoire de graphe : l'utilisation d'une matrice d'adjacence, ou l'utilisation d'un object par nœud contenant des pointeurs vers les nœuds voisins. La plupart des bibliothèques présentées ici utilisent la seconde méthode, qui permet, en particulier, de parcourir très rapidement les graphes. Sauf indication contraire, ces bibliothèques permettent toutes de gérer efficacement de très grands graphes.

Liste de bibliothèques :

Dans le cas où aucune de ces bibliothèques ne vous convient, choissez celle la plus proche de votre besoin et modifiez la : repartir de zéro est rarement une bonne solution (en particulier, ça signifie de tout redéboguer de zéro).

2. Format de stockage sur disque

Ces formats permettent tous de stocker un ensemble de nœuds et d'arêtes pouvant porter chacun n'importe quel type d'attributs. Tous sont capables de gérer des graphes dirigés et non dirigés, cenpendant seul certains sont capables de gérer des graphes mixtes possèdant à la fois des arêtes dirigiées et des arêtes non dirigées. Un autre point important est la possibilité de regrouper des nœuds pour former des sous graphes.

  • GraphML (graphes dirigés ou non, sous-graphes) : format à base de XML
    <graphml>
      <key id="d1" for="edge" attr.name="weight" attr.type="double"/>
      <graph id="G" edgedefault="undirected">
        <node id="n0"><data key="d1">2.0</data></node>
        <node id="n1">
          <graph id="G1" edgedefault="directed">
            <node id="n2"><data key="d1">1.3</data></node>
            <edge source="n3" target="n2"/>
            <node id="n3">      	
          </graph>
        </node>
        <edge source="n0" target="n2" id="e1" directed="true"/>
        <edge source="n1" target="n3"/>
      </graph>
    </graphml>
  • DOT (graphes soit dirigés soit non-dirigés mais pas mixtes, sous-graphes) : format du logiciel GraphViz.
    graph G {
      e [shape=square]
      subgraph clusterA { a -- b }
      subgraph clusterB { d -- f }
      b -- d [label="hello"]
      e -- clusterB
      clusterC -- clusterB
    }
  • GML (graphes soit dirigés soit non-dirigés mais pas mixtes)
    graph [
        comment "This is a sample graph"
        directed 1
        node [
            id 1
            label "Node 1"
        ]
        node [
            id 2
            thisIsASampleAttribute 43
        ]
        edge [
            source 1
            target 2
            label "Edge from node 1 to node 2"
        ]
    ]
    
  • GDF (graphes dirigés ou non): format du logiciel Guess. Très simple et basé sur un modèle de base de données.
    nodedef> name,x,y,value INT
    "racine",0.0,0.0,17
    "noeud 1",2.0,3.2,4
    "noeud 2",-1.3,1.5,6
    edgedef> node1,node2,directed
    "racine","noeud 1",false
    "racine","noeud 2",true
    
  • et tous les formats spécifiques à certains logiciels (LibSea utilisé par CAIDA, YGF utilisé par yEd, GDL utilisé par aiSee…)
  • 3. Algorithmes de positionnement

    C'est assez bien expliqué sur la page du logiciel yEd.

    4. Logiciels de visualisation et manipulation de graphes

    La plupart de ces outils sont des outils de visualisation de graphes statiques, permettant de définir de nombreux attributs comme la taille, couleur, forme, flèche des nœuds et arêtes, et de choisir parmi un certain nombre d'algorithmes de positionnement.

    Il existe une multitude de logiciels de ce genre, cependant nombreux sont ceux qui sont incapables de traiter de très grands graphes. Je ne présente ici que des logiciels qui sont capables de faire quelque chose de ces très grands graphes (et qui dans tous les cas marchent aussi très bien sur de petits graphes). Les indications entre parenthèses correspondent à l'éditeur, la licence, le langage et les formats supportés :

    Logiciels de visualisation partielle, permettant de naviguer plus facilement dans de très grands graphes :

    5. Liens