1

I am looking to run MST on some vectors with geometries and cost. I have not been able to find a one stop python/arcpy method to do so. The closest I've gotten is by using the code in the comment by dkweins at:

https://community.esri.com/blogs/dan_patterson/2017/01/31/spanning-trees

This code does not have a place to assign weight to the graph.

  1. Is there a package MST tool in Arc where I can just input a set of points and receive the paths out in consideration of cost.

  2. If no (1), what can I do to the linked code to allow this functionality?

I have tried adding a cost field to the search cursor but I can't figure out how to append this info to the dictionary Q. If I could, the edit to addToTree should be pretty straight forward.

ORIGINAL:

def addToTree(F,Q,sr):
    min_dist = float("inf") # set to infinity
    for fk,fv in F.iteritems(): # loop through tree vertices
        for qk,qv in Q.iteritems(): # loop through non-tree vertices
            dist = fv['G'].distanceTo(qv['G']) # calculate distance
            if dist < min_dist: # if distance is less than current minimum, remember
                fk_fv_qk_qv = [fk,fv['G'],qk,qv['G']]
                min_dist = dist
    F[fk_fv_qk_qv[2]] = {'G': fk_fv_qk_qv[3]} # add to tree vertices
    del Q[fk_fv_qk_qv[2]] # delete from non-tree vertices
    return arcpy.Polyline(arcpy.Array([fk_fv_qk_qv[1].centroid,fk_fv_qk_qv[3].centroid]),sr) # return new line

fc = 'points' # points feature class
sr = arcpy.Describe(fc).spatialReference # spatial ref
Q = {str(i[0]):{'G':i[1]} for i in arcpy.da.SearchCursor(fc,['OID@','SHAPE@'],spatial_reference=sr)} # non-tree vertices
F = {} # empty tree vertices
lines = [] # placeholder for lines
q_cur = Q.keys()[0] # get first non-tree vertex
F[q_cur] = Q[q_cur] # transfer to tree vertices
del Q[q_cur] # delete from non-tree vertices
while len(Q)>0: # do until all non-tree vertices assigned to tree
    output = addToTree(F,Q,sr) # add a vertex via function
    lines.append(output) # remember line
arcpy.CopyFeatures_management(lines,r'in_memory\lines') # write lines
2
  • You could try Dijkstra's algorithm using your weight instead of length, an example in python is here dev.to/mxl/… and here gist.github.com/econchick/4666413 . The example you have shown is so python it's almost unreadable, I'm not even going to try. Oct 29 '19 at 23:59
  • I am having a hard time reading it as well! But it is the only code I have found so far that is close to what I need and was hoping to edit it to my needs. I have Dijkstra all worked out, looking to test some theories using MST.
    – D_C
    Oct 30 '19 at 2:17
1

I was unable to find a python solution but was able to get the CostConnectivity tool of ArcGIS Pro to work.

https://pro.arcgis.com/en/pro-app/tool-reference/spatial-analyst/cost-connectivity.htm

1
Is there a package MST tool in Arc where I can just input a set of points and receive the paths out in consideration of cost.

The Network Analyst extension is the package for this type of analysis. Of course, you need to specify how the points are connected. Are they connected via road network? Are they connected based on a nearest neighbor structure?

These are some alternative python only options. You need to build the graph based on how the distances are to be calculated. For example, if it is a road network, you need to create a network structure (the graph) based on that road, then place the points in that graph.

Probably the easiest would be to use the networkx library and create a Graph with a weight attribute (edge or node).

https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html

But that requires installing the library which may not be an option for you.

I can't remember if scipy is installed with the base ArcGIS python, but there is also an option with their sparse graphs.

https://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html

Finally, numpy is installed with arcpy, and this is just one possible implementation you could reference using a numpy array to store the graph.

https://medium.com/quick-code/prims-algorithm-with-numpy-arrays-a9ea3d3f112a

In addition, Pysal may give you the base functionality to roll your own MST function: https://pysal.readthedocs.io/en/latest/api.html

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.