January 26, 2021, 12:01:02 PM

### Author Topic: [bmx] Minimum spanning tree by Warpy [ 1+ years ago ]  (Read 483 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] Minimum spanning tree by Warpy [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
Title : Minimum spanning tree
Author : Warpy
Posted : 1+ years ago

Description : Given a connected graph of vertices and edges, <a href="http://en.wikipedia.org/wiki/Kruskals_algorithm" target="_blank">Kruskal's algorithm[/url] will find a minimum spanning tree.

this program will generate a random graph, then step through kruskal's algorithm, describing each step.
Some background:
----------------
- a graph is a set of vertices and a set of edges.
- a vertex is just a point in space
- an edge connects two vertices.
- a "weighted" edge also has a number associated with it. This could be the distance between its two vertices, for example.
- a graph is "connected" if it is possible to trace a path from each vertex to any other vertex.
- a tree is a graph with no loops in it - that is, it isn't possible to trace a path along the edges starting and ending at the same vertex, and which never uses any edge twice.
- a spanning tree of a graph is a connected tree which contains every vertex from the original graph, only using the edges from the original graph.

Summary of algorithm:
---------------------

- start with a graph consisting of a set of vertices connected by edges. The graph must be connected - that is, there must be a path from each vertex to any other vertex
- for each vertex, create a tree containing only that vertex. Mark on the vertex which tree it belongs to. The set of all the trees is called the "forest".
- the idea is that by joining these trees together when there is an edge connecting them, we will end up with a spanning tree.
- if we add the edges in order of length, that will ensure that the resulting tree is a minimum spanning tree.
- sort the edges of the graph by length (or weight).
- starting with the shortest edge:
- - if the two vertices that the edge connects belong to the same tree, forget about this edge and move on to the next one.
- - if the two vertices that the edge connects belong to different trees, merge the two trees together, and add this edge to it.
- when a tree contains every vertex in the graph, you have created a minimum spanning tree and can end the algorithm.

