listing nodes in paths

[Federico Calboli]

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 [phone]   Fax [phone]

f.calboli [.a.t] imperial.ac.uk
f.calboli [.a.t] gmail.com

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

[Federico Calboli]

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 [phone]   Fax [phone]

f.calboli [.a.t] imperial.ac.uk
f.calboli [.a.t] gmail.com

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

[johan Faux]

Hello,
   
  Is it possible to pass R matrix as a parameter to an internal C procedure?
  From the documentation I got the impression that only 1-dim vectors can be passed.
  Why the following wont work for me?
   
   
  > a<-matrix(1:15,3,5)
> .C("pr",as.integer(a))
   
  void pr(int **a){
  a[1][1]=100;
}
   
   
  Thanks,
  Johan
   

               
---------------------------------


        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

[Austin, Matt]

You need to pass it as a vector and then you can convert to an array
structure in C.  Look at carray.c for one way to do this, there are others.
Browse the source code and see how different authors handle your problem.

Matt Austin
Statistician
Amgen, Inc
800 9AMGEN9 x77431
805-447-7431

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]]On Behalf Of johan Faux
Sent: Monday, March 20, 2006 1:13 PM
To: r-help
Subject: [R] How can I pass a R matrix as parameter to C code?


Hello,
   
  Is it possible to pass R matrix as a parameter to an internal C procedure?
  From the documentation I got the impression that only 1-dim vectors can be
passed.
  Why the following wont work for me?
   
   
  > a<-matrix(1:15,3,5)
> .C("pr",as.integer(a))
   
  void pr(int **a){
  a[1][1]=100;
}
   
   
  Thanks,
  Johan
   

               
---------------------------------


        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide!
http://www.R-project.org/posting-guide.html

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

[Liaw, Andy]

From: johan Faux
>
> Hello,
>    
>   Is it possible to pass R matrix as a parameter to an
> internal C procedure?
>   From the documentation I got the impression that only 1-dim
> vectors can be passed.
>   Why the following wont work for me?

In short, because a matrix in R is just a vector with dim attribute.  .C()
will pass the pointer to a copy of that vector to the C function, and return
the result in a list.  If you want to work with pointer-to-pointer, you need
to do that yourself, starting with what R gives you.  Alternatively you can
use the .Call() interface and work with the R object directly.

Andy
   

>    
>   > a<-matrix(1:15,3,5)
> > .C("pr",as.integer(a))
>    
>   void pr(int **a){
>   a[1][1]=100;
> }
>    
>    
>   Thanks,
>   Johan
>    
>
>
> ---------------------------------
>
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

[Thomas Lumley]

On Mon, 20 Mar 2006, johan Faux wrote:

> Hello,
>
>  Is it possible to pass R matrix as a parameter to an internal C procedure?
>  From the documentation I got the impression that only 1-dim vectors can be passed.
>  Why the following wont work for me?
>
>
>  > a<-matrix(1:15,3,5)
>> .C("pr",as.integer(a))
>
>  void pr(int **a){
>  a[1][1]=100;
> }

Because a is passed as int* rather than int**.

Matrices in R are stored as one-dimensional vectors with a "dim"
attribute.  They can be passed to .C, but you have to pass the dim
information separately, eg


   void pr(int *a, int *dim){

      int nrow, ncol;
      nrow=dim[0];
      ncol=dim[1];

      a[1] = 100; /* a[1,1] */
      a[(10-1) + (5-1) * nrow] = 100; /* a[10,5] */

      return;
   }

called as
   .C("pr",as.integer(a), as.integer(dim(a)))


In fact, int** wouldn't be the right type even for a C two-dimensional
array. The rule that array parameters decay to pointers is not applied
recursively, so int ** is the type for a one-dimensional vector of
pointers to int. If a variable has type int[3][5] it has to be passed as
*int[5] or int[][5] so that the compiler knows how far it is from a[1][1]
to a[2][1].


  -thomas

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html