Re: [igraph] finding paths of given length

[Gábor Csárdi]

On Thu, Apr 5, 2012 at 10:02 AM, Sam Steingold <address@hidden> wrote:
[...]
> note: this is a digraph, it is directed!

Does not matter much here.

>>> 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.

Yes, shortest.paths() is almost doing this:

> g <- graph.lattice(c(4,4), dir=TRUE, circ=TRUE)
> sp <- shortest.paths(g, 1, mode="out")
> sp
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,]    3    0    1    2    4    1    2    3    5     2     3     4     6     3
     [,15] [,16]
[1,]     4     5

You can easily convert this to a list of lists of vertices:

> tapply(as.vector(V(g)), sp, c, simplify=FALSE)
$`0`
[1] 1

$`1`
[1] 2 5

$`2`
[1] 3 6 9

$`3`
[1]  0  7 10 13

$`4`
[1]  4 11 14

$`5`
[1]  8 15

$`6`
[1] 12

List element `4` contains the vertices that are 4 steps away from
vertex '1', etc. Is this what you want?

G.

-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI