在图中指定某些节点的位置

Question

在图中指定某些节点的位置

5

有没有办法在保持某些节点的位置不变的情况下，让某些算法决定其他节点的位置呢？我希望找到一种算法，将边看作弹簧，这样它就不会离其他节点太远，例如graphopt。我查看了igraph中的几个其他算法，例如lgl、drl，但似乎没有一个允许指定节点位置的，我必须让算法完全控制所有节点的位置。

我之所以问这个问题，是因为我有一组数据的网络，其中一些节点我可以找到近似的地理坐标。我希望在地图上显示整个网络。然后我可以逐步识别更多具有某些地理身份的节点，最终得到至少在视觉上相当准确的地理参考图。

我已经开始使用R中的igraph，但我愿意尝试其他软件包/语言，甚至是GIS工具，如果有接近我所寻找的内容的东西。

谢谢！

毕竟，这个问题不是一个很好的问题，但既然我已经开始了，让我进一步描述一下我想要的。希望我寻求的有道理，而且之前有人做过这件事。

G5W的建议是朝着我想要去的方向发展，但我希望在固定方向后应用原始算法的原则。 FR方法的论文说：

我们仅有两个图形绘制原则：

由边连接的顶点应该靠近彼此。
顶点不应该绘制得太靠近。

所以我认为包括路径10-8-4-1-3的大循环应该缩小并靠近其他节点。如果我像G5M那样固定这四个点，我就可以找到下面的布局。

我认为算法可能会偶然生成这样的图表，所以尝试了下面这种非常粗糙的暴力方法。但是算法从未生成我想要的东西...我想我需要指定一些例外来处理固定节点之间的边缘。

library(igraph)
set.seed(1)
g = erdos.renyi.game(10, 0.3)
LO = layout_with_fr(g)
plot(g, layout=LO)

n <- nrow(LO)
i <-  0
for (i in 1:100000) {
#  i <- i + 1
  LO <- layout_with_fr(g)
  chk <- c(all(LO[c(5,7),2] >= sort(LO[-c(5,7),2])[n-3]), # 5,7 should come close to top
           all(LO[c(2,9),2] <= sort(LO[-c(2,9),2])[2]),   # 2,9 near bottom 
           all(LO[c(2,7),1] <= sort(LO[-c(2,7),1])[2]),   # 2,7 toward left
           all(LO[c(5,9),1] >= sort(LO[-c(5,9),1])[n-3])  # 5,9 toward right
  ) 
  if (all(chk)>1 ) break      
}

[编辑2]

仍在寻找实现这一目标的方法。我发现了一个d3页面Stick Force Layout，看起来很符合我的要求。问题是，我不确定在布局满意后是否能够导出坐标。另外，我可能希望保存中间结果。因此，我应该能够将节点坐标与属性一起保存，以便查看它们是否被卡住。还需要进行数据输入和输出。如果这对于熟悉JS的人来说很简单，请给我指点。如果不行，我会尝试创建json输入/输出接口。

由某种力学布局算法确定用户未指定节点位置的图形

我会将一些节点的位置设置为树状图，以使图形看起来像树形结构。这只是一个例子，但我的意思是，我希望能够大致确定布局的形状，而不必确定每个节点的位置。

- yosukesabai

1

networkx 的弹簧布局版本允许在节点的子集中固定节点位置：https://networkx.github.io/documentation/networkx-1.11/reference/generated/networkx.drawing.layout.fruchterman_reingold_layout.html - Paul Brodersen

我查看了layout_fr的代码，至少从原理上讲，更改将非常简单。我不是很擅长C语言，但我可以说出，主循环会为每个迭代中的每个节点计算x和y的位移，然后将其应用于每个节点的位置。所需的所有工作只是向函数提供另一个参数（例如“fixed”，就像networkx一样），可以检查是否实际应将位移应用于节点位置。您可以通过反复调用该函数并在每次重置固定节点位置来进行破解。 - Paul Brodersen

对于这个hack，你应该把max_iter参数设置为1（假设R和Python接口相同），然后迭代一堆次数（在Python中，默认是500）。 - Paul Brodersen

Paul，谢谢你的建议。我会尝试理解并测试它。我也不是很精通C语言，但我一定会尽力而为。 - yosukesabai

澄清一下，当我说“hack it”时，我的意思是你可以通过在R中多次调用该函数并将max_iter设置为1来实现相同的结果，并在每次迭代时重置要保持固定的节点的位置。不需要了解C语言。只是速度会很慢。 - Paul Brodersen

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- G5W · Accepted Answer

您没有提供图表或特定布局的示例数据，因此我将以随机图表和简单配置为目标。思路是让任何算法布置所有点，然后调整您想要指定的位置。

## basic graph for illustration
library(igraph)
set.seed(1)
g = erdos.renyi.game(10, 0.3)
LO = layout_with_fr(g)
plot(g, layout=LO)

好的，现在假设我们想要将节点2、5、7和9放置在一个框中，而没有任何边交叉。我想做的是采用基本的框架布局并将其移动，以便这四个节点及其边缘远离图形的其余部分。我只需将这四个节点向上移动一点，使它们略高于其他所有节点。

UB = max(LO[,2])
DesiredLO = matrix(c(0,0,0,1,1,0,1,1), nrow=4, ncol=2, byrow=TRUE)
LO[c(2,7,9,5), ]  = DesiredLO + matrix(rep(LO[2,], 4), ncol=2, byrow=TRUE)
LO[c(2,7,9,5), 2] = LO[c(2,7,9,5), 2] + UB - LO[2,2] + 1
plot(g, layout=LO)

也许您可以根据自己的需求进行调整。如果无法满足需求，请使用此示例或类似示例更清楚地指定您想要的内容。