Hi All,
I have the following adjacency matrix for a directed graph:
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 0 0 0 0
[3,] 1 0 0 0 0 0 0 0
[4,] 0 0 1 0 0 0 0 0
[5,] 0 0 1 0 0 0 0 0
[6,] 1 1 0 0 0 0 0 0
[7,] 0 0 0 1 1 0 0 0
[8,] 0 0 0 0 0 1 1 0
My interest is the numberof path between (8) and (1). Using a
standard matrix moltiplication I can see I have one pathe of length 2
and two paths of length 4.
(paths of length 2)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 0 0 0 0
[3,] 0 0 0 0 0 0 0 0
[4,] 1 0 0 0 0 0 0 0
[5,] 1 0 0 0 0 0 0 0
[6,] 0 0 0 0 0 0 0 0
[7,] 0 0 2 0 0 0 0 0
[8,] 1 1 0 1 1 0 0 0
(paths of length 4)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 0 0 0 0
[3,] 0 0 0 0 0 0 0 0
[4,] 0 0 0 0 0 0 0 0
[5,] 0 0 0 0 0 0 0 0
[6,] 0 0 0 0 0 0 0 0
[7,] 0 0 0 0 0 0 0 0
[8,] 2 0 0 0 0 0 0 0
All in all I have 3 paths (not all of the same length) between (8)
and (1).
Is there already a function in R (whatever the library) that will
list the nodes touched in all those three paths (i.e. 8 -> 6 -> 1; 8 -
> 7 -> 4 -> 3 -> 1; 8 -> 7 -> 5 -> 3 -> 1)?
Regards,
Federico Calboli
--
Federico C. F. Calboli
Department of Epidemiology and Public Health
Imperial College, St. Mary's Campus
Norfolk Place, London W2 1PG
Tel +44 (0)20 75941602 Fax +44 (0)20 75943193
f.calboli [.a.t] imperial.ac.uk
f.calboli [.a.t] gmail.com
Hi All, I found a solution for my question:> I have the following adjacency matrix for a directed graph: > > [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] > [1,] 0 0 0 0 0 0 0 0 > [2,] 0 0 0 0 0 0 0 0 > [3,] 1 0 0 0 0 0 0 0 > [4,] 0 0 1 0 0 0 0 0 > [5,] 0 0 1 0 0 0 0 0 > [6,] 1 1 0 0 0 0 0 0 > [7,] 0 0 0 1 1 0 0 0 > [8,] 0 0 0 0 0 1 1 0 > > My interest is the numberof path between (8) and (1). Using a > standard matrix moltiplication I can see I have one pathe of length > 2 and two paths of length 4. > > Is there already a function in R (whatever the library) that will > list the nodes touched in all those three paths (i.e. 8 -> 6 -> 1; > 8 -> 7 -> 4 -> 3 -> 1; 8 -> 7 -> 5 -> 3 -> 1)?The function is an elaboration of 'findPath' in library 'ggm'. The original code was written in Python by Guido van Rossum and translated into R by Giovanni Marchetti... I translated the Python code for the list_all_paths in the same page: http://www.python.org/doc/essays/graphs.html The function is: "paths" <- function (amat, st, en, path = c()){ indices = 1:nrow(amat) if(st == en) # st is 'node' in recursive calls return(c(path, st)) if(sum(amat[st,]) == 0 ) return(NULL) paths = c() ne = indices[amat[st,]==1] # Boundary of x. Assumes that amat is symmetric for(node in ne){ if(!is.element(node, c(path, st))){ newpaths = paths(amat, node, en, c(path, st)) for(newpath in newpaths){ paths = c(paths,newpath) } } } return(paths) } and if I do: >paths(ad, 8, 1) [1] 8 6 1 8 7 4 3 1 8 7 5 3 1 Which I can then slice to my heart content. Best, Federico -- Federico C. F. Calboli Department of Epidemiology and Public Health Imperial College, St. Mary's Campus Norfolk Place, London W2 1PG Tel +44 (0)20 75941602 Fax +44 (0)20 75943193 f.calboli [.a.t] imperial.ac.uk f.calboli [.a.t] gmail.com