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.