标签: graph-layout

我有一个表示有向图的数据结构,我想在HTML页面上动态呈现它.这些图通常只是几个节点,可能只有十个节点,所以我的猜测是性能不会是一个大问题.理想情况下,我希望能够使用jQuery将其挂钩,以便用户可以通过拖动节点来手动调整布局.

注意:我不是在寻找图表库.

我需要建议来渲染具有178,000个节点和500,000个边缘的无向图.我尝试过Neato,Tulip和Cytoscape.Neato甚至没有近距离接触,Tulip和Cytoscape声称他们可以处理它,但似乎无法做到.(郁金香什么也没做,Cytoscape声称工作,然后停止.)

我只是喜欢一个矢量格式文件(ps或pdf),它具有远程合理的节点布局.

我试图用Dot和GraphViz绘制一个家谱.

这就是我目前拥有的:

# just graph set-up
digraph simpsons {
ratio = "auto"
mincross = 2.0

# draw some nodes
"Abraham"   [shape=box, regular=1, color="blue"] ;
"Mona"      [shape=box, regular=1, color="pink"] ;
"Clancy"    [shape=box, regular=1, color="blue"] ;
"Jackeline" [shape=box, regular=1, color="pink"] ;
"Herb"      [shape=box, regular=1, color="blue"] ;
"Homer"     [shape=box, regular=1, color="blue"] ;
"Marge"     [shape=box, regular=1, color="pink"] ;
"Patty"     [shape=box, regular=1, color="pink"] ;
"Selma"     [shape=box, regular=1, color="pink"] ;
"Bart"      [shape=box, regular=1, color="blue"] ;
"Lisa"      [shape=box, regular=1, color="pink"] ;
"Maggie"    [shape=box, regular=1, color="pink"] ;
"Ling" …

通过这里的图表我的意思是类似这些图像的东西:

理想的解决方案是:

• 仅使用托管代码
• 允许输出到位图图像
• 允许输出到WPF元素
• 包括某种交互式表面,用于显示支持节点缩放,平移和重组的图形

我也有兴趣了解可能被用作此类工作起点的项目.如果需要一些开发来实现我想要的东西,那么我已经准备好解决它了.这个目标中最复杂的部分似乎是在合理的时间范围内获得图形布局.

对于我正在制作的iOS应用程序,我需要显示根据类型组合在一起的元素组,以及在完美布局中彼此分离的不同类型的组.

我想到了使用一个无向图,其中分组的节点都以一种循环引用相互指向,然后每个组作为另一个"元图",它们的节点也以圆形引用相互指向,希望与良好的图形布局框架一起,这可以很好地显示.

不幸的是,我一直听到的唯一框架是graphviz,但似乎没有适用于iOS的可用端口.

所以我的问题是:

1. 关于如何实现我需要的其他想法？
2. iOS的图形布局的良好实现？
3. 适用于iOS的graphviz可用端口？

更新:请注意,我不是在寻找图形绘图框架,它是用于绘制图形和图表的框架(例如饼图等).我正在寻找一个布局框架,它确定抽象图中任意节点的最佳位置.

我正在尝试更好地使用力导向布局算法(对于有向图)基本算法工作,即满足以下代码中的isStable条件并且算法结束,但边和节点可以重叠.所以我想在边缘的中间添加一些虚拟顶点(如下图所示),这应该解决这个问题,因为虚拟顶点会使边缘排斥其他边缘和节点.

我添加了addDummies方法,该方法对于不是循环的每个边添加一个节点.我将添加的节点称为midNodes.

然后在每次迭代(迭代方法)中,我将midNodes的位置设置在边缘的中间.剩下的就是旧算法.

我获得了一个没有边缘重叠的更好的布局,但是结果条件从未得到满足,而且,绘图不是很好,因为midNodes在中心节点周围形成一种"甜甜圈",如下图所示( midNodes在红色圆圈内)

我正在寻找一个算法的详细描述,该算法在边缘上使用虚拟节点或任何建议使算法终止并具有更好的绘图(我希望midNodes不要将其他节点排斥到外部区域)

我是否应该将中间节点的新边缘添加到旧节点？

一个解决方案可能是改变isStable条件,但这个数字通常可以保证图形的布局正确,所以我不想触摸它.

编辑:我以这种方式使用以下代码

var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
    layouter.iterate(1);
}

以下是当前代码的摘录

