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

[jordi torrents]

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.

Salut!

[1] Fast approximation algorithms for finding node-independent paths in networks
http://eclectic.ss.uci.edu/~drwhite/working.pdf