Optimisations des agencements de graphe

L'agencement de graphe est généralement une tâche complexe qui utilise souvent une méthode heuristique pour résoudre des problèmes NP-complets (problèmes ne pouvant pas être résolus facilement par des calculs). Les différentes méthodes heuristiques sont plus ou moins rapides. Les graphes de petite taille n'ont généralement pas besoin d'optimisations des performance. Certains algorithmes d'agencement son conçus pour les graphes de taille moyenne, mais seuls quelques algorithmes sont disponibles pour les graphes de grande taille.

Utilisez un agencement uniquement lorsque c'est nécessaire

L'algorithme d'agencement de graphe représente généralement la partie la plus complexe et la plus lente de votre application. Concevez vos applications pour utiliser l'agencement de graphe avec parcimonie et uniquement lorsque cela s'avère nécessaire. Par exemple, vous pouvez inclure un bouton qui déclenche l'agencement pour que ce dernier n'ait pas à s'exécuter continuellement lors de toutes les interactions.

Utilisez des liens orthogonaux sans agencement de liens

Si votre application nécessite des formes de lien orthogonal, vous serez tenté d'utiliser un mode d'agencement automatique (voir setAutomaticLinkLayout). Cependant, cela entraîne le déclenchement de l'agencement chaque fois qu'un lien est déplacé. Si vous avez beaucoup de liens, un agencement de liens entièrement automatique peut être lent. Une autre méthode consiste à utiliser le type de lien de forme orthogonale (voir setShapeType). Ce type garantit que la forme d'un lien reste orthogonale sans analyser tous les liens afin de réduire les croisements et les chevauchements de lien. Il peut donc s'avérer plus efficace que l'exécution de l'agencement de liens en mode automatique.
Pour activer le type de forme orthogonale sur un lien, appelez l'une des méthodes suivantes :
  • link.setShapeType(ibm_ilog.diagram.LinkShapeType.Orthogonal);
  • link.setShapeType(ibm_ilog.diagram.LinkShapeType.OrthogonalEditable);

Utilisez un agencement approprié pour la taille du graphe

Les différents algorithmes d'agencement de graphe prennent en charge des tailles différentes.
  • Les agencements arborescents et les agencements en grille peuvent traiter les graphes de grande taille.
  • L'agencement hiérarchique peut convenir à des graphes de taille moyenne qui ne comportent pas trop de liens.
  • L'agencement basé sur les forces (ForceDirected) est l'algorithme le plus lent et n'est pas adapté aux graphes de grande taille.

N'affichez pas tous les liens

Si vous avez un graphe de grande taille avec des liens, il est préférable d'afficher uniquement un arbre de type Spanning Tree du graphe et de masquer les autres liens. L'arbre Spanning Tree peut être agencé avec l'agencement arborescent.
Concevez votre application pour utiliser des interactions qui permettent à l'utilisateur d'être conscient des liens masqués. Par exemple, la sélection d'un noeud peut mettre en évidence tous les noeuds accessibles à partir de ce noeud par le biais de liens masqués ou visibles. Cette solution est plus ergonomique que l'affichage de tous les liens en même temps. L'oeil de l'utilisateur ne lui permet pas de suivre des liens si trop de liens sont affichés simultanément.

Regroupez les éléments en cluster dans des sous-graphes et réduisez-les

Parfois, les graphes peuvent avoir des informations de cluster significatives. Par exemple, un graphe de personnes divisés en clusters selon la nationalité ou des familles. Chaque cluster peut être représenté sous la forme d'un sous-graphe imbriqué (Subgraph) qui peut être réduit ou développé.
Les sous-graphes bénéficient d'un agencement plus rapide lorsqu'ils sont réduits car il n'est pas nécessaire d'agencer le contenu interne des clusters. Le diagramme devient également plus compréhensible si seuls les détails pertinents sont affichés tandis que les sous-graphes moins intéressants sont réduits. D'autre part, si tous les sous-graphes sont développés, l'agencement peut être ralenti lorsque la profondeur d'imbrication est importante. Lorsqu'une application utilise des graphes de grande taille, un regroupement en sous-graphes imbriqués conçu avec soin peut contribuer à améliorer la convivialité.

