topic Re: which minimum spanning tree algorithm? in Geoprocessing Questions

which minimum spanning tree algorithm?

DavidMedeiros — Mon, 23 Jan 2017 21:17:51 GMT

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

Re: which minimum spanning tree algorithm?

DanPatterson_Retired — Mon, 23 Jan 2017 21:32:40 GMT

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?

Re: which minimum spanning tree algorithm?

DavidMedeiros — Mon, 23 Jan 2017 21:50:26 GMT

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?

Re: which minimum spanning tree algorithm?

DanPatterson_Retired — Mon, 23 Jan 2017 22:25:00 GMT

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.

Re: which minimum spanning tree algorithm?

TimothyHales — Tue, 24 Jan 2017 14:44:50 GMT

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

Re: which minimum spanning tree algorithm?

DavidMedeiros — Tue, 24 Jan 2017 18:23:28 GMT

Thanks guys!

Re: which minimum spanning tree algorithm?

DavidMedeiros — Thu, 09 Feb 2017 18:11:08 GMT

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

David

Re: which minimum spanning tree algorithm?

DanPatterson_Retired — Thu, 09 Feb 2017 18:37:54 GMT

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

Re: which minimum spanning tree algorithm?

DavidMedeiros — Thu, 09 Feb 2017 18:49:02 GMT

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.

Re: which minimum spanning tree algorithm?

DanPatterson_Retired — Sun, 12 Feb 2017 18:44:04 GMT

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

Re: which minimum spanning tree algorithm?

TimothyHales — Sun, 12 Feb 2017 19:23:19 GMT

The https://community.esri.com/community/events/fedgis?sr=search&searchId=9d32edec-af5e-4c1b-b223-ba63963d0b6b&searchIndex=0‌ and the DC DevSummit is this week, so that may be the reason for the delay in response. I will follow up with them.

Re: which minimum spanning tree algorithm?

KevinJohnston1 — Tue, 14 Feb 2017 23:00:08 GMT

Esri’s Cost Connectivity tool currently determines the minimum spanning tree output based upon Kruskal’s algorithm.

Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem". Proceedings of the American Mathematical Society. 7: 48–50. doi:10.1090/S0002-9939-1956-0078686-7.

Kevin J

Esri Development

Re: which minimum spanning tree algorithm?

DanPatterson_Retired — Tue, 14 Feb 2017 23:11:26 GMT

Thanks Kevin...

good to know ..... now for the next question

...what is the difference between them

Kruskal vs Prim's specifically their references within