Concept d'agencement de graphe

Un graphe est une structure de données qui représente un ensemble d'entités, appelées noeuds, connectés par un ensemble de liens. On parle également de vertex pour désigner un noeud. On parle également de bord ou de connexion pour désigner un lien. Dans des applications pratiques, les graphes sont fréquemment utilisés pour modéliser un très grand nombre d'éléments variés : des réseaux informatiques, des structures de programme logiciel, des diagrammes de gestion de projets, etc. Les graphes sont des modèles très puissants car ils permettent aux applications de tirer parti des résultats de la recherche sur la théorie des graphes. Par exemple, il existe des méthodes efficaces pour rechercher le chemin le plus court entre deux noeuds, le chemin le moins onéreux, etc.

Agencement d'un graphe

L'agencement de graphe est utilisé dans les interfaces graphiques d'applications qui doivent afficher des modèles de graphe. Agencer un graphe revient à le tracer de manière à en produire une représentation lisible appropriée. Cela implique essentiellement de déterminer l'emplacement des noeuds et la forme des liens. Pour certaines applications, il se peut que l'emplacement des noeuds soit déjà connu (par exemple, d'après les positions géographiques des noeuds). Pour d'autres applications, l'emplacement n'est pas connu (graphe "logique" pur) ou l'emplacement connu, s'il est utilisé, peut produire une représentation illisible du graphe. Dans ces cas, l'emplacement des noeuds doit être calculé.
Qu'entend-on par "approprié" pour qualifier le tracé d'un graphe ? Dans des applications pratiques, le tracé de graphe doit souvent respecter certains critères de qualité. Ces critères peuvent varier en fonction du champ d'application ou d'une norme de représentation donnée. Il est souvent difficile de dire à quoi ressemble un agencement approprié. Chaque utilisateur peut avoir ses propres critères subjectifs pour qualifier un agencement d'approprié. Il existe toutefois une finalité commune à tous les critères et à toutes les normes : le tracé doit être facile à comprendre et fournir une navigation aisée dans la structure complexe du graphe.

Qu'est-ce qu'un agencement approprié ?

De nombreuses classes d'algorithmes d'agencement de graphe ont été développées pour prendre en charge les divers besoins de différentes applications. Un algorithme d'agencement tient compte d'un ou de plusieurs critères de qualité, en fonction du type de graphe et des fonctions de l'algorithme, lors de l'agencement d'un graphe.
Les critères les plus courants sont les suivants :
  • Réduction du nombre de link crossing
  • Réduction de la zone totale du tracé
  • Réduction du nombre de courbes (dans des tracés orthogonaux)
  • Réduction de l'angle le plus petit formé par des liens d'incident consécutifs
  • Réduction de l'affichage des symétries
Comment un algorithme d'agencement peut-il satisfaire chacun de ces critères de qualité et chacune de ces normes de représentation ? Si vous examinez chacun des critères individuellement, vous constaterez que certains sont relativement faciles à satisfaire, au moins pour certaines classes de graphes. Pour d'autres classes, il peut s'avérer difficile de produire un tracé qui soit conforme aux critères. Par exemple, il est assez facile de réduire le nombre d'intersections de liens pour des arborescences (c'est-à-dire pour des graphes dépourvus de cycles). Pour les graphes généraux, réduire le nombre d'intersections de liens est un problème mathématique NP-complete (avec tous les algorithmes connus, le temps nécessaire pour exécuter l'agencement augmente très vite à mesure que la taille du graphe se développe).
Si vous souhaitez satisfaire plusieurs critères en même temps, il n'existe probablement pas de solution optimale pour chacun d'eux, car bon nombre d'entre eux sont mutuellement contradictoires. Des substitutions dont l'exécution prend du temps peuvent s'avérer nécessaires. En outre, le fait d'affecter des poids à chaque critère n'est pas une tâche anodine. L'optimisation multicritère est, dans la plupart des cas, une opération trop complexe à implémenter et beaucoup trop longue. Pour toutes ces raisons, les algorithmes d'agencement sont souvent basés sur des méthodes heuristiques et sont susceptibles de fournir des solutions loin d'être optimales pour un ou plusieurs critères. Heureusement, dans la pratique, les algorithmes d'agencement fournissent encore très souvent des tracés relativement lisibles.

Méthodes d'utilisation des algorithmes

Les algorithmes d'agencement peuvent être employés de différentes façons dans les diverses applications où ils sont utilisés. Les utilisations les plus courantes d'un algorithme sont les suivantes :
  • Hormis peut-être la sélection de l'algorithme d'agencement à utiliser, aucune des actions de l'algorithme d'agencement ne nécessite une intervention de l'utilisateur. Parfois, un ensemble ou des règles peuvent être codés afin de permettre la sélection automatique (et dynamique) de l'algorithme d'agencement le plus approprié pour le type de graphe donné à agencer.
  • L'utilisateur de l'application est libre d'améliorer manuellement le résultat de la procédure d'agencement automatique. Dans certains cas, cet utilisateur peut déplacer et "fixer" les noeuds aux endroits de son choix et relancer l'agencement. Dans d'autres cas, une partie du graphe est automatiquement définie en "lecture seule" et l'utilisateur peut modifier le reste de l'agencement.
  • Agencement sur des bases entièrement nouvelles
    L'algorithme d'agencement est complètement refait ("sur des bases entièrement nouvelles") chaque fois que le graphe est modifié.
  • Agencement incrémentiel
    Lorsque l'algorithme d'agencement est effectué une seconde fois sur un graphe modifié, il tente de préserver le plus possible la stabilité de l'agencement. L'agencement n'est pas relancé sur des bases entièrement nouvelles. L'algorithme d'agencement tente également d'économiser du temps UC en utilisant l'agencement précédent comme solution initiale. Certains algorithmes et styles d'agencement sont incrémentiels par nature. Pour d'autres, l'agencement incrémentiel peut être impossible à réaliser.