logo标签列表

C#中的图形布局优化

c#optimizationperformancegraph-layout
17

我有一列需要组织成美观图形的对象。目前的方法是使用IronPython和遗传算法，但这需要太长时间。

我已经阅读了Graphviz、QuickGraph和Graph#，但我不需要可视化部分 - 我已经有一个应用程序会在给定的x/y坐标下显示节点。有人告诉我Sugiyama算法和基于力的算法族通常会输出令人满意的图形，但我似乎找不到能输出坐标而不进行一些严重的源代码修改的.NET库。

有人能推荐库、算法或类似的东西吗？

6个回答
28
有许多选择，各有优缺点 - 你可能需要浏览这个列表，里面列出了一些大致符合你需求的软件。
以前很难找到开源解决方案，但曾经商业许可的MSAGL现在似乎是开源的。 Graph#和QuickGraph之间的区别在于后者提供了图遍历和操作原语，但不提供任何布局算法。 Graph#的所有源代码都可用，并且从我（简要）查看的情况来看，它在布局引擎和绘制实现之间有一个清晰的分离。 Graphviz纯粹由C/C++编写，相当庞大，以文本文件作为输入描述图形并生成各种基于向量和光栅的输出。 它不适合作为插件式布局引擎，但可以通过调用外部程序并提供所需的输入文件以及解析输出来使用。这不是一个非常干净的解决方案。
还有一种叫做OGDF的东西。尽管它完全由C++编写，但已经设计成可用作布局引擎库，并且有一个良好结构化的界面。它支持各种布局算法，包括优化的Sugiyama算法，如果你感兴趣的话。如果您有兴趣实现优化的Sugiyama变体，您可以使用算法的简明描述自行编写 :)

但是，最终您应该在选择库之前确定所需的布局类型。

5
1
我尝试了GLEE/MSAGL，但据我所知它只能输出图像 - 你知道是否可以获取坐标吗？ - hb.
2
我曾经认为布局引擎与渲染组件是独立的，但我无法百分之百确定。这篇论文讨论了它背后的理论，包括Sugiyama算法。ftp://ftp.research.microsoft.com/pub/tr/TR-2007-72.pdf - Michael A. McCloskey
2
是的，你可以从MSAGL（曾称GLEE）中仅获取坐标，并实现自己的渲染 - http://coding-time.blogspot.com/2009/03/debugger-visualizer-for-visual-studio.html - Martin Konicek
1
MSAGL确实是GLEE的进一步开发和付费版本，但重要的是要注意，GLEE仍然存在，并且可以免费用于非商业目的。在此处下载GLEE的免费版本：http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/default.aspx - Silas Hansen
2
MSAGL现已在GitHub上作为开源项目发布：http://github.com/Microsoft/automatic-graph-layout - George Birbilis
1
MSAGL现在似乎已经采用MIT许可证：https://github.com/Microsoft/automatic-graph-layout/blob/master/LICENSE，而且它正在维护中，因为我最近看到他们推入了Silverlight版本的修复程序。 - George Birbilis
4

如果有人遇到类似的问题，可以使用 GraphX for .NET 开源项目，该项目包含许多布局算法，与可视化引擎分离。因此，您可以仅使用逻辑库进行计算，并获取坐标包以在自己的可视化工具中使用。

https://github.com/panthernet/GraphX

3

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

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

2
这是一个有点昂贵的解决方案，但其架构和文档非常不错，而且还拥有多个平台的库（现在包括一些HTML5）。 - George Birbilis
2

I had got the coordinates of nodes in this way

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




        }

    }
}
2

modsl系统中有一个Java实现的Sugiyama布局，使用Apache许可证。源代码在这里。

我能够相对容易地将其转换为基于digraph的混合Objective-C/Objective-C++实现。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接