c# - C# 中的图形布局优化

Question

我有一个需要组织为美学图表的对象列表。我目前的方法涉及 IronPython 和遗传算法，但这需要的时间太长了。

我一直在阅读 Graphviz、QuickGraph 和 Graph#，但我不需要可视化部分 - 我已经有一个应用程序可以显示给定 x/y 坐标的节点。有人告诉我，Sugiyama 算法和基于力的算法系列都倾向于输出令人愉悦的图形，但我似乎找不到一个 .NET 库可以在没有一些非常严格的源代码的情况下输出坐标而不是图像黑客攻击。

任何人都可以推荐库、算法或类似的东西吗？

Answer 1

There are a number of options, with various pros and cons - you may want to sift through this which is a list of software that does, more or less, what you're looking for.

It used to be the case that finding an open source solution was difficult, but the once commercially licensed MSAGL now seems to be open source.

The distinction between Graph# and QuickGraph is that the latter provides graph traversal and manipulation primitives but does not provide any layout algorithms. Graph# has all the source available, and from what I've (briefly) looked at, has a neat separation between layout engine and drawing implementation.

Graphviz is written in pure C/C++ and is fairly monolithic, taking as input a text file describing the graph and producing various types of output, both vector and raster based. It isn't a great fit as a plug-in layout engine, but could be used by shelling out and providing the requisite input file and parsing the output. Not a very clean solution though.

There's also something called OGDF. Although it's written entirely in C++, it has been designed to be used as a layout engine library and has a well-structured interface for this. It supports various layout algorithms including optimised Sugiyama if that's what you're interested in.

If you're interested in implementing an optimised variation on Sugiyama, you could always roll your own using a neat description of the algorithm :)

Ultimately though, you should probably decide what type of layout you're after before you make a decision on the library.

Answer 2

Microsoft Research 有一个自动图形布局引擎，可以帮助您完成这项工作。

你可以在这里阅读更多关于它的信息：

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

Answer 3

以防万一有人会遇到类似的问题。有一个 GraphX for .NET 开源项目，其中包含许多与可视化引擎分离的布局算法。因此，您只需获取逻辑库，执行计算并获取要在您自己的 vis 工具中使用的坐标包。

https://github.com/panthernet/GraphX

Answer 4

yFiles具有非常复杂的强制导向（称为“有机”）和基于 Sugiyama（“称为分层”）布局算法的实现。它们为 Java、.net、Silverlight、Flex 和 Javascript 提供无需查看器的实现。检索坐标的 API 可在此处在线获得。

算法及其质量可以在免费的yEd Graph Editor应用程序中进行测试，但这些库仅在商业上可用。

Answer 5

作为 modsl 系统的一部分，Apache 许可证有一个 Sugiyama 布局实现在 Java 中。来源在这里。

我能够相当容易地将它转换为基于有向图的混合Objective-C/Objective-C++ 实现。

Answer 6

我以这种方式获得了节点的坐标

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);




        }

    }
}