Minimum Spanning Tree

This is the updated version of my MST code from 2012. After over a hundred hours of Rhinocommon and Grasshopper SDK studies, and lots of dead ends, I was finally able to calculate the minimum spanning tree of any given curve network in Grasshopper. Problems like these are interesting to me because of their clear logic and diverse areas of applications in design. I tried to simulate Dijkstra’s, Kruskal’s, and Prim’s algorithms, but no chance. There are similar solutions such as Shortest Walk and SpiderWeb which are much more faster and professional than mine. I chose a reverse-delete algorithm. The logic is simple: take the longest connection in the set. Then, see if you delete the connection, and whether the two nodes are still connected or not. If deleting that connection does not remove the two nodes, then delete it and continue from the next longest connection.

This Grasshopper definition includes one component written in VB.net language and it generates the Minimum Spanning Tree of a given curve network (a list of connected lines) in 2D and 3D. I added a standard Delaunay Triangulation to test it in the Grasshopper definition. The only input of the code is the list of lines. The outputs are the minimum spanning tree as line objects, and the step-by-step explanation texts of the operation. The code is using native Grasshopper components. Thus, no add-ons are necessary for it to work. This animation visualizes the outcome with a MultiPipe.

Dim i, j As Integer
Dim message As String
Dim count As Integer = lines.Count()
Dim connect As New DataTree (Of Object)
Dim point_list As New List (Of point3d)
For i = 0 To count - 1
	Dim path As New GH_Path(i)
	Dim temp_pointA As point3d
	Dim temp_pointB As point3d
	temp_pointA = lines(i).pointatnormalizedlength(0)
	temp_pointB = lines(i).pointatnormalizedlength(1)
	Dim flag As Boolean = False
	Dim which_point As Integer
	which_point = -1
	For j = 0 To point_list.Count() - 1
		If (point_list(j) = temp_pointA) Then
			flag = True
			which_point = j
		End If
	Next
	If (flag = True) Then
		connect.insert(which_point, path, 0)
	End If
	If (flag = False) Then
		point_list.add(temp_pointA)
		connect.insert(point_list.count() - 1, path, 0)
	End If
	which_point = -1
	flag = False
	For j = 0 To point_list.Count() - 1
		If (point_list(j) = temp_pointB) Then
			flag = True
			which_point = j
		End If
	Next
	If (flag = True) Then
		connect.insert(which_point, path, 1)
	End If
	If (flag = False) Then
		point_list.add(temp_pointB)
		connect.insert(point_list.count() - 1, path, 1)
	End If
	connect.insert(temp_pointA.distanceto(temp_pointB), path, 2)
	connect.insert("unchecked", path, 3)
Next

Dim mspt As DataTree (Of Object)
mspt = connect

Dim maxlen As Double
Dim maxidx As Integer

For j = 0 To mspt.branchcount() - 1
	maxlen = 0
	maxidx = 0
	message = "*** Started iteration # " + System.Convert.ToString(j)
	Print(message)

	For i = 0 To mspt.branchcount() - 1
		If (mspt.branch(i).item(2) > maxlen) And (mspt.branch(i).item(3) = "unchecked") Then
			maxlen = mspt.branch(i).item(2)
			maxidx = i
		End If
	Next
	message = "Longest edge is " + System.Convert.ToString(maxlen) + " at connection " + System.Convert.ToString(maxidx)
	Print(message)
	Dim temp_indexA As Integer
	Dim temp_indexB As Integer
	temp_indexA = mspt.branch(maxidx).item(0)
	temp_indexB = mspt.branch(maxidx).item(1)

	message = "Nodes of this connection are " + System.Convert.ToString(temp_indexA) + " and " + System.Convert.ToString(temp_indexB)
	Print(message)

	Dim temp_resultA, temp_resultB As Boolean
	temp_resultA = isConnected(mspt, temp_indexA, point_list.count(), maxidx)
	If (temp_resultA = True)
		message = "Deleting connection " + System.Convert.ToString(maxidx) + " did not break connectivity of node " + System.Convert.ToString(temp_indexA)
	Else
		message = "Deleting connection " + System.Convert.ToString(maxidx) + " DID break connectivity of node " + System.Convert.ToString(temp_indexA)
	End If
	Print(message)

	temp_resultB = isConnected(mspt, temp_indexB, point_list.count(), maxidx)
	If (temp_resultB = True)
		message = "Deleting connection " + System.Convert.ToString(maxidx) + " did not break connectivity of node " + System.Convert.ToString(temp_indexB)
	Else
		message = "Deleting connection " + System.Convert.ToString(maxidx) + " DID break connectivity of node " + System.Convert.ToString(temp_indexB)
	End If
	Print(message)

	If (temp_resultA = True) And (temp_resultB = True) Then
		message = "Therefore, connection " + System.Convert.ToString(maxidx) + " is deleted from the graph"
		Print(message)
		mspt.branch(maxidx).item(3) = "deleted"
	Else
		message = "Connection " + System.Convert.ToString(maxidx) + " is important and remained"
		mspt.branch(maxidx).item(3) = "approved"
	End If

Next

Dim length As Double = 0

Dim finale As New List (Of line)
For i = 0 To mspt.branchcount() - 1
	If (mspt.branch(i).item(3) = "approved") Then
		finale.add(New Rhino.Geometry.Line(point_list(mspt.branch(i).item(0)), point_list(mspt.branch(i).item(1))))
		length = length + (point_list(mspt.branch(i).item(0)).distanceto(point_list(mspt.branch(i).item(1))))
	End If
Next

conn = finale
node = point_list
mst = mspt

message = "Found minimum spanning tree of " + System.Convert.ToString(point_list.count()) + " points, at total length of " + System.Convert.ToString(length)
Print(message)