网络中的跟踪连接？

如何在有向图中找到/隔离与节点的所有上游/下游连接？网络中的跟踪连接？

例如，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调用该功能？

来源

2016-05-31 hatmatrix

应选择'C'也找回除了'A-> B-> C''D-> B-> C'？图表无法区分这一点，是吗？ –

我同意@circuit咖啡 - 虽然输入侧可能知道它们是分开的路径，并且图形被绘制为表明它们彼此成直角，但这是任意的。您是否可以在输入时创建属性或标签以记住这些数据？ – thelatemail

@ mathematical.coffee：你说得对，我纠正了我的问题 – hatmatrix

这就完成了由@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

来源

2017-08-28 19:50:35 G5W

在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

尽管这并不完全解决您的问题，它可能会提供一些有用的提示。

来源

2016-05-31 00:43:56 Psidom

网络中的跟踪连接？

回答

相关问题