私は私は2つの間のすべてのパスを見つけることができるコードを実装する方法について質問したいと思い、私はRプログラミングに新たなんだと私はR. を使用してグラフを表すに関与してい

Question

を2つの頂点（ノード）間のすべてのパスを検索隣接行列に基づいて頂点またはノードを生成する。私は他のプログラミング言語で多くの実装を見てきましたが、それらのほとんどは（BFS）のようにキューを使用して動作させました。たとえば、これは私のグラフのエッジリストです。

  [,1] [,2] 
    [1,] 0 1 
    [2,] 1 2 
    [3,] 1 3 
    [4,] 1 4 
    [5,] 2 5 
    [6,] 2 6 
    [7,] 5 7 
    [8,] 5 8 
    [9,] 6 9 
    [10,] 6 10 
    [11,] 8 11 
    [12,] 10 12 
    [13,] 11 13 
    [14,] 11 14 
    [15,] 11 15 
    [16,] 12 16 
    [17,] 12 17 
    [18,] 12 18 
    [19,] 13 19 
    [20,] 16 20 
    [21,] 19 21 
    [22,] 19 22 
    [23,] 20 22 
    [24,] 20 23  

私は、ノード0とノード22との間のすべてのパスを望んでいた場合、彼らは二つの経路でなければなりません：

[[1]] 
    [1] 0 1 2 6 10 12 16 20 22 

    [[2]] 
    [1] 0 1 2 5 8 11 13 19 22 

おかげ

Answer 1

あなたはグラフィカルモデルのタスクビューの優れた読み取りをしたいです：

http://ftp.heanet.ie/mirrors/cran.r-project.org/web/views/gR.html

私はあなたが何のことをしませんが、統計的な意味でのグラフィカルモデリングです。このタスクビューは、グラフ処理とアルゴリズムのためのパッケージを概説します。

私は、様々なグラフィーのもののためIGRAPHを使用しました。

Answer 2

あなたは、単純なdirected acyclic graph（DAG）を持っていると仮定すると、次のようなアプローチは、カウントのために動作します：

(A^n)_ijはあなたのノードiとj間の長さnのパスの数を示します。したがって、任意の2つのノード間のパスの総数を取得するには、A + A^2 + ... + A^n + ...を計算する必要があります。 DAGで作業することは不可欠です。十分な大きさの場合は、n、A^n = 0が保証されています。その結果は、A . (I - A)^(-1)と書くことができ、Iは単位行列です。

---

EDIT：

私は本当に私はあなたにいくつかの擬似コードや説明を与えることができますRを知りません。

まず、ノードから到達可能なノードの集合を見つけよう。i。ベクトルvを定義して、i番目の位置に1を含むゼロ以外の0だけを含むようにしましょう。第一のノードのためにあなたは

v = (1,0,0, ..., 0) 

今すぐsign()機能の目的は、1で非ゼロ要素を交換し、ゼロ0を使用して、固定点に到達するまで、この反復を行い、あなたに保つことですv_(n+1) = sign(v_n + A . v_n)を、聞かせていますノードiから到達可能なノードに対応する位置に0以外の要素を持つベクトルvがあります。

ベクトルvの代わりに（Aと同じサイズの）恒等行列を使用すると、他のノードの到達可能なノードを一度に取得できます。

は今、あなたは、任意の開始ノードのための到達可能なノードのセットを持っています。同様に、ターゲットノードが到達可能なノードのリストを得ることができます（つまり、transpose A）

次に、グラフをたどり、必要なすべてのパスを見つけよう。

この再帰関数は、（擬似コード）を実行する必要があります。

traverse(path-so-far, target): 
    let S = the last element of path-so-far 
    if S == target: 
     output path-so-far 
     return 
    let N = the set of nodes reachable from S in one step 
    remove all nodes from N from which the target is not reachable 
    for each K in N: 
     traverse(append(path-so-far, K), target) 

