[R] listing nodes in paths
Federico Calboli
f.calboli at imperial.ac.uk
Mon Mar 20 21:05:06 CET 2006
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
More information about the R-help
mailing list