Force-based layout
Un article de Wikipédia, l'encyclopédie libre.
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.
Sommaire |
Méthode[modifier]
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[modifier]
- Interactivité: les nœuds peuvent être replacés à la volée pendant le calcul.
Inconvénients[modifier]
- Ce sont des algorithmes souvent coûteux en puissance de calcul.
- Ces algorithmes souffrent pour le plupart de ne terminer que dans un état qui est un minimum local du problème d'optimisation à l'origine de la modélisation physique.
