查找两个顶点（节点）之间的所有路径

问题描述：

我是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

感谢

通过路径，你是指没有重复顶点的路径？否则在你的例子中，你会有无限多的循环。 – Szabolcs

我只是想找到任何给定的两个顶点之间的所有路径。这个例子是一个没有周期的有向图。 – malhom

答

你想拥有的图形模型任务视图的很好看：

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

虽然我没有的东西你是什么在统计意义上做图形建模，这个任务视图概述了图形处理和算法的软件包。

我已经使用igraph为各种图形的东西。

我见过并在igraph包上做了一些工作。我只能找到（get.all.shortest.paths）。我可能需要实现（DFS算法）给我所有给定的两个顶点之间的所有路径。 – malhom

答

假定有一个简单的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)。

需要注意的是，我们移除该目标不可达，只存在所有节点的步骤，以加快遍历，不要进入“死胡同”

我实际上需要找到所有路径（不包括所有路径）。我发现一些其他语言的实现使用队列来确定已经访问过哪些节点等等。你能否通过所有可能的方式递归地遍历图表来解释如何做到这一点。我可能需要将它用于大图。 – malhom

@malhom我更新了我的答案。请接受它对你是否有用。 – Szabolcs

我会考虑你的想法，并尝试完成它。谢谢 – malhom

答

只是做了深度优先搜索，不检查节点访问 - 这可以给你的路径数特定长度

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

如何ÿ你是否有多条路径连接两个点，每个都被认为是不同的？

只适用于图非循环的情况 – hasanatkazmi

答

我已经使用以下代码来创建矩阵（顶点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"))

答

检查以下的igraph功能了：

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

它列出来自一个源的所有简单路径。

说明此函数列表是从一个源顶点到另一个顶点或顶点的简单路径。如果它访问的顶点没有被访问多次，路径很简单。

用法 all_simple_paths（曲线图中，从，到= V（图），模式= C（ “出”， “在”， “所有”， “总”））

参数

图表
输入图形。

from
源顶点。

到
顶点的目标顶点。缺省为所有顶点。

模式
字符常量，指出是否应该为有向图计算给定顶点的最短路径或从给定顶点计算最短路径。如果超过，则将考虑顶点的最短路径，如果在那里，则考虑它。如果全部，默认，那么将使用相应的无向图，即。没有定向路径被搜索。对于无向图，这个参数被忽略。

详细

注意，可能有成倍图的两个顶点之间的许多路径，而且使用该功能时，如果你的图形是网格状的，你可能会耗尽内存。

该函数当前忽略多个循环边。

查找两个顶点（节点）之间的所有路径

相关推荐