Re: [igraph] Counting the # of chains

[Eric Sun]

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