Re: [igraph] finding paths of given length

[Sam Steingold]

> * Gábor Csárdi <address@hidden> [2012-04-05 09:31:05 -0400]:
>
> Sorry for the delay! Answers below.

better late than never!

> On Tue, Apr 3, 2012 at 11:16 AM, Sam Steingold <address@hidden> wrote:
>>> * Sam Steingold <fqf-zKKw517/address@hidden> [2012-03-23 14:39:02 -0400]:
>>>
>>> given a digraph, how do I find all paths of given length?

note: this is a digraph, it is directed!

>> neighborhood() appears to be useful, except that it returned really a
>> neighborhood, i.e., the vertexes reachable by <= N steps.
>> What if I want the vertexes reachable in _EXACTLY_ N steps?
>
> You mean shortest paths here? If yes, then you can calculate
> shortest.paths() from a given starting vertex and see which vertices
> are n steps away.

Suppose the graph describes information propagation.
I want to see long paths, i.e., A told B, who told C, who told D.
I understand that normally this would return HUGE lists for even
moderate-sized graphs (for V*d^l for V vertices with average degree d
and paths of length l), but in my case the number of such paths is very
limited as I was able to establish by iterating line.graph() calls.

I guess I might use line.graph() iteratively or, alternatively, take the
set difference between neighborhood(N) and neighborhood(N-1); however, I
would prefer a ready-made solution :-)

e.g., it would be nice to have a function
neighborhoods(graph, nodes=V(graph), mode=c("all", "out", "in"))
which would return a list of vectors of vertices reachable from nodes in
the number of steps equal to the position in the list.
e.g., the first element of the list contains nodes, the second - their
immediate neighbors &c.
then I would be looking for, say, 4th element of the list for each
vertex to find all paths of length 4.

-- 
Sam Steingold (http://sds.podval.org/) on Ubuntu 11.10 (oneiric) X 11.0.11004000
http://www.childpsy.net/ http://honestreporting.com http://dhimmi.com
http://ffii.org http://mideasttruth.com http://www.PetitionOnline.com/tap12009/
If you want it done right, you have to do it yourself