R graphs: all paths lengths between two nodes in a directed graph
2
0
Entering edit mode
@victoria-v-plamadeala-3406
Last seen 7.4 years ago
I would need help in obtaining all path lengths between two nodes in a directed graph. Suppose I have the following directed graph (below) called "mygraph": > library(graph) > > y <- as.character(seq(1,6)) > rel <- list(c(2,4), c(3,5), 6, 5, 6, NULL) > edgelength <- list(c(0,1), c(0,2), 3, 0, 0, "NA") > > edL=vector("list", length=(length(y))) > names(edL)=y > for(l in 1:(length(y))) + {edL[[l]]=list(edges=rel[[l]], weights=edgelength[[l]])} > > mygraph=new("graphNEL", nodes = y, edgeL = edL, edgemode = "directed") > mygraph A graphNEL graph with directed edges Number of Nodes = 6 Number of Edges = 7 > edges(mygraph) $`1` [1] "2" "4" $`2` [1] "3" "5" $`3` [1] "6" $`4` [1] "5" $`5` [1] "6" $`6` character(0) > edgeWeights(mygraph) $`1` 2 4 0 1 $`2` 3 5 0 2 $`3` 6 3 $`4` 5 0 $`5` 6 0 $`6` numeric(0) I am striving to get the lengths of all possible paths between nodes "1" and "6", which are: 1 --> 2 --> 3 --> 6 : length 0+0+3=3 1 --> 2 --> 5 --> 6 : length 0+2+0=2 1 --> 4 --> 5 --> 6 : length 1+0+0=1 What would be a clever way to accomplish this in R? Thank you.
graph graph • 2.6k views
ADD COMMENT
0
Entering edit mode
@lilongisb-sibch-1725
Last seen 7.4 years ago
you can take a look at BioC/RBGL package, which contains quite a number of often-used graph algorithms. Li > I would need help in obtaining all path lengths between two nodes in a > directed graph. > > Suppose I have the following directed graph (below) called "mygraph": > >> library(graph) >> >> y <- as.character(seq(1,6)) >> rel <- list(c(2,4), c(3,5), 6, 5, 6, NULL) >> edgelength <- list(c(0,1), c(0,2), 3, 0, 0, "NA") >> >> edL=vector("list", length=(length(y))) >> names(edL)=y >> for(l in 1:(length(y))) > + {edL[[l]]=list(edges=rel[[l]], weights=edgelength[[l]])} >> >> mygraph=new("graphNEL", nodes = y, edgeL = edL, edgemode = "directed") >> mygraph > A graphNEL graph with directed edges > Number of Nodes = 6 > Number of Edges = 7 >> edges(mygraph) > $`1` > [1] "2" "4" > > $`2` > [1] "3" "5" > > $`3` > [1] "6" > > $`4` > [1] "5" > > $`5` > [1] "6" > > $`6` > character(0) > >> edgeWeights(mygraph) > $`1` > 2 4 > 0 1 > > $`2` > 3 5 > 0 2 > > $`3` > 6 > 3 > > $`4` > 5 > 0 > > $`5` > 6 > 0 > > $`6` > numeric(0) > > I am striving to get the lengths of all possible paths between nodes "1" > and "6", which are: > > 1 --> 2 --> 3 --> 6 : length 0+0+3=3 > 1 --> 2 --> 5 --> 6 : length 0+2+0=2 > 1 --> 4 --> 5 --> 6 : length 1+0+0=1 > > What would be a clever way to accomplish this in R? Thank you. > > _______________________________________________ > Bioconductor mailing list > Bioconductor at stat.math.ethz.ch > https://stat.ethz.ch/mailman/listinfo/bioconductor > Search the archives: > http://news.gmane.org/gmane.science.biology.informatics.conductor >
ADD COMMENT
0
Entering edit mode
Hi Li, I did look into all RBGL graph algorithms. They appear useful for situations when one is interested in some optimal criteria, like the shortest path. It seems that getting all possible paths between two nodes and their associated lengths would rely on some recursive method. I can neither come up with a code in R for such a method nor do I see a way to apply the RBGL functions to my problem. Would you have any more specific suggestions? Thanks, Victoria ----- Original Message ----- From: Li Long <li.long@isb-sib.ch> Date: Wednesday, April 22, 2009 7:26 am Subject: Re: [BioC] R graphs: all paths lengths between two nodes in a directed graph > > you can take a look at BioC/RBGL package, which contains quite a > number of > often-used graph algorithms. > > Li > > > I would need help in obtaining all path lengths between two > nodes in a > > directed graph. > > > > Suppose I have the following directed graph (below) called > "mygraph":> > >> library(graph) > >> > >> y <- as.character(seq(1,6)) > >> rel <- list(c(2,4), c(3,5), 6, 5, 6, NULL) > >> edgelength <- list(c(0,1), c(0,2), 3, 0, 0, "NA") > >> > >> edL=vector("list", length=(length(y))) > >> names(edL)=y > >> for(l in 1:(length(y))) > > + {edL[[l]]=list(edges=rel[[l]], weights=edgelength[[l]])} > >> > >> mygraph=new("graphNEL", nodes = y, edgeL = edL, edgemode = > "directed")>> mygraph > > A graphNEL graph with directed edges > > Number of Nodes = 6 > > Number of Edges = 7 > >> edges(mygraph) > > $`1` > > [1] "2" "4" > > > > $`2` > > [1] "3" "5" > > > > $`3` > > [1] "6" > > > > $`4` > > [1] "5" > > > > $`5` > > [1] "6" > > > > $`6` > > character(0) > > > >> edgeWeights(mygraph) > > $`1` > > 2 4 > > 0 1 > > > > $`2` > > 3 5 > > 0 2 > > > > $`3` > > 6 > > 3 > > > > $`4` > > 5 > > 0 > > > > $`5` > > 6 > > 0 > > > > $`6` > > numeric(0) > > > > I am striving to get the lengths of all possible paths between > nodes "1" > > and "6", which are: > > > > 1 --> 2 --> 3 --> 6 : length 0+0+3=3 > > 1 --> 2 --> 5 --> 6 : length 0+2+0=2 > > 1 --> 4 --> 5 --> 6 : length 1+0+0=1 > > > > What would be a clever way to accomplish this in R? Thank you. > > > > _______________________________________________ > > Bioconductor mailing list > > Bioconductor at stat.math.ethz.ch > > https://stat.ethz.ch/mailman/listinfo/bioconductor > > Search the archives: > > http://news.gmane.org/gmane.science.biology.informatics.conductor > > > >
ADD REPLY
0
Entering edit mode
Victoria V Plamadeala wrote: > Hi Li, > > I did look into all RBGL graph algorithms. They appear useful for situations when one is interested in some optimal criteria, like the shortest path. It seems that getting all possible paths between two nodes and their associated lengths would rely on some recursive method. I can neither come up with a code in R for such a method nor do I see a way to apply the RBGL functions to my problem. Would you have any more specific suggestions? > Hi, google suggests this method: http://www.perlmonks.org/?node_id=522270 should be relatively straightforward in R, or you can just use their perl code. One word of caution is that if the graph is at all large or dense the size of the output can be enormous. best wishes Robert > Thanks, > > Victoria > > ----- Original Message ----- > From: Li Long <li.long at="" isb-sib.ch=""> > Date: Wednesday, April 22, 2009 7:26 am > Subject: Re: [BioC] R graphs: all paths lengths between two nodes in a directed graph > >> you can take a look at BioC/RBGL package, which contains quite a >> number of >> often-used graph algorithms. >> >> Li >> >>> I would need help in obtaining all path lengths between two >> nodes in a >>> directed graph. >>> >>> Suppose I have the following directed graph (below) called >> "mygraph":> >>>> library(graph) >>>> >>>> y <- as.character(seq(1,6)) >>>> rel <- list(c(2,4), c(3,5), 6, 5, 6, NULL) >>>> edgelength <- list(c(0,1), c(0,2), 3, 0, 0, "NA") >>>> >>>> edL=vector("list", length=(length(y))) >>>> names(edL)=y >>>> for(l in 1:(length(y))) >>> + {edL[[l]]=list(edges=rel[[l]], weights=edgelength[[l]])} >>>> mygraph=new("graphNEL", nodes = y, edgeL = edL, edgemode = >> "directed")>> mygraph >>> A graphNEL graph with directed edges >>> Number of Nodes = 6 >>> Number of Edges = 7 >>>> edges(mygraph) >>> $`1` >>> [1] "2" "4" >>> >>> $`2` >>> [1] "3" "5" >>> >>> $`3` >>> [1] "6" >>> >>> $`4` >>> [1] "5" >>> >>> $`5` >>> [1] "6" >>> >>> $`6` >>> character(0) >>> >>>> edgeWeights(mygraph) >>> $`1` >>> 2 4 >>> 0 1 >>> >>> $`2` >>> 3 5 >>> 0 2 >>> >>> $`3` >>> 6 >>> 3 >>> >>> $`4` >>> 5 >>> 0 >>> >>> $`5` >>> 6 >>> 0 >>> >>> $`6` >>> numeric(0) >>> >>> I am striving to get the lengths of all possible paths between >> nodes "1" >>> and "6", which are: >>> >>> 1 --> 2 --> 3 --> 6 : length 0+0+3=3 >>> 1 --> 2 --> 5 --> 6 : length 0+2+0=2 >>> 1 --> 4 --> 5 --> 6 : length 1+0+0=1 >>> >>> What would be a clever way to accomplish this in R? Thank you. >>> >>> _______________________________________________ >>> Bioconductor mailing list >>> Bioconductor at stat.math.ethz.ch >>> https://stat.ethz.ch/mailman/listinfo/bioconductor >>> Search the archives: >>> http://news.gmane.org/gmane.science.biology.informatics.conductor >>> >> > > _______________________________________________ > Bioconductor mailing list > Bioconductor at stat.math.ethz.ch > https://stat.ethz.ch/mailman/listinfo/bioconductor > Search the archives: http://news.gmane.org/gmane.science.biology.informatics.conductor > -- Robert Gentleman, PhD Program in Computational Biology Division of Public Health Sciences Fred Hutchinson Cancer Research Center 1100 Fairview Ave. N, M1-B514 PO Box 19024 Seattle, Washington 98109-1024 206-667-7700 rgentlem at fhcrc.org
ADD REPLY
0
Entering edit mode
lo_ken • 0
@lo_ken-7324
Last seen 7.0 years ago
United States

