[R] Igraph library: How to calculate APSP (shortest path matrix) matrix for a subset list of nodes.

[Csardi Gabor]

It is O(|V|+|E|) to calculate unweighted shortest paths from one vertex 
to all others. It is indeed O(|E|*log|V|) if you have a weighted graph.
But both of these should be reasonable for |V|=25000 and 500 sources, 
you just need a fair amount of memory.

For the details see ?shortest.paths.

Gabor

On Sun, Aug 24, 2008 at 11:06:08PM -0700, Moshe Olshansky wrote:
> I was too optimistic - the complexity is O(E*log(V)) where V is the number of nodes, but since log(25000) < 20 this is still reasonable.
> 
> 
> --- On Mon, 25/8/08, Moshe Olshansky <m_olshansky at yahoo.com> wrote:
> 
> > From: Moshe Olshansky <m_olshansky at yahoo.com>
> > Subject: Re: [R] Igraph library: How to calculate APSP (shortest path matrix) matrix for a subset list of nodes.
> > To: r-help at r-project.org, "dinesh kumar" <barupal at gmail.com>
> > Received: Monday, 25 August, 2008, 3:27 PM
> > As far as I know/remember, if your graph is connected and
> > contains E edges then you can find the shortest distance
> > from any particular vertex to all other vertices in O(E)
> > operations. You can repeat this procedure starting from
> > every node (out of the 500). If you have 100,000 edges this
> > will require about 100,000*500 = 50,000,000 operations
> > (times a small factor) which is very reasonable.
> > 
> > 
> > --- On Mon, 25/8/08, dinesh kumar <barupal at gmail.com>
> > wrote:
> > 
> > > From: dinesh kumar <barupal at gmail.com>
> > > Subject: [R] Igraph library: How to calculate APSP
> > (shortest path matrix) matrix for a subset list of nodes.
> > > To: r-help at r-project.org
> > > Received: Monday, 25 August, 2008, 8:00 AM
> > > Dear R Users,
> > > 
> > > I have a network of 25000 total nodes and a list of
> > 500
> > > node which is a
> > > subset of all nodes. Now I want to calculate the APSP
> > (all
> > > pair shortest
> > > path) matrix only for these 500 nodes.
> > > I would appreciate any help.
> > > Thanks in advance
> > > 
> > > Dinesh
> > > 
> > > -- 
> > > Dinesh Kumar Barupal
> > > Research Associate
> > > Metabolomics Fiehn Lab
> > > UCD Genome Center
> > > 451 East Health Science Drive
> > > GBSF Builidng
> > > University of California
> > > DAVIS
> > > 95616
> > > http://fiehnlab.ucdavis.edu/staff/kumar
> > > 
> > > 	[[alternative HTML version deleted]]
> > > 
> > > ______________________________________________
> > > R-help at r-project.org mailing list
> > > https://stat.ethz.ch/mailman/listinfo/r-help
> > > PLEASE do read the posting guide
> > > http://www.R-project.org/posting-guide.html
> > > and provide commented, minimal, self-contained,
> > > reproducible code.
> > 
> > ______________________________________________
> > R-help at r-project.org mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide
> > http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained,
> > reproducible code.
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

-- 
Csardi Gabor <csardi at rmki.kfki.hu>    MTA RMKI, ELTE TTK