Fonctions et limites de l'agencement arborescent

Fonctions

  • Tient compte de la taille des noeuds de manière à éviter les chevauchements.
  • Les liens sont éventuellement remodelés sous une forme orthogonale (segments de ligne horizontaux et verticaux alternatifs).
  • Offre divers modes d'agencement : libre, en niveaux, radial et radial alternatif, en ballon et renversé de façon automatique.
    • En mode d'agencement libre, organise les noeuds enfants de chaque noeud, en commençant de façon récursive à partir de la racine, de sorte que tous les liens s'écoulent de manière uniforme dans la même direction.
    • En mode d'agencement en niveaux, partitionne les noeuds en niveaux et organise ceux-ci horizontalement ou verticalement.
    • En mode d'agencement radial, partitionne les noeuds en niveaux et organise ceux-ci en cercles ou en points de suspension autour de la racine.
    • En mode d'agencement en ballon, les noeuds enfants sont organisés en cercles autour du noeud parent, de sorte que chaque sous-arborescence forme un ballon.
    • En mode renversé, les noeuds sont organisés d'une façon similaire au mode d'agencement libre, mais les noeuds enfants sont renversés automatiquement de sorte que la taille de l'agencement corresponde mieux au rapport hauteur/largeur.
  • Fournit plusieurs options d'alignement et de décalage.
  • Vous permet de spécifier des noeuds qui doivent être des voisins directs.
  • Fournit des modes incrémentiel et non incrémentiel. Le mode incrémentiel tient compte de la précédente position des noeuds et positionne les noeuds sans modifier leur ordre relatif dans l'arborescence, de sorte que l'agencement soit stable lors de modifications incrémentielles sur le graphe.
  • Algorithme efficace et évolutif. Génère un agencement attrayant très rapidement même si le nombre de noeuds est élevé.

Limites

  • Si le paramètre orthogonal n'est pas spécifié comme style de lien (voirStyle de lien (TL)), certains liens peuvent, en de rares cas, chevaucher des noeuds selon la taille des noeuds, des paramètres d'alignement et des paramètres de décalage.
  • L'algorithme d'agencement commence par déterminer une arborescence fractionnée du graphe. Si le graphe n'est pas une arborescence pure, certains liens ne sont pas inclus dans l'arborescence fractionnée. Ces liens sont ignorés. Par conséquent, ils peuvent croiser d'autres liens ou chevaucher des noeuds dans l'agencement final.
  • Pour assurer la stabilité en mode incrémentiel, l'algorithme tente de préserver l'ordre relatif des noeuds enfants de chaque noeud. Il utilise une méthode heuristique pour calculer l'ordre relatif à partir des positions précédentes des noeuds. La méthode heuristique peut échouer si des noeuds enfants chevauchent leurs anciennes positions ou ne sont pas alignés horizontalement ou verticalement.
  • Malgré la conservation de l'ordre relatif des noeuds enfants, il peut arriver que l'agencement ne soit pas parfaitement stable dans des agencements radiaux incrémentiels. Les agencements suivants peuvent faire pivoter les noeuds autour de la racine, bien que l'ordre circulaire relatif des noeuds au sein de leurs niveaux circulaires soit conservé.
  • Malgré la conservation de l'ordre relatif des noeuds enfants, il peut arriver que l'agencement ne soit pas parfaitement stable dans des agencements en ballon incrémentiels. Les agencements suivants peuvent faire pivoter les noeuds enfants autour du parent, bien que l'ordre circulaire relatif des noeuds soit conservé.
  • Les modes d'agencement renversé exécutent plusieurs agencements d'essai avec différentes options d'alignement renversé, en fonction de diverses méthodes heuristiques. Parmi ces agencements d'essai, l'algorithme choisit celui qui correspond le mieux au rapport hauteur/largeur. Il peut ne pas s'agir de l'agencement optimal pour le rapport hauteur/largeur, mais cet agencement est le plus adapté parmi les agencements d'essai. Le calcul de l'agencement qui convient absolument le mieux n'est pas une opération réalisable ; il s'agit généralement d'un problème NP-complet.