Hi Victoria,

This reply is likely 6 years too late.  But I recently asked the exact same question.  Since I couldn't find anyone else who had done the work, I decided to write it based on Robert's suggestion.  Here is what I wrote.  Hopefully, it will be helpful to someone else.

To use it, just put in an adjacency matrix and specify pathlength (i.e. 3).  You should get a vector back of all of the possible paths.  For me, I wasn't interested in paths where you back track and visit a node more than once, so I included a backtrack flag to specify where you care about back tracking or not.

HTH,

Ken

 

=== code ===

findPath <- function(adj.matrix, pathlengths, backtrack=F, plot=F){
    if(plot){
        require(Rgraphviz)
        testgraph <- new("graphAM", adj.matrix, edgemode="directed")
        plot(testgraph, attrs=list(node =list(fillcolor="lightblue"), edge=list(arrowsize=0.5)))
    }
    
    converted.path.matrix <- matrix("", nrow=nrow(adj.matrix), ncol=ncol(adj.matrix))
    path.matrix <- matrix("", nrow=nrow(adj.matrix), ncol=ncol(adj.matrix))
    for (i in 1:nrow(adj.matrix)){
        for (j in 1:ncol(adj.matrix)){
            if (adj.matrix[i,j] == 1) {
                converted.path.matrix[i,j] <- paste(c(i,j), collapse=",")
                path.matrix[i,j] <- j
            }
        }
    }
    
    new.path.matrix = converted.path.matrix
    
    if (pathlengths == 1)
        return(as.vector(return_paths(new.path.matrix, backtrack)))    
    if (pathlengths > 1){
        for (n in 2:pathlengths){
            new.path.matrix <- matrix_combine(new.path.matrix, path.matrix)
        }
    }
    return(as.vector(return_paths(new.path.matrix, backtrack)))
}


