[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] finding paths of given length
From: |
Gábor Csárdi |
Subject: |
Re: [igraph] finding paths of given length |
Date: |
Thu, 5 Apr 2012 10:14:10 -0400 |
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