January 26, 2021, 12:01:02 PM

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

Offline 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)))
  138.                         g.edges.addlast edge.Create(v,v2)
  139.                         hasedge[n*Min(v.id,v2.id)+Max(v.id,v2.id)] = 1
  140.                 EndIf
  141.                
  142.                 g.vertices.addlast v
  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)
  171.                 g.edges.addlast e
  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
  202.                 t.vertices.addlast v
  203.                 'mark on the vertex which tree it belongs to
  204.                 v.t = t
  205.                 'add the tree to the forest
  206.                 forest.addlast t
  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
  239.                         t1.edges.addlast e
  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
  245.                                 t1.vertices.addlast v
  246.                         Next
  247.                        
  248.                         'add all of t2's edges to t1
  249.                         For e:edge = EachIn t2.edges
  250.                                 t1.edges.addlast e
  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


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal