Re: [igraph] Counting the # of chains

[Eric Sun]

Thanks, this is fantastic!


On 9/5/08 5:46 AM, "Csardi Gabor" <address@hidden> wrote:

> 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
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help