Graph.Layout.Spring = function() {
    this.maxRepulsiveForceDistance = 10;
    this.maxRepulsiveForceDistanceQ = this.maxRepulsiveForceDistance * this.maxRepulsiveForceDistance;
    this.k = 2.5;
    this.k2 = this.k * this.k; 
    this.c = 0.01;

    this.maxVertexMovement = 0.2;

    this.damping = 0.7;
};
Graph.Layout.Spring.prototype = {
resetForUpdate : function() {
    this.addDummies();
    this.currentIteration = 0;
    this.resetVelocities();
},

reset : function() {
    this.pastIterations = 0;
    this.currentIteration = 0;
    this.layoutPrepare();
    this.resetForUpdate();
},


isStable: function() {
    var …

在制作图形时,我有完美的瘫痪.如果没有充分探索视觉的对称性,我很难理解正在发生的事情.我也是一个非常直观的学习者,我喜欢简化我刚刚学到的东西并将它们写在纸上.

Graphviz是一个自动绘制东西的好工具,但它可能更好.让我们从一个好图(一个状态机)的例子开始.没关系质量(它可以用更好的工具重新绘制)这个几乎是完美的,除了我将逆时针旋转45度以使对称性明显.然后,它应该让读者花更少的时间来弄清楚状态q1和q2是如何相似以及它们在何处不同.我认为,只有一种最好的方式来表示该图表,因为它旁边没有其他图形.

http://gallery.hd.org/_exhibits/maths/math-finite-state-machine-DHD.gif http://gallery.hd.org/_exhibits/maths/math-finite-state-machine-DHD.gif

现在让我们来看一个不太完美的描述:

http://linux.softpedia.com/screenshots/Graphviz_1.png http://linux.softpedia.com/screenshots/Graphviz_1.png

这看起来像是graphviz会生成的东西.是的,边缘是光滑的,但GAAAAWWWD这是不必要的混乱!它看起来像一张思维导图,而不是一张准备好消费的完成图.我相信人眼CRAVE(不能少)对称.是的,等级制度等也是重要因素.

我很惊讶没有更好的算法可用.有些人根本不是视觉学习者; 他们可以通过阅读符号来掌握抽象概念.不是我!

那么,我的问题是什么？那么,是否有更好的免费软件可用于绘制中小型图形？也许

谢谢!

让我知道如何改进这篇文章.

PS我花了10分钟在dia中画出一个类似的克隆.它仍然不是很完美,但它很方便制作,因为一切都按网格(我错过了一些小细节,但不想重新上传).LR_0需要来自上方的"开始--->"以让用户更快地掌握起始状态.

Finate State Machine http://i47.tinypic.com/315e6w6.png

我有一个以树为主干的图表.所以我有,例如一个带有子B,C和D的节点A.假设图形是自上而下绘制的,A将在一个级别上,然后是B,C和D.我想强制graphviz到在他们的等级内按B,C,D顺序排列.这可能吗？如果是这样,怎么样？

如果只有A,B,C和D,我可以通过在输入点文件中按顺序放入B,C和D来获得此效果.但是如果B,C和/或D中有其他边缘,有时订单会被扰乱.这就是我想要避免的.

我想用dot实现以下模型:

到目前为止,我有这么多:

digraph G {
graph [rankdir = LR, splines=ortho]

  unit [shape=box, width = 2, height = 10];

  more_different_unit [shape=box, height=4];
  other_unit [shape=box, height=4];


  unit -> other_unit [label = "foo"];
  unit -> other_unit [label = "bar"];
  unit -> other_unit [label = "bar"];
  unit -> other_unit [label = "bar"];
  unit -> other_unit [label = "bar"];
  unit -> other_unit [label = "bar"];
  unit -> more_different_unit [label = "bar"];
  unit -> more_different_unit [label = "bar"];
  unit -> more_different_unit [label = "bar"];
  unit -> …

在此示例中:http://bl.ocks.org/mbostock/1747543:

......迈克向我们展示了如何避免节点之间的冲突,以便没有两个节点相互重叠.

我想知道是否有可能避免节点和边缘之间的冲突,以便没有节点"剪辑"或重叠边缘,除非它由该边连接.

使用D3力直接示出了下面的示例该节点L与边缘连接重叠I和A,类似地,节点M与边缘连接重叠L和D.我们如何防止此类案件？