跟踪网络中的连接？

Question

如何 find/isolate 所有 upstream/downstream 连接到有向图中的节点？[=18=]

例如，在 R igraph 中我创建了两条路径 A->B->C 和 D->B->E:

library(igraph)

g <- graph_from_literal(A-+B-+C, D-+B-+E)

plot(g, vertex.color = "grey", edge.color = "blue")

通过选择节点 C 或 A，我想检索 A->B->C 和 D->B->C。这个操作叫什么？是否可以通过 R/igraph 调用此功能？

Answer 1

在R igraph包中，有两个函数适用于基于两种算法搜索连接——graph.dfs（深度优先搜索）和graph.bfs（广度优先搜索）。

library(igraph)
graph.dfs(g, "A", neimode = "out", dist = T)$dist
A B C D E 
0 1 2 0 2

graph.bfs(g, "A", neimode = "out", dist = T)$dist
A B C D E 
0 1 2 0 2

另一个对你的情况有用的函数是all_shortest_path()，它给出了从一个顶点开始的所有路径：

all_shortest_paths(g, "A", mode = "out")
$res
$res[[1]]
+ 1/5 vertex, named:
[1] A

$res[[2]]
+ 2/5 vertices, named:
[1] A B

$res[[3]]
+ 3/5 vertices, named:
[1] A B C

$res[[4]]
+ 3/5 vertices, named:
[1] A B E


$nrgeo
[1] 1 1 1 0 1

虽然这不能完全解决您的问题，但它可能会提供一些有用的提示。

Answer 2

@Psidom 开始的回答到此结束。

您似乎只在寻找最大条进出节点的路径。离开节点的最大路径以汇结束。进入节点的最大路径从源开始。我为进入或离开节点的路径提供了稍微不同的解决方案。

使用您的示例数据：

sources = which(degree(g, v = V(g), mode = "in")==0,  useNames = T)
sinks   = which(degree(g, v = V(g), mode = "out")==0, useNames = T)

## Paths out of A
all_simple_paths(g, from = "A", to = sinks)
[[1]]
+ 3/5 vertices, named:
[1] A B C

[[2]]
+ 3/5 vertices, named:
[1] A B E

## Paths into C
lapply(sources, function(x) all_simple_paths(g, from =x, to = "C"))
$A
$A[[1]]
+ 3/5 vertices, named:
[1] A B C

$D
$D[[1]]
+ 3/5 vertices, named:
[1] D B C

跟踪网络中的连接？

trace connections in network?

r

igraph