ネットワーク内のトレース接続？

Question

有向グラフ内のノードへのすべてのアップストリーム/ダウンストリーム接続を検索/分離するにはどうすればよいですか？例えば

、RのIGRAPHでIは、2つのパス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

これで@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 

Answer 2

パッケージでは、（深さ優先検索）とgraph.bfs（幅優先検索）の2つのアルゴリズムに基づいて接続を検索するのに適した2つの機能があります。

が

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 

これはまさにあなたの問題を解決していませんが、それはいくつかの有用なヒントを提供するかもしれない：

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()、です。