# which minimum spanning tree algorithm?

2453
12
01-23-2017 01:17 PM
Occasional Contributor III

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?

Tags (3)
12 Replies
MVP Legendary 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?

Occasional Contributor III

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?

MVP Legendary 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.

Esri Notable Contributor

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

Occasional Contributor III

Thanks guys!

Occasional Contributor III

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

David

MVP Legendary 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

Occasional Contributor III

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.

MVP Legendary 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