Optimisation de la disposition des graphes en C#

Question

J'ai une liste d'objets que j'ai besoin d'organiser comme un graphique esthétique. Mon approche actuelle implique IronPython et un algorithme génétique, mais cela prend trop de temps. J'ai lu sur Graphviz, QuickGraph et Graphique #, mais je n'ai pas besoin de la partie de visualisation - J'ai déjà une application qui affichera les nœuds donnés les coordonnées x/y. On m'a dit que l'algorithme de Sugiyama et la famille d'algorithmes basés sur la force tendent à produire des graphiques agréables, mais je ne peux pas trouver une bibliothèque .NET qui produira les coordonnées à la place de l'image sans un code source assez sévère le piratage.

Quelqu'un peut-il recommander des bibliothèques, des algorithmes ou autres?

Answer 1

Il y a un certain nombre d'options, avec divers avantages et les inconvénients - vous pouvez passer au crible this qui est une liste de logiciels qui fait, plus ou moins, ce que vous cherchez. Fondamentalement, il ne semble pas y avoir une implémentation C# pure et gratuite qui soit destinée à être utilisée dans la capacité de la bibliothèque du moteur de mise en page. La chose la plus proche semble être MSAGL, qui est downloadable if you're on MSDN, mais sinon c'est assez cher.

La distinction entre Graph# et QuickGraph est que cette dernière fournit des primitives de parcours et de manipulation de graphe mais ne fournit aucun algorithme de disposition. Le graphique # a toute la source disponible, et d'après ce que j'ai (brièvement) regardé, il y a une séparation nette entre le moteur de mise en page et l'implémentation du dessin.

Graphviz est écrit en C/C++ pur et est assez monolithique, en prenant en entrée un fichier texte décrivant le graphique et produisant différents types de sortie, à la fois vectoriel et raster. Ce n'est pas un bon ajustement en tant que moteur de mise en page plug-in, mais pourrait être utilisé en décochant et en fournissant le fichier d'entrée requis et en analysant la sortie. Pas une solution très propre cependant.

Il y a aussi quelque chose qui s'appelle OGDF. Bien qu'il soit entièrement écrit en C++, il a été conçu pour être utilisé comme bibliothèque de moteur de mise en page et dispose d'une interface bien structurée pour cela. Il prend en charge différents algorithmes de mise en page optimisée, y compris Sugiyama si c'est ce qui vous intéresse.

Si vous êtes intéressé à mettre en œuvre une variante optimisée sur Sugiyama, vous pouvez toujours rouler votre propre en utilisant un neat description of the algorithm :)

En fin de compte Cependant, vous devriez probablement décider du type de disposition que vous recherchez avant de prendre une décision sur la bibliothèque.

Answer 2

Microsoft Research dispose d'un moteur de présentation graphique automatisé qui peut vous aider dans cette tâche.

Vous pouvez en lire davantage ici:

http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/

Answer 3

yFiles a des implémentations très sophistiquées d'algorithmes de disposition à la fois dirigés par la force (appelés «organiques») et Sugiyama («appelés hierarchiques»). Ils offrent des implémentations sans spectateur pour Java, .net, Silverlight, Flex et Javascript. L'API pour récupérer les coordonnées est disponible en ligne here.

Les algorithmes et leur qualité peuvent être testés dans l'application gratuite yEd Graph Editor, mais les librairies ne sont disponibles que dans le commerce.

Answer 4

Il existe une implémentation de mise en page Sugiyama en Java dans le cadre du système modsl, la licence Apache. la source est here.

J'ai été capable de le convertir raisonnablement facilement en un mélange Objective-C/Objective-C++ implementation basé sur le digramme.

Answer 5

j'avais obtenu les coordonnées des noeuds de cette manière

namespace GleeTest 
{ 
    class GleeTest 
    { 

     static void Main() { 
      Microsoft.Glee.GleeGraph oGleeGraph = new Microsoft.Glee.GleeGraph(); 

      Microsoft.Glee.Splines.ICurve oCurve = 
       Microsoft.Glee.Splines.CurveFactory.CreateEllipse(
        1, 1, 
        new Microsoft.Glee.Splines.Point(0, 0) 
        ); 
      Microsoft.Glee.Node strNode1 = new Microsoft.Glee.Node("Circle", oCurve); 

      Microsoft.Glee.Node strNode3 = new Microsoft.Glee.Node("Diamond", oCurve); 
      Microsoft.Glee.Node strNode4 = new Microsoft.Glee.Node("Standard", oCurve); 
      Microsoft.Glee.Node strNode2 = new Microsoft.Glee.Node("Home", oCurve); 

      oGleeGraph.AddNode(strNode1); 
      oGleeGraph.AddNode(strNode2); 
      oGleeGraph.AddNode(strNode3); 
      oGleeGraph.AddNode(strNode4); 

      Microsoft.Glee.Edge oGleeEdge1 = 
       new Microsoft.Glee.Edge(strNode1, strNode2); 
      Microsoft.Glee.Edge oGleeEdge2 = 
      new Microsoft.Glee.Edge(strNode2, strNode1); 
      Microsoft.Glee.Edge oGleeEdge3 = 
      new Microsoft.Glee.Edge(strNode2, strNode2); 
      Microsoft.Glee.Edge oGleeEdge4 = 
      new Microsoft.Glee.Edge(strNode1, strNode3); 
      Microsoft.Glee.Edge oGleeEdge5 = 
      new Microsoft.Glee.Edge(strNode1, strNode4); 
      Microsoft.Glee.Edge oGleeEdge6 = 
      new Microsoft.Glee.Edge(strNode4, strNode1); 


      oGleeGraph.AddEdge(oGleeEdge1); 
      oGleeGraph.AddEdge(oGleeEdge2); 
      oGleeGraph.AddEdge(oGleeEdge3); 
      oGleeGraph.AddEdge(oGleeEdge4); 
      oGleeGraph.AddEdge(oGleeEdge5); 
      oGleeGraph.AddEdge(oGleeEdge6); 

      oGleeGraph.CalculateLayout(); 


      System.Console.WriteLine("Circle position " + oGleeGraph.FindNode("Circle").Center.X + "," + oGleeGraph.FindNode("Circle").Center.Y); 
      System.Console.WriteLine("Home position = " + oGleeGraph.FindNode("Home").Center.X + "," + oGleeGraph.FindNode("Home").Center.Y); 
      System.Console.WriteLine("Diamond position = " + oGleeGraph.FindNode("Diamond").Center.X + "," + oGleeGraph.FindNode("Diamond").Center.Y); 
      System.Console.WriteLine("Standard position = " + oGleeGraph.FindNode("Standard").Center.X + "," + oGleeGraph.FindNode("Standard").Center.Y); 




     } 

    } 
} 

Answer 6

quelqu'un Juste au cas où sera confronté le même problème. Il existe un projet open-source GraphX ​​for .NET qui incorpore de nombreux algorithmes de mise en page séparés du moteur de visualisation. Vous pouvez donc simplement prendre la bibliothèque logique, effectuer des calculs et obtenir le pack de coordonnées à utiliser dans votre propre outil vis.

https://github.com/panthernet/GraphX