Re: [igraph] how to plot a very basic MST with igraph

[Gábor Csárdi]

On Wed, Mar 5, 2014 at 1:50 PM, Steve Boudreault <address@hidden> wrote:

>
> Maybe you want this:
> http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
> Do you?
>

Yes, this is correct.

Anyway, igraph is not optimal for this, then. igraph does MSTs, not EMSTs. As I wrote in my very first email, you can create a full graph, set edge weights to Euclidean distances, and then you can use minimum.spanning.tree() in igraph. But this is very suboptimal. It might work if you have a couple of hundred points, maybe a couple of thousands.

Btw. this naive algorithm is the first one discussed at the wikipedia page:

http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree#Algorithms_for_computing_EMSTs_in_two_dimensions

 

In the link you gave me, I see the following sentence : << [...] an EMST

(Euclidean minimum spanning tree) connects a set of dots using lines such
that the total length of all the lines is minimised and any dot can be
reached from any other by following the lines. >>

Isn't that the rule? i.e. that my objects in the RA vs DEC place are
connected such that the total length of all the lines is minimised?

So you expected us to guess that you wanted an EMST, without you telling us? :)

I can add that all my objects have the same weight.

I have no idea what you mean. You don't need to assign weights to your objects. Please read that wikipedia page.

G. 

 

>
> On Wed, Mar 5, 2014 at 11:17 AM, Steve Boudreault
> <address@hidden
>> wrote:
>> > But I'd prefer you tell us want you want to do, and then we don't
need
>> > to
>> > guess.
>> Please look at the following image :
>> http://inspirehep.net/record/833443/files/mst.png
>> These are "minimum spanning tree" (right?) of stars distributed in X (i.e.
>> right ascension, RA) and Y (i.e. declination, DEC). You have this for
three open clusters : IC2391, M34, M11.
> Again. The minimum spanning trees in igraph are defined for graphs
(=networks), not for points:
> http://en.wikipedia.org/wiki/Minimum_spanning_tree
> Maybe you want this:
> http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
> Do you?
> This *is* what I want to do. I want to do a plot like this.
> This is not an explanation, I am sorry. What is the rule to connect the
dots? Maybe this is evident for people in your field, but not to me. G.
> [...]

--
============================================================
Steve Boudreault, Ph.D.
CNRS UMR 8111 / GÉPI
Bâtiment 11 - Hipparque     Email: address@hidden
Observatoire de Paris       Phone : +33 (0) 145077868
5 Place Jules Janssen       Fax: +33 (0) 145077878
92190 Meudon, France        Mobile : +33 (0) 604530082
============================================================