Fonctions et limitations de l'agencement hiérarchique (HL)

Fonctions

  • Organise les noeuds sans chevauchement dans les niveaux horizontal ou vertical.
  • Dispose le graphe de sorte que la majorité des liens sont courts et se déroulent de manière uniforme dans la même direction (de gauche à droite, du haut en bas, et ainsi de suite).
  • Réduit le nombre d'intersections de liens. La plupart du temps, produit des tracés sans intersections ou avec juste un petit nombre d'intersections.
  • Produit souvent des tracés équilibrés qui soulignent les symétries dans le graphe.
  • Prend en charge les self-link (c'est-à-dire, les liens avec le même noeud d'origine et de destination), les multiple links entre la même paire de noeuds, et les cycles.
  • Algorithme efficace et évolutif. Produit relativement vite un bel agencement pour la plupart des graphes rares et moyennement denses, même si le nombre de noeuds est très élevé.
  • Propose plusieurs options d'alignement et de décalage.
  • Prend en charge les spécifications de port lorsque les liens se connectent aux noeuds. Permet de spécifier le côté du noeud (haut, bas, gauche, droite) auquel un lien peut être connecté ou d'indiquer la position de port relative qui doit être utilisée pour la connexion.
  • Prend en charge les contraintes d'agencement. Permet de spécifier les contraintes positionnelles relatives, par exemple, lorsqu'un un noeud se trouve au-dessus d'un autre noeud ou est séparé d'un autre noeud.
  • Mode incrémentiel et non incrémentiel. En mode incrémentiel, la position précédente des noeuds est prise en compte. Les noeuds sont positionnés sans modifier leur classement relatif de sorte que l'agencement est stable lors des changements incrémentiels du graphe.
  • Le temps de calcul dépend du nombre de noeuds, du nombre de niveaux et du nombre de liens qui s'entrecroisent dans plusieurs niveaux. La plupart du temps, les liens sont placés entre des niveaux adjacents, ce qui permet de réduire le temps de calcul.

Limitations

  • L'algorithme tente de minimiser le nombre de link crossing (il s'agit généralement d'un problème NP-complete). Il est mathématiquement impossible de résoudre ce problème si rapidement quelle que soit la taille de graphe. Par conséquent, l'algorithme utilise un heuristique rapide qui obtient un bon agencement, mais pas toujours avec le nombre minimum théorique d'intersections de liens.
  • L'algorithme essaie de placer les noeuds de sorte que tous les liens pointent de manière uniforme dans la même direction. Il est impossible de placer des cycles de liens de cette manière. Pour cette raison, il produit parfois un graphe dans lequel un petit nombre de liens sont inversés et pointent dans la direction opposée. L'algorithme essaie de minimiser le nombre de liens inversés (ce qui, une fois de plus, est un problème NP-complet). Par conséquent, l'algorithme utilise un heuristique rapide, ce qui se traduit par un bon agencement, mais pas toujours avec le nombre minimum théorique de liens inversés.
  • Le temps de calcul requis pour obtenir un tracé approprié dépend le plus souvent du nombre de coudes dans les liens. Etant que l'algorithme place un coude chaque fois qu'un lien croise un niveau, le nombre de coudes peut croître relativement vite si l'agencement requiert un grand nombre de liens longs qui s'étendent sur plusieurs niveaux. Par conséquent, le processus d'agencement peut être très long pour les graphes de grande densité (le nombre de liens est relativement élevé comparé au nombre de noeuds) ou pour les graphes qui nécessitent un grand nombre de niveaux de noeuds.