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

[Moshe Olshansky]

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.