Re: [igraph] find all paths from multiple sources

[Tamas Nepusz]

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
> for your time.
> 
>  
> 
> Best wishes,
> 
>  
> 
> Sofia
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help