Graphes

04/11/2005

Projets: graph, aims, cartobase, pyaims, [sigraph]

Les exemples présentés sont compilables avec build-config et utilisables: ils sont dans le projet perforce documents/main/coursGraphes-1005/examples/graphex-main

Utilité

en quoi c'est vachement générique: on peut mettre tout et n'importe quoi dedans, de façon "semi-structurée", sans qu'on ait à vraiment savoir ce qu'il y a dedans depuis les couches logicielles "génériques".

ça aggrège un ensemble d'objets qu'on n'a pas à charger/manipuler/sauver un par un (par ex. on le charge dans anatomist en tant qu'un seul objet)

ça sert à tout: ROIs, clusters, sillons, gyri, fibres, modèles de reconnaissance, primalsketches, modèles du monde...

Formats de fichiers

fichier .arg [/ python-minf-like / XML], répertoire .data

objets dans .data: objets Aims, sous forme "compacte" (global) ou "éclatée" (local)

Le format .arg actuel a des limites (ou des garde-fou) dans sa généricité: la syntaxe, donnée par des fichiers externes.

Pre-requis: librairie cartobase

Les compteurs de référence: rc_ptr<T>

C'est comme des pointeurs: ça s'utilise pareil:

#include <cartobase/smart/rcptr.h>

{
  rc_ptr<int>  rc1( new int );
  rc_ptr<int>  rc2 = rc1;
  int          a = *rc1 + *rc2;
}

Les compteurs de référence se partagent l'appartenance d'un objet et le détruisent quand il n'y en a plus besoin:
on ne doit jamais faire de delete sur l'objet pointé: ça se fait tout seul.

Les objets génériques

GenericObject est la classe de base pour tous les objets graphe, noeuds et relation.

