igraph-help
[Top][All Lists]

## Re: [igraph] Counting the # of chains

 From: Eric Sun Subject: Re: [igraph] Counting the # of chains Date: Tue, 2 Sep 2008 09:45:52 -0700 User-agent: Microsoft-Entourage/12.10.0.080409

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
> http://lists.nongnu.org/mailman/listinfo/igraph-help

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

_______________________________________________
igraph-help mailing list