查找兩個頂點（節點）之間的所有路徑

Question

我是R編程的新手，我參與使用R表示圖。我想問一下如何實現可以找到兩個節點之間所有路徑的代碼基於鄰接矩陣的頂點或節點。我在其他編程語言中看到過許多實現，但其中大多數使用隊列（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的路徑的數量。因此，您需要計算A + A^2 + ... + A^n + ...以獲取任意兩個節點之間的路徑總數。您必須與DAG合作，因爲這保證足夠大的n,A^n = 0。然後結果可寫爲A . (I - A)^(-1)其中I是單位矩陣。

---

編輯：

我真的不知道[R，所以我只能給你一些僞代碼或解釋。

首先，我們來看看從節點i可到達的節點集。讓我們定義矢量v只包含零，除了它在其中包含1的第i位置處。對於第一點，你將有

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

現在讓v_(n+1) = sign(v_n + A . v_n)，其中sign()功能的目的是通過1取代非零元素，並保持零0，直到你到達固定點做這個迭代和你將具有在與從節點i可到達的節點對應的位置具有非零元素的矢量v。

如果您不是從矢量v開始使用單位矩陣（與A的大小相同），您將一次獲得每個其他節點的可達節點。

現在你有任何起始節點的可達節點集。類似地，你可以得到任何目標節點可以到達的節點列表（只是反轉有向邊，即轉置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

只是做了深度優先搜索，不檢查節點訪問 - 這可以給你的路徑數特定長度

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); 
} 

而且在主要的兩點之間，撥打

dfs(start_node, length); 

如何ÿ你是否有多條路徑連接兩個點，每個都被認爲是不同的？

Answer 4

我已經使用以下代碼來創建矩陣（頂點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：\工作區」的文件。然後我用下面的代碼讀取該文件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 

最後，我遍歷整個圖找每兩個頂點之間的所有間接連接的數量。我把這個數字放到我剛纔創建的間接矩陣中（另外我創建了一個將所有值都放在對角線上的子句）。模式「輸出」確保只有輸出路徑被計數。這也可以設置爲「中」或「總」：

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

它列出來自一個源的所有簡單路徑。

說明 此函數列表是從一個源頂點到另一個頂點或頂點的簡單路徑。如果它訪問的頂點沒有被訪問多次，路徑很簡單。

用法 all_simple_paths（曲線圖中，從，到= V（圖），模式= C（ 「出」， 「在」， 「所有」， 「總」））

參數

圖表
輸入圖形。

from
源頂點。

到
頂點的目標頂點。缺省爲所有頂點。

模式
字符常量，指出是否應該爲有向圖計算給定頂點的最短路徑或從給定頂點計算最短路徑。如果超過，則將考慮頂點的最短路徑，如果在那裏，則考慮它。如果全部，默認，那麼將使用相應的無向圖，即。沒有定向路徑被搜索。對於無向圖，這個參數被忽略。

詳細

注意，可能有成倍圖的兩個頂點之間的許多路徑，而且使用該功能時，如果你的圖形是網格狀的，你可能會耗盡內存。

該函數當前忽略多個循環邊。