Rapidité des algorithmes d'agencement de graphe

La rapidité des algorithmes d'agencement de graphe dépend du type de graphe et des paramètres d'agencement. Certains agencements sont lents pour des types de graphe spécifiques.

Agencement arborescent

L'agencement arborescent est rapide et peut traiter de très grands graphes dans la mesure où vous n'utilisez pas de modes de renversement automatiques.
  • Les modes d'agencement FREE et LEVEL sont les plus rapides.
  • Les modes d'agencement radiaux sont légèrement plus lents, mais suffisamment rapides pour les graphes de grande taille.
  • Les modes d'agencement renversés sont lents et sont plus efficaces pour les graphes de petite taille uniquement.
Pour plus de détails, voir Agencement arborescent (Tree layout - TL).

Agencement hiérarchique

La rapidité de l'agencement hiérarchique dépend de la densité (rapport entre le nombre de liens et le nombres de noeuds) du graphe. L'agencement hiérarchique peut traiter des graphes de grande taille avec peu de liens, mais peut être lent pour des graphes de plus petite taille comportant beaucoup de liens.
La rapidité et la qualité de l'agencement hiérarchique dépend également du nombre de contraintes. Plus le nombre de contraintes est faible, plus l'agencement est libre dans le placement des noeuds et plus il est rapide. En particulier, évitez les conflits de contrainte car la détection de ces conflits peut s'avérer lente.

Agencement en grille

L'agencement en grille est rapide et peut traiter des graphes de grande taille. Cependant, dans le mode d'agencement TILE_TO_MATRIX, la rapidité dépend de la taille de maillage de la grille (distance entre les lignes de la grille). Plus la taille de maillage de la grille est réduite, plus l'agencement est lent. Dans d'autres modes d'agencement, la taille de maillage de la grille n'a pas d'influence sur les performances.
Pour plus de détails, voir Agencement de grille (Grid Layout - GL).

Agencement avec liens courts et longs

La rapidité de l'agencement de liens dépend du nombre de liens. Les agencements de liens conviennent aux graphes de petite taille et de taille moyenne. Si le graphe comprend beaucoup de liens, voir Utilisez des liens orthogonaux sans agencement de liens.
Pour l'agencement avec liens longs, la rapidité dépend de la taille de maillage de la grille (distance entre les lignes de la grille). Plus la taille de maillage de la grille est réduite, plus l'agencement est lent. Si possible, évitez le mode de recherche exhaustive (LongLinkLayout.setExhaustiveSearching), car il est très lent.
Pour plus de détails, voir Agencement de liens (Link Layout - LL).

Agencement basé sur les forces

Cet algorithme fournit trois modes facultatifs : incrémentiel, non incrémentiel et multiniveaux rapide. Ce dernier mode est plus rapide pour les graphes de taille moyenne et de grande taille.
Pour plus de détails sur ces modes, reportez-vous à Mode d'agencement et consultez les informations sur le mode d'agencement basé sur les forces.

Agencement côté serveur

Pour les graphes complexes de grande taille, vous pouvez améliorer les performances en utilisant un agencement côté serveur. L'agencement côté serveur envoie toutes les données du graphe au serveur et effectue l'agencement de graphe sur le serveur. Il peut s'avérer plus rapide selon :
  1. La vitesse du moteur JavaScript de votre navigateur.
  2. La vitesse de la connexion réseau entre le client et le serveur.

Interfaces de personnalisation d'agencement

Plusieurs algorithmes d'agencement prennent en charge des interfaces de personnalisation, telles que INodeBoxProvider, INodeSideFilter ou ILinkConnectionBoxProvider. Lorsque vous utilisez ces interfaces, l'algorithme d'agencement passe directement dans votre code. Faites attention lorsque vous implémentez ces interfaces, car elles peuvent entraîner une baisse des performances de l'algorithme d'agencement.