Re: [igraph] All paths between all existing nodes of a network

[Gábor Csárdi]

On Wed, Apr 14, 2010 at 11:42 AM, jordi torrents <address@hidden> wrote:
> 2010/4/14 anupam sinha <address@hidden>:
>> Hi all,
>>               Apologies for asking a question which has already been asked
>> before. Is there any way of finding all the paths(not just the shortest
>> paths) between all pairs of nodes of a network "programmatically"(i.e. not
>> by using any in-built function of igraph) in R/igraph. Thanks in advance for
>> any suggestions.
>>
>
> As Tamas points out, finding all the paths is not possible if the
> graphs contains cycles. However, if you restrict the search to
> node-independent paths (which is a known NP-hard problem), there is an
> approximation algorithm developed by White and Newman [1] which gives
> good lower bounds on numbers of node-independent paths between any
> pair of nodes.

Maybe I am missing something, but I don't think this is an NP-complete
problem. You can solve it in polynomial time, using maximum flow
techniques. igraph has a function that gives you the maximum number of
vertex-independent paths:
igraph.sourceforge.net/doc/html/igraph_vertex_disjoint_paths.html

Best,
Gabor

>
> Salut!
>
> [1] Fast approximation algorithms for finding node-independent paths in 
> networks
> http://eclectic.ss.uci.edu/~drwhite/working.pdf
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM