Geek Answers Handbook

Find all the paths between two vertices (nodes)

I am new to R programming and am involved in graphing using R. I would like to ask how I implement code that can find all the paths between two vertices or nodes based on an adjacency matrix. I saw many implementations in other programming languages, but most of them used queues, as in (BFS), to make them work. For example, this is an extreme list of my schedule.

          [,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

If I need all the paths between node 0 and node 22, they should be two paths:

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

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

thank

+5
source share
5 answers

( ) , .

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)

, "", . , :

indirect <- direct

, , . , ( , , ). "" , . "in" "total":

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"))
+4

, (DAG), :

(A^n)_ij n i j. A + A^2 + ... + A^n + ..., . , DAG, , n, A^n = 0. A . (I - A)^(-1), i - .

EDIT:

R, .

, node i. v , i - , 1. . 1- node

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

v_(n+1) = sign(v_n + A . v_n), sign() 1 0. , , v , , node i.

v ( , A), node .

node. , node ( , .. 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 - node.

traverse( {start}, target ).

, , , , , , ""

+2

-

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

, , , ?

0

igraph:

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

.

- . , .

all_simple_paths (graph, from, to = V (graph), mode = c ( "out", "in", "all", "" ))


.


.


. .


, , . , . , , , .. . .

, , , .

.

0
source

More articles:


All Articles