Code :
Code: BlitzMax
1. 'Kruskal's algorithm
2. '
3. 'this program will generate a random graph, then step through kruskal's algorithm, describing each step.
4. '
5. '
6. '-------------------
7. 'Some background:
8. ' - a graph is a set of vertices and a set of edges.
9. ' - a vertex is just a point in space
10. ' - an edge connects two vertices.
11. ' - a "weighted" edge also has a number associated with it. This could be the distance between its two vertices, for example.
12. ' - a graph is "connected" if it is possible to trace a path from each vertex to any other vertex.
13. ' - a tree is a graph with no loops in it - that is, it isn't possible to trace a path along the edges starting and ending at the same vertex, and which never uses any edge twice.
14. ' - a spanning tree of a graph is a connected tree which contains every vertex from the original graph, only using the edges from the original graph.
15. '
16. '-------------------
17. 'Summary of algorithm:
18. ' - start with a graph consisting of a set of vertices connected by edges. The graph must be connected - that is, there must be a path from each vertex to any other vertex
19. ' - for each vertex, create a tree containing only that vertex. Mark on the vertex which tree it belongs to. The set of all the trees is called the "forest".
20. ' - the idea is that by joining these trees together when there is an edge connecting them, we will end up with a spanning tree.
21. ' - if we add the edges in order of length, that will ensure that the resulting tree is a minimum spanning tree.
22.
23. '
24. ' - sort the edges of the graph by length (or weight).
25. ' - starting with the shortest edge:
26. ' - - if the two vertices that the edge connects belong to the same tree, forget about this edge and move on to the next one.
27. ' - - if the two vertices that the edge connects belong to different trees, merge the two trees together, and add this edge to it.
28. ' - when a tree contains every vertex in the graph, you have created a minimum spanning tree and can end the algorithm.
29.
30.
31.
32. 'a vertex is a point on the graph
33. 'for the purposes of Kruskal's algorithm, each vertex needs to keep track of which tree in the forest it belongs to
34. 'the id property is just for convenience, so I can describe each step the algorithm makes
35. Type vertex
36.         Field x#,y#
37.         Field id
38.         Field t:graph
39.
40.         Method draw()
41.                 DrawOval x-5,y-5,10,10
42.                 DrawText "Vertex: "+id,x,y+5
43.                 If t
44.                         DrawText "Tree: "+t.id,x,y+18
45.                 EndIf
46.         End Method
47. End Type
48.
49. 'an edge connects two vertices together
50. Type edge
51.         Field a:vertex
52.         Field b:vertex
53.         Field length#
54.
55.         Function Create:edge(a:vertex,b:vertex)
56.                 e:edge = New edge
57.                 e.a=a
58.                 e.b=b
59.                 e.length = Sqr( (a.x-b.x)^2 + (a.y-b.y)^2 )
60.                 Return e
61.         End Function
62.
63.         'this method allows edges to be sorted by length
64.         Method Compare(o2:Object)
65.                 e2:edge = edge(o2)
66.
67.                 Return Sgn(length-e2.length)
68.         End Method
69.
70.         Method draw()
71.                 DrawLine a.x,a.y,b.x,b.y
72.         End Method
73. End Type
74.
75. 'a graph is a set of vertices and a set of edges
76. 'again, the id property and red/green/blue are just for convenience
77. Type graph
78.         Field vertices:TList
79.         Field edges:TList
80.         Field id
81.         Field red,green,blue
82.
83.         Method New()
84.                 vertices = New TList
85.                 edges = New TList
86.
87.
88.                 'generate a random colour
89.                 acc = 255
90.                 red = Rand(0,acc)
91.                 acc :- red
92.                 green = Rand(0,acc)
93.                 acc :- green
94.                 blue = acc
95.
96.         End Method
97.
98.         Method draw()
99.                 SetColor red,green,blue
100.                 For e:edge=EachIn edges
101.                         e.draw
102.                 Next
103.
104.                 SetColor 255,255,255
105.                 For v:vertex = EachIn vertices
106.                         v.draw
107.                 Next
108.         End Method
109. End Type
110.
111.
112. 'this function creates a random graph
113. 'it isn't directly relevant to Kruskal's algorithm, so ignore it if you like
114. Function randomGraph:graph()
115.
116.         'create a graph
117.         g:graph = New graph
118.
119.         'decide how many vertices it should contain
120.         n = Rand(5,15)
121.
122.         'this array will keep track of whether there is already an edge connecting two vertices
123.         'kruskal's algorithm will work if there are repeated edges, but to make the graphical description easier to understand, I don't want any.
124.         Local hasedge[n*n]
125.
126.         'create the vertices
127.         For c=0 To n-1
128.                 v:vertex = New vertex
129.
130.                 'arrange the vertices around an ellipse so they're easy to differentiate
131.                 v.x = 400+Cos(360*(c+Rnd(0.5))/n)*300
132.                 v.y = 300+Sin(360*c/n)*200
133.                 v.id = c
134.
135.                 'create an edge between this vertex and a previously created one, to make sure that the graph is connected
136.                 If c
137.                         v2:vertex = vertex(g.vertices.valueatindex(Rand(0,c-1)))
139.                         hasedge[n*Min(v.id,v2.id)+Max(v.id,v2.id)] = 1
140.                 EndIf
141.
143.
144.         Next
145.
146.         'at this point, the graph is a tree because of the way I added edges before.
147.         'So, add a few more edges
148.         For c=1 To n/2
149.
150.                 'pick a random vertex
151.                 i=Rand(0,n-1)
152.
153.                 'pick another one, but make sure it's not the same as the first one
154.                 j=Rand(0,n-2)
155.                 If j>=i Then j:+1
156.
157.                 'if there's already an edge between i and j, pick a new pair of vertices
158.                 'I'm assuming it's not possible for this algorithm to end up creating edges between every pair of vertices, so this while loop will terminate.
159.                 While hasedge[n*Min(i,j)+Max(i,j)]
160.                         i=Rand(0,n-1)
161.                         j=Rand(0,n-2)
162.                         If j>=i Then j:+1
163.                 Wend
164.
165.                 'get the vertex objects corresponding to i and j
166.                 a:vertex = vertex(g.vertices.valueatindex(i))
167.                 b:vertex = vertex(g.vertices.valueatindex(j))
168.
169.                 'create an edge between the picked vertices and add it to the graph
170.                 e:edge = edge.Create(a,b)
172.
173.                 'record that there is now an edge between these vertices
174.                 hasedge[n*Min(i,j)+Max(i,j)] = 1
175.         Next
176.
177.         'just for convenience when describing the algorithm graphically
178.         g.red = 50
179.         g.green = 50
180.         g.blue = 50
181.
182.         Return g
183. End Function
184.
185. 'this function will compute the minimum spanning tree for a graph
186. Function spanningTree:graph(g:graph)
187.
188.         'the forest is the set of all trees. It should be reduced down to one tree by the time the algorithm finishes.
189.         forest:TList = New TList
190.
191.         describe g,forest,Null,"Start with this graph. Create a tree for each vertex."
192.         numgraphs = 0
193.         For v:vertex=EachIn g.vertices
194.                 describe g,forest,Null,"Create a tree for each vertex."
195.
196.                 'create a tree
197.                 t:graph = New graph
198.                 t.id=numgraphs
199.                 numgraphs:+1
200.
201.                 'add the vertex to it
203.                 'mark on the vertex which tree it belongs to
204.                 v.t = t
205.                 'add the tree to the forest
207.         Next
208.
209.         describe g,forest,Null,"Now we can begin. Work through the edges, starting with the shortest one."
210.
211.         'sort the edges by length
212.         g.edges.sort()
213.
214.         'for each edge in the graph:
215.         For e:edge=EachIn g.edges
216.                 txt\$="Vertices "+e.a.id+" and "+e.b.id
217.                 If e.a.t = e.b.t
218.                         txt:+" are in the same tree, so discard this edge."
219.                 Else
220.                         txt:+" are in different trees, so merge the trees and add this edge."
221.                 EndIf
222.                 describe g,forest,e,txt
223.
224.                 'if the two vertices this edge connects belong to different trees, then we can merge them.
225.                 If e.a.t <> e.b.t
226.
227.                         t1:graph = e.a.t
228.                         t2:graph = e.b.t
229.
230.                         'I want to keep the tree with the most edges in it, so the least colour change happens on scree
231.                         'this bit isn't part of kruskal's algorithm, but it makes the graphical description easier to follow
232.                         If t2.edges.count() > t1.edges.count()
233.                                 t:graph = t1
234.                                 t1 = t2
235.                                 t2 = t
236.                         EndIf
237.
238.                         'add the edge to t1
240.
241.                         'add all of t2's vertices to t1
242.                         'remember to mark on each vertex that it now belongs to t1
243.                         For v:vertex=EachIn t2.vertices
244.                                 v.t = t1
246.                         Next
247.
248.                         'add all of t2's edges to t1
249.                         For e:edge = EachIn t2.edges
251.                         Next
252.
253.                         'remove t2 from the forest, because all of its contents are now in t1
254.                         forest.remove t2
255.
256.                         'if there is only one tree left in the forest, then it must be a spanning tree, so the algorithm can finish
257.                         If forest.count() = 1
258.                                 Print forest.count()
259.                                 describe Null,forest,Null,"All vertices are in the same tree now, so this is a minimum spanning tree."
260.
261.                                 Return t1
262.                         EndIf
263.                 EndIf
264.         Next
265. End Function
266.
267. 'this function describes a step of the algorithm graphically
268. Function describe(g:graph=Null,forest:TList=Null,e:edge=Null,txt\$="")
269.         While Not KeyHit(KEY_SPACE)
270.                 If KeyHit(KEY_ESCAPE) Or AppTerminate()
271.                         End
272.                 EndIf
273.
274.                 If g
275.                         SetLineWidth 1
276.                         g.draw
277.                 EndIf
278.
279.                 If forest
280.                         SetLineWidth 2
281.                         For t:graph=EachIn forest
282.                                 t.draw
283.                         Next
284.                 EndIf
285.
286.                 If e
287.                         SetColor 255,255,255
288.                         SetLineWidth 3
289.                         e.draw
290.                 EndIf
291.
292.                 SetColor 255,255,255
293.                 DrawText txt,0,0
294.                 DrawText "Press SPACE to continue.",0,15
295.
296.                 Flip
297.                 Cls
298.         Wend
299. End Function
300.
301. Graphics 800,600,0
302. SeedRnd MilliSecs()
303.
304. While 1
305.         g:graph = randomGraph()
306.         tree:graph = spanningTree(g)
307. Wend