Force-based layout
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Cet article est une ébauche concernant la géométrie et l’informatique.
Les algorithmes de dessin basé sur les forces (Force-based ou Force-directed algorithms) permettent de positionner les nœuds d'un graphe pour faciliter sa visualisation en utilisant un système de force appliqués entre les nœuds et les arcs.
Méthode
[modifier | modifier le code]L'algorithme peut être décrit comme une analogie physique des composants du graphe :
- les nœuds sont représentés par des particules de même charge ;
- les arcs sont assimilables à des ressorts.
À chaque passe, l'algorithme fait la somme des forces appliquées sur chacun des nœuds puis les déplace suivant des règles de physique classique jusqu'à trouver un état stable.
Avantages et inconvénients
[modifier | modifier le code]Avantages :
- interactivité, les nœuds pouvant être replacés à la volée pendant le calcul, être ajoutés ou supprimés.
Inconvénients :
- ce sont des algorithmes souvent coûteux en puissance de calcul ;
- ces algorithmes souffrent pour la plupart de terminer dans un état qui n'est qu'un minimum local du problème d'optimisation à l'origine de la modélisation physique, et non dans l'état minimum absolu.
Références
[modifier | modifier le code]- ↑ Martin Grandjean, Introduction à la visualisation de données : l’analyse de réseau en histoire, université de Lausanne, (lire en ligne [PDF]).
