1

我想使用 igraph 函数在图中找到生成树graph.bfs。你能告诉我怎么做吗？

PS：我尝试使用$fatherfrom 返回值的信息graph.bfs，但结果让我感到困惑。这是一个例子：

g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
plot(g)

tmp <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE,callback=f)

查找生成树

结果是： tmp$order = 1 2 4 5 6 3和tmp$father=0 1 4 1 1 2

我可以使用该$father信息查找所有生成树吗？

4

4 回答 4

3

该father向量由节点索引，即它与 的顺序不同order。

library(igraph)
g <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)
h <- graph( rbind(r$order, r$father[r$order])[,-1], directed=FALSE )
plot(h)

在这个例子中，我们有：

order:  1 2 4 5 6 3
father: 0 1 4 1 1 2.

的i第 th 元素是预遍历顺序中第 th 节点order的名称（或索引） 。i

的i第 th 元素father是具有索引的节点的父节点的名称（或索引），而i不是 的i第 th 元素的名称（或索引） order。i的第 th 个元素的父级order是parent[order[i]]。这就是我们需要定义的边缘。

因此，树的边缘是：

order:  1 2 4 5 6 3
        | | | | | |
father: 0 1 1 1 2 4.
于 2013-08-01T10:04:35.460 回答
1

为避免以下错误： simple_vs_index(x, ii, na_ok) 中的错误：选择了未知顶点，我们需要将代码语句之一更改为：

h <- graph( rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed=FALSE )

这允许 NA 出现在索引中。

于 2016-10-08T17:17:39.740 回答
0

I agree with the answer given by "Vincent Zoonekynd" above. However, it did not work as-it-is with me. So I made some modifications in order for it to work. Here is my code

library(igraph)
g2 <- graph(c(1,2,2,6,1,4,4,6,5,6,1,5,5,3,3,4), directed=FALSE)
r <- graph.bfs(g2, root=1, neimode='all', order=TRUE, father=TRUE)
a = as.integer(r$order)
aa = as.integer(r$father)
h <- graph( rbind(a, aa[a])[,-1], directed=FALSE )
plot(h)

It give a new matrix "h", which is based on the minimum spanning tree of original graph

于 2020-05-01T19:49:00.080 回答
0

我认为order是直截了当的。对于father,

> r$order
6/6 vertices, from 29ab0f7:
[1] 1 2 4 5 6 3
> r$father
+ 6/6 vertices, from 29ab0f7:
[1] NA  1  4  1  1  2

  • 节点 1（标签为 1 的节点）没有父亲 --> NA

  • 节点 2 有节点 1 作为父亲

  • 节点 3 有节点 4 作为父亲

  • 节点 4 有节点 1 作为父亲

  • 节点 5 以节点 1 作为父亲

  • 节点 6 有节点 2 作为父亲*

在用星号表示的情况下，这里很容易混淆。“为什么节点 6 是节点 2 的父节点，而不是节点 4 的父节点？”。答案是，父亲不是定义为节点 6 所连接的横向序列中最近的元素，而是节点 6 所连接的横向序列中最早的元素。即节点6连接到节点2和节点4（节点2在横向序列中较早）。这是一个使这个概念显而易见的例子

g <- sample_smallworld(1, 5, 5, 0.05)
plot(g)
r <- graph.bfs(g, root=1, neimode='all', order=TRUE, father=TRUE)

在此处输入图像描述

如您所见，节点 1 是所有节点的父节点，因为它是横向序列中最早的，并且连接到所有节点。

$order
+ 5/5 vertices, from 0960d64:
[1] 1 2 3 4 5

$father
+ 5/5 vertices, from 0960d64:
[1] NA  1  1  1  1
于 2017-07-28T03:45:58.853 回答