path-so-farがすでに訪問したノードのリストです。 targetがターゲットノードです。

開始ノードとターゲットノードのペアについては、traverse({start}, target)を実行してください。

我々がターゲットに到達できない、そこからすべてのノードを削除する手順は、トラバーサルをスピードアップするだけであり、そして「袋小路」を入力しないことに注意

Answer 3

だけチェックせず深さ優先探索を行いますノードが訪問した - これは、Yを行う方法

dfs(start_node, length); 

を呼び出して、あなたの特定の長さ

void dfs(int start, int hops) 
{ 
    if(hops == k && start == t) 
    { 
     path++; 
     return; 
    } 
    else if(hops >= k) 
    return; 
    for(int w = 1; w <= n; w++) 
    if(routes[start][w]) 
     dfs(w, hops + 1); 
} 

そしてメインでの2点間のパスの数を与えることができます2つのポイントを結ぶ複数のパスがあり、それぞれが異なるとみなされる場合はどうすればよいですか？

Answer 4

私はすべての2つの頂点間のすべてのパスの数を含むマトリックスを（頂点が頂点をX）を作成するために、次のコードを使用しています。

library(igraph) 
setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 
direct <- get.adjacency(graph) 
indirect <- direct 
max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

この目的のためにigraphライブラリを使用することを提案します。

library(igraph) 

私は "graph.txt"という名前のファイルにエッジリストを入れました。これを "C：\ workspace"に入れました。それから私は、読み取りにするために、そのファイルRに次のコードを使用します。

setwd("C:/Workspace") 
graph <- read.graph("graph.txt", format="edgelist") 

あなただけのすべての大丈夫は（ただし、このステップは離れておくことができます）ことを確認するために、グラフをプロットする場合があります

plot(graph, layout=layout.fruchterman.reingold.grid) 

私は頂点の間のすべての直接のリンクを参照するために、隣接行列を作成します。

direct <- get.adjacency(graph) 

は、その後、私はと呼ばれるダミーのマトリックスを作成し、「間接的」ウィッヒはadjancency行列のコピーです。私は、後に、間接的な値でそれを埋めるために、この行列を必要とする：

indirect <- direct 

は最後に、私はすべての2つの頂点間のすべての間接的な接続の数を見つけるために、グラフ全体を反復します。私はこれまでに作成したばかりの間接行列にこの数を加えました（さらに、すべての値を対角のゼロに置いた節を作成しました）。モード「アウト」は、発信パスのみがカウントされることを保証する。これはまた、「中」または「合計」に設定することができます。

max <- vcount(graph)-1 
for(i in 0:max) 
for(j in 0:max) 
    indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out")) 

Answer 5

は、次のIGRAPH機能をチェックアウト：

http://igraph.org/r/doc/all_simple_paths.html

それは一つのソースからのすべての単純なパスを一覧表示します。

説明 このファンクションリストは、あるソースの頂点から別の頂点または頂点への単純なパスです。パスは、それが訪れる頂点が2回以上訪問されなければ単純です。

使用 all_simple_paths（へ= V（グラフ）、モード= C（ "アウト" から、 "中" グラフ、 "すべて"、 "合計"））

引数

グラフ
入力グラフ。

ソースの頂点。

~
頂点のターゲット頂点。デフォルトはすべての頂点です。

モード
文字定数は、指定された頂点との最短パスを有向グラフで計算するかどうかを指定します。頂点からの最短パスがある場合は、そこに含まれていればそれが考慮されます。すべてがデフォルトの場合、対応する無向グラフが使用されます。有向パスは検索されません。この引数は、無向グラフの場合は無視されます。

詳細潜在的に存在して指数関数的グラフの2つの頂点間の多くのパスであり、あなたのグラフは格子状である場合、この機能を使用するときにメモリが不足することがあり

注意。

この関数は現在、複数のループエッジを無視しています。