# Storing a geographic minimum spanning tree with PyShp

I have a list of geographic coordinates (longitudes, latitudes in decimal degrees) as follows:

``````-72.9833,10.6167
-63.1167,10.55
-63.1167,7.91667
-65.9667,10.3167
-67.4333,8.93333
-68.4,10.6167
-70.6667,9.53333
-72.8667,9.83333
-72.9833,10.6167
-60.5,3.93333
-56.4833,3.1
-78.9333,8.38333
-79.4333,9.15
-81.0167,7.66667
-81.1833,7.51667
``````

and a list of edges connecting these points with a minimum spanning tree (computed using Prim's algorithm) as shown below:

``````0 0
5 1
4 5
11 5
10 11
14 10
3 14
13 3
15 13
8 4
7 8
12 13
2 12
9 2
6 9
``````

I am trying to save the minimum spanning tree as a shapefile using the PyShp library (so that the MST can be displayed on a GIS).

Here is my code so far:

``````    import numpy as np
from mpl_toolkits.basemap import Basemap
import matplotlib.pyplot as plt
import shapefile

lon = coords[:,0]
lat = coords[:,1]

edges = np.array(edges, dtype=np.int32)

# Create map
map = Basemap()

map.drawcoastlines()
map.drawcountries()
map.drawmapboundary()
x,y = map(lon,lat)
map.plot(x,y,'ro')
plt.title('Minimum Spanning Tree')

# Ths MST plotting algorithm works!
edge_list = []
n = len(edges)
for i in range(n):
t = edges[i,0]-1
u = edges[i,1]-1
x = [coords[t,0], coords[u,0]]
y = [coords[t,1], coords[u,1]]
#edge_list.append(x)
#edge_list.append(y)
#edge_list.append((x,y))
edge_list.append([(x[0],y[0]), (x[1], y[1])])
plt.plot(x,y,'-r')
plt.show()

# Sort the list of edges
edge_list = list(sorted(edge_list))

# Save the minimum spanning tree
w = shapefile.Writer()
w.line(parts=[edge_list])
w.field("COMMON_ID", 'C')
w.record("Point")
w.save("mst")
``````

The code above correctly plots the points and draws the minimum spanning tree connecting them, as shown in the figure below:

But the tree is not being correctly saved in the shapefile, as shown in the figure below (displayed by QGIS):

An alternative would be to have the tree saved as a KML file (compatible Google Earth), which could then be converted into a shapefile using the ogr2ogr tool of GDAL. I have not tried this as yet.

Any hints?

UPDATE 1: Following the suggestion of Marc Pfister (see comments below), I stored the coordinates as lists of tuples in edge_list: edge_list.append((x, y)). The results are shown below:

``````[([-61.049999999999997, -63.116666666699999], [10.4, 10.550000000000001]), ([-63.116666666699999, -63.116666666699999], [7.9166666666700003, 10.550000000000001]), ([-63.116666666699999, -65.966666666699993], [10.550000000000001, 10.3166666667]), ([-67.433333333299998, -65.966666666699993], [8.9333333333299993, 10.3166666667]), ([-67.433333333299998, -68.400000000000006], [8.9333333333299993, 10.6166666667]), ([-70.666666666699996, -68.400000000000006], [9.5333333333300008, 10.6166666667]), ([-70.666666666699996, -72.866666666699999], [9.5333333333300008, 9.8333333333299997]), ([-72.866666666699999, -72.983333333299996], [9.8333333333299997, 10.6166666667]), ([-63.116666666699999, -60.5], [7.9166666666700003, 3.9333333333299998]), ([-56.483333333300003, -60.5], [3.1000000000000001, 3.9333333333299998]), ([-78.933333333299998, -72.866666666699999], [8.3833333333300004, 9.8333333333299997]), ([-79.433333333299998, -78.933333333299998], [9.1500000000000004, 8.3833333333300004]), ([-79.433333333299998, -81.016666666700004], [9.1500000000000004, 7.6666666666700003]), ([-81.183333333299998, -81.016666666700004], [7.5166666666699999, 7.6666666666700003])]
``````

The shapefile created by storing these data is still uglier than the previous one.

UPDATE 2: Fixed the storing of the (x,y) tuples in edge_list. It now works fine! Have updated the code above to include this fix.

• Your updated edge list is ((x,x), (y,y), (x,x), (y,y)...) Aug 31, 2017 at 21:22
• Sure, in a rush I haven't noticed. Now I fixed it. It works! Thanks! Aug 31, 2017 at 21:42

Looking at the second graphic it looks like `edge_list` is all the coordinate values mixed together and sorted in order, not coordinate pairs. For the shapefile geometry you should be appending `(x,y)` tuples to a list.
Pyplt wants two lists: `[x1,x2,x3]` and `[y1,y2,y3]`
Pyshp wants one list of a list of coordinate pairs: `[[[x1,y1], [x2,y2], [y3,y3]]]`