Un objet générique particulier super-courant: le dictionnaire: il contient un Dictionary (qui est un typedef sur map<string,Object>), ou un PropertySet qui est un truc maison équivalent à la base (mais avec d'autres trucs en plus).

Fonctions génériques (Interface):

  • getProperty
  • setProperty
  • size
  • getScalar
  • getString
  • fonction "array"
  • itération sur les propriétés / sous-objets
  • Object est un compteur de référence sur un GenericObject: on utilise surtout son opérateur ->.

    Clases principales:

  • Graph
  • Vertex
  • Edge
  • Reader<Graph>
  • Writer<Graph>
  • RoiIterator et dérivées
  • MaskIterator
  • Manipulation courante

    Lecture

    Ne pas utiliser les classes bas-niveau dans la lib graph (GraphReader / GraphParser / GraphWriter)

    Utiliser les IO génériques d'AIMS:

    #include <aims/io/reader.h>
    #include <graph/graph/graph.h>
    #include <iostream>
    
    using namespace aims;
    using namespace std;
    
    int main( int, char** )
    {
      Reader<Graph> reader( "filename.arg" );
      Graph         graph;
      try
      {
        reader.read( graph );
      }
      catch( exception & e )
      {
        cerr << e.what() << endl;
      }
    }

    itération sur les noeuds

      Graph::iterator i, e = graph.end();
      Vertex *v;
      for( i=graph.begin(); i!=e; ++i )
      {
        v = *i;
        // do something with v
      }

    Voir aussi l'exemple 1

    itération sur les relations

    à travers les noeuds:

      Graph::iterator i, e = graph.end();
      Vertex::iterator ie, ee;
      Vertex *v;
      Edge   *edge;
      for( i=graph.begin(); i!=e; ++i )
      {
        v = *i;
        for( ie=v->begin(), ee=v->end(); ie!=ee; ++ie )
        {
          edge = *ie;
          // do something with edge
        }
      }

    illustré aussi dans l'exemple 1

    itération sur des ROI

    Ça se fait en utilisant RoiIteratorOf<Graph> et MaskIterator, des itérateurs "simplifiés" pour les ROIs contenant des buckets.

    Apparemment MaskIterator ne fonctionne pas encore sur des graphes sous forme de volumes de labels.

    Par contre, RoiIteratorOf< AimsData<T> > fonctionne sur des volumes. Il manque un petit lien entre les deux...

    démonstration dans l'exemple 2

    accès aux objets Aims (maillages, buckets...) dans les graphes

    classe GraphManip et structures GraphElementTable, GraphElementCode

    quand on sait ce qu'on y cherche: exemple 3

    mode exhaustif: exemple 4

    représentation interne: locale ou globale (cf fichiers dans .data)

    locale: 1 fichier par objet

    globale: 1 fichier pour tous les objets de même "identifiant", concaténés en utilisant la dimension temporelle

    illustré dans l'exemple 4 aussi.

    représentation interne/externe: buckets ou volumes

    Buckets: un bucket par noeud (ou relation), représentation globale ou locale

    Volumes: un volume de labels stocké dans le graphe, et un indice dans chaque noeud/relation

    lecture partielle / écriture

    On utilise le 3ème paramètre (optionnel) de Reader::read() pour dire si on veut lire les objets AIMS dans les graphes, et lesquels:

      Reader<Graph> reader( "filename.arg" );
      Graph graph;
      reader.read( graph, 0, -1 ); // lit tout (noeuds + relations)
      reader.read( graph, 0, 0 ); // ne lit rien
      reader.read( graph, 0, 1 ); // lit les objets dans les noeuds
    
      // ou avec les options de lectures plus génériques (système plus moderne):
      Reader<Graph> reader( "filename.arg" );
      Graph graph;
      Object options( new Dictionary );
      options->setProperty( "subobjectsfilter", -1 ); // lit tout, 0: rien, 1: noeuds
      reader.setOptions( options );
      reader.read( graph );

    Écriture: maintenant tous les objets manquants (pas lus) sont lus avant que le graphe soit ré-écrit, de manière à ce qu'il ne manque rien.

    #include <aims/io/writer.h>
      // ...
      Writer<Graph> writer( "filename.arg" );
      writer.write( graph );
    

    Note: quand on réécrit un graphe dans son directory d'origine, mais sous un autre nom, le comportement par défaut est de réutiliser le même répertoire .data (par mesure d'économie). C'est peut-être une mauvaise idée...
    Pour éviter ça, mettre "*" dans la propriété "filename_base" du graphe.

    Graphes spécialisés (sigraph)

    sillons: FGraph, modèles: MGraph, FRGraph, primal sketches...

    Pour lire un graphe spécialisé, normalement il suffit d'utiliser les Reader en mode "factory", qui renvoient l'objet lu plutôt que d'en remplir un existant:

      Reader<Graph> reader( "filename.arg" );
      Graph *graph = reader.read();
      // graph can be a derived graph, like FGraph or FRGraph.

    Il est aussi possible de forcer le type de graphe et d'utiliser l'autre forme de Reader:

      Reader<Graph> reader( "filename.arg" );
      FGraph graph;
      reader.read( graph );

    Autre utilisation spécialisée: les bundles

    Les "bundles" (faisceaux de fibres) sont stockés sur disque en format (.bundles, .bundlesdata). Ils n'ont pas de structure de donnée propre en mémoire: ce format est fait pour être lu et réécrit à la volée (classes BundleProducer, BundleListener et dérivées).

    Ceci dit, ils peuvent aussi être lus sous forme de graphe: c'est ce que fait anatomuist. En principe, Reader<Graph> sait lire des .bundles. On trouve dans les noeuds des graphes de bundles des courbes ou des maillages (maillages de segments ou de triangles).

    En python: pyaims

    exemple dans pyaims/src/examples/graph_test.py

    Les RoiIterator / MaskIterator n'ont pas encore été exportés en python.
    GraphManip non plus.

    Manipulation dans Anatomist

    charger un graphe

    nomenclatures

    visu maillages / buckets

    labels

    modèles, recuit simulé

    Futures évolutions, prévues, rêvées, en plan...

  • ROI / DOI: lien entre ROIs et des "textures" de données
  • Manipulations plus simples et transparentes pour les objets AIMS dans les graphes (avec des sur-couches dans le style RoiIterator / MaskIterator
  • Support complet des formats XML et minf
  • Réunion des concepts de graphe et de .minf
  • Prise en compte transparente des référentiels et transformations
  • ... ... ... ...