# A and B both matrix
matrix_combine <- function(A, B){
    #data checks
    if (!is.matrix(A) | !is.matrix(B))
        stop ("A needs to be a matrix, B needs to be a matrix")
    if (ncol(A) != nrow(B) | nrow(A) != ncol(B))
        stop ("Incompatible matrix dimensions between A and B!")
    
    result <- matrix("", nrow=nrow(A), ncol=ncol(B))
    for (i in 1:ncol(A)){
        #print(paste("i=", i))
        for (j in 1:nrow(A)){
            #print(paste("j=", j))
            temp <- NULL
            for (k in 1:ncol(A)){
                #print(paste("k=", k))
                temp <- c(temp, combine_paths(A[i,k], B[k,j]))   
            }
            temp2 <- lapply(temp, function(x){
                junk <- NULL
                if (x != ""){
                    junk <- c(junk, x)
                }
                junk
            })
            temp2 <- paste(unlist(temp2), collapse="/")
            result[i,j] <- temp2
        }
    }
    result
}

combine_paths <- function(x,y){
    result <- ""
    counter <- 1
    for (i in unlist(strsplit(as.character(x), split="/"))) {
        for (j in y){
            if (i != "" & j != "" & counter != 1){
                result <- c(result, paste(c(i,j), collapse=","))
            } else if (i != "" & j != "" & counter == 1){
                result <- paste(c(i,j), collapse=",")
            }
            counter = counter + 1
        }
    }
    if (length(result) > 1) return(paste(result, collapse="/"))
    return(result)
}


return_paths <- function(path.matrix, backtrack=F){
    result <- NULL
    if (is.matrix(path.matrix)){
        for (i in 1:nrow(path.matrix)){
            for (j in 1:ncol(path.matrix)){
                if (path.matrix[i,j] != ""){
                    result <- c(result, strsplit(path.matrix[i,j], split="/"))
                }
            }
        }
    } 
    result <- unique(sort(unlist(result)))
    if (!backtrack) {
        unlist(sapply(result, function(x){
            temp <- unlist(strsplit(x, split=","))
            if( length(unique(temp)) != length(temp)) return(NULL)
            x
        }))
    } else {
        result
    }
}

 

 

ADD COMMENT

Login before adding your answer.

Traffic: 201 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6