which minimum spanning tree algorithm?

2062
12
01-23-2017 01:17 PM
DavidMedeiros
Occasional Contributor II

I have a student who is using the Cost Connectivity tools in ArcGIS for his research who needs to know the specific algorithm being used in the tool to determine the minimum spanning tree.

The ArcGIS online help only refers to the linked wikipedia article for more detail on the method, but there are several algorithms listed there. How can he determine the specific one being used in the arcGIS tool?

How the Cost Connectivity tool works—Help | ArcGIS Desktop 

Minimum spanning tree - Wikipedia 

0 Kudos
12 Replies
DanPatterson_Retired
MVP Esteemed Contributor

I would venture that given the same point and constraints, they 'should' all return the same tree.  Most differentiation is based on the spped at which a solution is determined.  In  Spanning Tree Tools I am pretty sure I use Prim's algorithm since it was easy to implement.  Are you comparing the difference between derivations of the spanning trees? the speed? the complexity that one can ascribe to the analysis?  Perhaps you could elaborate?

timothy_hales-esristaff‌ is there someone on dev team that could answer this?

0 Kudos
DavidMedeiros
Occasional Contributor II

Thanks. I'm not actually the researcher in question but am helping track this down for a PhD candidate who's a patron at my center. I don't think he's doing any comparative analysis between algorithms, rather he's compiling reference information for his works defense where he may very likely be asked, "which min spanning tree algorithm did you use?". The answer can't be "I don't know" or "the one Esri uses" ; )

Esri tools usually post the specific algorithm details on the help pages so I was surprised this wasn't there. Unless it really doesn't matter in practical terms which is used?

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

Hence my qualifications in my response, If someone on the geoprocessing team sees this or Timothy can flag someone, you may have a response.  I suspect the whole analysis isn't a simple variant given the aspects that are covered in the connectivity constraints.  The spanning tree, I suspect, is only one... and a minor one in the process.

0 Kudos
TimothyHales
Esri Notable Contributor

We have reached out to the team that manages this gp tool, so they are aware of the question. Thanks!

0 Kudos
DavidMedeiros
Occasional Contributor II

Thanks guys!

0 Kudos
DavidMedeiros
Occasional Contributor II

Hi all, just checking in to see if there's a response from the GP team on this question? Thanks!

David

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

None to me... probably Prim's... Burkhardt at a pinch.  You could simply pass the buck and indicate that it was not disclosed, since no references were given to the literature which might indicate otherwise, and that is what they usually do if there is some chance that an algorithm can affect outcomes

0 Kudos
DavidMedeiros
Occasional Contributor II

Thanks Dan. I was hoping Timothy would have been able to get the info direct form the GP dev team. I'll pass your suggestion on to the researcher.

0 Kudos
DanPatterson_Retired
MVP Esteemed Contributor

No dice... timothy_hales-esristaff‌ indicated they are aware of the question, but I suspect Dev Summit has attentions turned in another direction.  Maybe someone there could put them on the spot

0 Kudos