3

For the Cost Connectivity tool in the Spatial Analyst toolbox, what is the algorithm used to compute the minimum spanning tree?

The ArcGIS website includes a general description of how the cost connectivity algorithm works, but it does not specify what minimum spanning tree algorithm is used.

I am asking because I am a PhD student who may use the cost connectivity tool for my research, and it is important that I understand how the tool works.

Edit to clarify based on responses so far: Please note I am specifically interested in the minimum spanning tree algorithm (e.g., Dijkstra). From the Esri website, I understand generally how the Cost Connectivity tool otherwise works.

2

Below is an illustration of how the algorithm works as provided by Esri. I'm pulling in my comment from below to also add:

Esri provides an illustration, they are not being specific about the MST used, only stating "optimum network (the minimum spanning tree) is the desired output." Furthermore, Esri is being ambiguous "The minimum spanning tree is determined using graph theory to connect the vertices (the regions) in the most effective (least cost) way possible." Nonetheless, Esri is trying to show the " steps are conceptually how the Cost Connectivity algorithm works:"

Esri provides an overview of Cost Connectivity

The two inputs (regions and cost data) are shown on the left side of the image, and right side of the image shows the output least-cost network displayed over the regions.

enter image description here

The minimum spanning tree is described:

The minimum spanning tree is calculated from the graph representation of the paths to determine the least-cost path network necessary to travel between the regions.

Esri also provides How the Cost Connectivity tool works

Which provides a section focused on How the cost connectivity algorithm works

The input sources and cost surface are identified.

In the graphic below, the input regions (the colored polygons) are displayed over the cost surface layer.

enter image description here

A Cost Allocation is performed.

In the graphic below, the input regions are displayed over the associated cost allocation layer. The value of each cell in the allocation raster is that of the particular region that can be reached with the cheapest (lowest) accumulated cost.

enter image description here

Cost paths are created between each region and its neighboring cost region.

In the graphic below, the input regions and the least-cost paths from each region to its neighboring cost region (magenta lines) are displayed over the associated cost allocation layer.

enter image description here

The regions and the resulting paths are converted to a graph (in graph theory). In the translation, the regions are the vertices and the paths are the edges. The accumulative cost for the path is the weight for the edge.

Conceptually, the translation of the regions and paths into graph theory can be represented by the following illustration. The numbered circles are the vertices (the regions) and the connecting lines between the vertices are the edges (the least-cost paths). The weights for the edges are the accumulative cost for the paths. In the illustration, the higher the cost, the thicker the line.

enter image description here

Esri also recommends to have an understanding of graph theory:

To fully understand how this tool works, it is recommended that you have some basic understanding of graph theory. Many resources are available for this, but you can start with the Wikipedia entry at Graph Theory.

The minimum spanning tree is determined using graph theory to connect the vertices (the regions) in the most effective (least cost) way possible. More information about minimum spanning trees is available online, such as from the Wikipedia entry at Minimum Spanning Tree

The spatial representation of the regions and the paths from the minimum spanning tree are mapped back to an output feature class.

In the graphic below, the input regions and the least-cost path network from the minimum spanning tree (magenta color) are displayed over the associated cost surface layer.

enter image description here

Comparing the paths when using just the Cost Distance and Cost Path tools (left) against the Cost Connectivity tool (right)

enter image description here

| improve this answer | |
  • This doesn't answer the question about MST algorithm – FelixIP Jan 10 '17 at 21:26
  • I believe it does, because MST algorithm is determined by identifying "A minimum spanning tree would be one with the lowest total cost, thus would represent the least expensive path for laying the cable." – whyzar Jan 10 '17 at 21:35
  • There are multiple algorithms like Kruskal, Prim etc en.m.wikipedia.org/wiki/Minimum_spanning_tree – FelixIP Jan 10 '17 at 22:18
  • 1
    Yes, there are multiple algorithms, I included that same link as recommended by Esri. Esri provides an illustration, they are not being specific about the MST used, only stating "optimum network (the minimum spanning tree) is the desired output." Furthermore, Esri is being ambiguous "The minimum spanning tree is determined using graph theory to connect the vertices (the regions) in the most effective (least cost) way possible." Nonetheless, Esri is trying to show the " steps are conceptually how the Cost Connectivity algorithm works:" – whyzar Jan 10 '17 at 22:35
  • Thanks for helping. @FelixIP is correct that I am looking for the specific MST algorithm. I understand the Esri's main Cost Connectivity webpage (discussed above) doesn't specify which algorithm was used, which is why I originally posted the question. – user89413 Jan 11 '17 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.