igraph-help
[Top][All Lists]

## Re: [igraph] find all paths from multiple sources

 From: Tamas Nepusz Subject: Re: [igraph] find all paths from multiple sources Date: Fri, 09 Dec 2011 12:58:36 +0100 User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:8.0) Gecko/20111124 Thunderbird/8.0

```Dear Sofia,

Finding all paths in a general graph usually does not make sense because the
presence of even a single cycle in the graph would mean that the number of
such paths would be infinite -- that's why there is no built-in function for
this in igraph. Your graph is very special in the sense that it is acyclic;
in this case, the set of all paths is finite.

Either way, since there is no built-in function for calculating all the
shortest paths, you have to make one yourself. I'm no expert in R so I'd
rather not try it myself, but here is an implementation in Python that you
might try to translate into R:

http://stackoverflow.com/questions/3971876/all-possible-paths-from-one-node-to-another-in-a-directed-tree-igraph

(Note that this calculates all paths *from* a particular vertex to all other
vertices, but all you have to do is to construct the adjacency list with
mode=IN to get all the paths *to* a particular vertex from all others).

Once you have the list of vertices along a particular path in a variable
called `path`, you can simply use mean(E(g, path=path)\$weight) to calculate
the average weight along the path.

Cheers,
Tamas

On 12/08/2011 06:41 PM, Morais, Ana Sofia wrote:
> Dear all,
>
>
>
> I have a question on how to find all paths from multiple source-vertices to
> a particular destination-vertex in a graph.
>
>
>
> As an example, please consider the following graph.
>
>
>
>   > mat <- matrix(c(0,0,0,0,0,2,0,4,2,0,0,0,0,5,3,3,0,0,0,5,0,0,0,0,0), 5,
> byrow = T)
>
>   > g = graph.adjacency(mat, mode="directed", weighted=TRUE)
>
>   > plot(g, edge.label=E(g)\$weight)
>
>
>
> For each source-vertex 2:5 in graph g:
>
>
>
> a. Find all paths to the destination-vertex 1 and
>
> b. calculate the sum of the weights of all (non-redundant) arcs in those
> paths, divided by the total number of (non-redundant) arcs in the paths.
>
>
>
> Results for the graph above:
>
>
>
> Vertex 2
>
> a.
>
>   2->1
>
>   2->3->4->1
>
>   2->4->1
>
> b.
>
>   (2+4+5+3+2)/5
>
>
>
> Vertex 3
>
> a.
>
>   3->4->1
>
> b.
>
>   (5+3)/2
>
>
>
> Vertex 4
>
> a.
>
>   4->1
>
> b.
>
>   3
>
>
>
> Vertex 5
>
> a.
>
>   no path to vertex 1
>
> b.
>
>   0
>
>
>
> Is there a function in Igraph that I could use to achieve this? Thank you
>
>
>
> Best wishes,
>
>
>
> Sofia
>
>
>
> _______________________________________________
> igraph-help mailing list