igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Counting the # of chains


From: Csardi Gabor
Subject: Re: [igraph] Counting the # of chains
Date: Fri, 5 Sep 2008 14:46:36 +0200
User-agent: Mutt/1.5.9i

Eric, I think this is an O(n^2) problem, so you cannot really do 
much better than this. Some R code enhancements can speed it up,
this was five times faster for me, but I guess it depends on the 
graph:

CountAllTerminalChains2 = function(graph) {
  chainlengths = numeric()
  sources <- V(graph)[ degree(graph, mode="in") == 0 ]
  targets <- V(graph)[ degree(graph, mode="out") == 0 ]
  for (v in sources) {
    if (v%%100==0) {print(paste("completed",v,"nodes"))}
    shortestpaths = get.all.shortest.paths(graph, v, mode=c("out"))
    valid <- sapply(shortestpaths, tail, 1) %in% targets
    shortestpaths = shortestpaths[valid]
    chainlengths <- c(chainlengths, sapply(shortestpaths, length))
  }
  return(data.frame(table(chainlengths-1)))
}

Further speedup would be to calculate just the number of shortest paths,
and not the paths themselves, within the C igraph core. I put this 
on the TODO list, it is not hard to do it.

G.

On Tue, Sep 02, 2008 at 09:45:52AM -0700, Eric Sun wrote:
> A Œchain¹ would be a shortest path.  I¹d like the number of paths of length
> 1 that start with a node with in-degree 0 and end with a node with
> out-degree 0, the number of such paths of length 2, 3, 4, etc.
> 
> Here¹s my implementation, which is unfortunately O(n^2).  Takes about 10
> minutes to run on my machine with a 75,000-node graph.  I¹d appreciate any
> comments/speed enhancements/etc.
> 
> #definition: length refers to tiers of edges; i.e. length=1 means there¹s
> one edge between two nodes.
> CountAllTerminalChains = function(graph) {
>     chainlengths = array()
>     for (v in V(graph)) {
>         if (v%%100==0) {print(paste("completed",v,"nodes"))}
>         indegree = degree(graph, v, mode=c("in"))
>         if (indegree==0) {
>             shortestpaths = get.all.shortest.paths(graph, v, mode=c("out"))
>             for (pathlist in shortestpaths) {
>                 if(degree(graph, pathlist[length(pathlist)], mode=c("out"))
> == 0) {
>                     chainlengths[length(chainlengths)+1] = length(pathlist)
> - 1
>                 }
>             }
>         }
>     }
>     return(data.frame(table(chainlengths)))
> }
> 
> 
> 
> On 8/30/08 4:25 AM, "Csardi Gabor" <address@hidden> wrote:
> 
> > Hi Eric, what is a 'chain' for you? A chain is a shortest path?
> > Or just any path? If the former, just do
> > 
> > length(get.all.shortest.paths(graph, from, to, mode="out"))
> > 
> > It is slighly overkill, because we don't actually need all the paths
> > themselves, but might work if your graphs are not very big or not very
> > dense.
> > 
> > Gabor
> > 
> > On Tue, Aug 26, 2008 at 10:52:37AM -0700, Eric Sun wrote:
> >> > Hi,
> >> >
> >> > I¹m wondering if it¹s possible, using the igraph R interface, to count 
> >> > the
> #
> >> > of chains of a certain length.
> >> >
> >> > I am familiar with path.length.hist(), but that double-counts chains
> >> because
> >> > all the 1-length chains are included in the 2-length chains, etc.  The
> >> > nonpredictable structure of my graph may not allow me to calculate a
> >> > non-double-counting histogram using the results of path.length.hist().
> >> >
> >> > Ideally I would like to count the number of chains of length X from a 
> >> > node
> >> > with degree(mode=²in²) == 0 [i.e., a root node] to a node with
> >> > degree(mode=²out²) == 0  [i.e., a leaf node].
> >> >
> >> > Is this possible?
> >> >
> >> > Thank you very much!
> >> > Eric
> > 
> >> > _______________________________________________
> >> > igraph-help mailing list
> >> > address@hidden
> >> > http://lists.nongnu.org/mailman/listinfo/igraph-help
> > 
> > 
> > --
> > Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK
> > 
> > 
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden
> > http://lists.nongnu.org/mailman/listinfo/igraph-help
> > 
> 

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK




reply via email to

[Prev in Thread] Current Thread [Next in Thread]