Re: [igraph] find all paths from multiple sources

[Moses Boudourides]

Tamas,

Excuse me if this has been already answered, but I was wondering
whether igraph has any functions for the longest path problem in
certain situations where an algorithm can be implemented approximately
since this an NP-complete problem?

Greetings,

--Moses


On Fri, Dec 9, 2011 at 1:58 PM, Tamas Nepusz <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help