[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
> for your time.
>
>
>
> Best wishes,
>
>
>
> Sofia
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help