Accueil🇫🇷Chercher

Force-based layout

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

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

  • InteractivitĂ©: les nĹ“uds peuvent ĂŞ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.

Voir aussi

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.