B4J Tutorial [WebApp] Minimum Spanning Tree

I took Ilan's challenge and implemented a minimum spanning tree algorithm.

You can see the solution online: https://b4x.com:51041/mst/index.html

The algorithm used is Prim's algorithm: https://www.ics.uci.edu/~eppstein/161/960206.html

This example uses three JavaScript functions to draw on the canvas.

Code:

'WebSocket class
Sub Class_Globals
   Private ws As WebSocket
   Private cvs, btnClear As JQueryElement
   Private offsetX, offsetY As Double
   Type MST_Point(x As Double, y As Double)
   Type MST_Edge (p1 As MST_Point, p2 As MST_Point, distance As Double)
   Private points As Map
   Private edges As List
End Sub

Public Sub Initialize
   points.Initialize
   edges.Initialize
End Sub

Private Sub btnClear_Click (Params As Map)
   ws.RunFunction("Clear", Null)
   points.Clear
   edges.Clear
End Sub

Private Sub WebSocket_Connected (WebSocket1 As WebSocket)
   ws = WebSocket1
   Dim m As Map = cvs.RunMethodWithResult("offset", Null).Value
   offsetX = m.Get("left")
   offsetY = m.Get("top")
End Sub

Sub cvs_Click (Params As Map)
   Dim x As Double = Params.Get("pageX") - offsetX
   Dim y As Double = Params.Get("pageY") - offsetY
   Dim p As MST_Point
   p.Initialize
   p.x = x
   p.y = y
   AddPoint(p)
End Sub

Private Sub AddPoint(NewPoint As MST_Point)
   For Each p As MST_Point In points.Keys
     Dim e As MST_Edge
     e.Initialize
     e.p1 = NewPoint
     e.p2 = p
     e.distance = CalcDistance(e)
     edges.Add(e)
   Next
   points.Put(NewPoint, "")
   'sort the edges
   edges.SortType("distance", True)
   ws.RunFunction("Clear", Null)
   Dim tree As Map
   tree.Initialize
   tree.Put(NewPoint, "")
   Do While tree.Size < points.Size
     'find the smallest edge connecting T to G-T
     For Each e As MST_Edge In edges
       Dim p1Inside As Boolean = tree.ContainsKey(e.p1)
       Dim p2Inside As Boolean = tree.ContainsKey(e.p2)
       If p1Inside <> p2Inside Then
         'relevant edge
         DrawEdge(e)
         tree.Put(e.p1, "")
         tree.Put(e.p2, "")
         Exit
       End If
     Next
   Loop
   For Each p As MST_Point In points.Keys
     ws.RunFunction("Circle", Array(p.x, p.y, 5))
   Next
End Sub

Private Sub DrawEdge(e As MST_Edge)
   ws.RunFunction("Line", Array(e.p1.x, e.p1.y, e.p2.x, e.p2.y))
End Sub

Private Sub CalcDistance(e As MST_Edge) As Double
   Return Power(e.p1.x - e.p2.x, 2) +  Power(e.p1.y - e.p2.y, 2)
End Sub

Index.html

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>B4J - Minimum Spanning Tree</title>
  <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
  <link rel="stylesheet" type="text/css" href="index.css" />
  <script src="/b4j_ws.js"></script>
 </head>
 <body>
   <h1>Minimum Spanning Tree Example (WebSocket)</h1>

     <button id="btnclear" style="position:relative;left:300px;width:100px;margin-bottom:20px;">Clear</button>

   <div id="main">
     
  <canvas id="cvs" width="800" height="500">
  </canvas>
  </div>
   <script>
   var ctx;
  $( document ).ready(function() {
  ctx = document.getElementById('cvs').getContext('2d')
  b4j_connect("/mst/ws");
   
  });
  function Clear() {
  ctx.clearRect(0, 0, $(cvs).width(), $(cvs).height());
  }
   function Circle(x, y, radius) {
  ctx.beginPath();
     ctx.arc(x,y,radius,0,2*Math.PI);
     ctx.fill();
  }
   function Line(x1, y1, x2, y2) {
     ctx.beginPath();
     ctx.moveTo(x1,y1);
     ctx.lineTo(x2,y2);
     ctx.stroke();
   }
   
   </script>

 </body>

 

[ilan]

wonderful, this is my solution:

#Region  Project Attributes
    #MainFormWidth: 600
    #MainFormHeight: 400
#End Region

Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
    Dim can As Canvas
    Dim clear_btn As Button
    Type vertices(x As Float, y As Float)
    Dim All_verts As List
    Dim line_length As Double = 0.0
End Sub

Sub AppStart (Form1 As Form, Args() As String)
    MainForm = Form1
    MainForm.SetFormStyle("UNIFIED")
    MainForm.Show
   
    clear_btn.Initialize("clear")
    can.Initialize("can")
    All_verts.Initialize
    
    MainForm.RootPane.AddNode(can,0,0,MainForm.Width,MainForm.Height)
    MainForm.RootPane.AddNode(clear_btn,0,0,100,30)
   
    clear_btn.Text = "clear"
    clear_btn.TextSize = 14
    drawtext(line_length)
End Sub

Sub drawtext(length As Double)
    can.DrawText("Line length: " & NumberFormat2(length,1,1,1,False),120,20,fx.CreateFont("Arial",14,False, False),fx.Colors.Black,"LEFT")
End Sub

Sub clear_MouseClicked (EventData As MouseEvent)
    All_verts.Clear
    can.ClearRect(0,0,MainForm.Width,MainForm.Height)
    line_length = 0.0
    drawtext(line_length)
End Sub

Sub MainForm_MouseClicked (EventData As MouseEvent)
    Dim v1 As vertices
    v1.x = EventData.X
    v1.y = EventData.Y
    All_verts.Add(v1) 'on every mouse click we add a new vertices to the main vertices list array

    can.ClearRect(0,0,MainForm.Width,MainForm.Height) 'we clear on every mouse click the canvas
    line_length = 0.0
    Prims_Algorithm 'start algorithm
End Sub

Sub Prims_Algorithm
    Dim unreached_list, reached_list As List 'we create 2 list (reached and unreached)
    unreached_list.Initialize
    reached_list.Initialize
   
    For i = 0 To All_verts.Size - 1 'first we move all dots that are stored in the main list array to "unreached" dots list array!
        Dim v1 As vertices = All_verts.Get(i)
        If i = 0 Then can.DrawCircle(v1.x,v1.y,6,fx.Colors.Red,True,0) Else can.DrawCircle(v1.x,v1.y,6,fx.Colors.Black,True,0) 'first dot will be our starting point so we draw it red
        unreached_list.Add(v1) 'add all dots to unreached list!
    Next
   
    reached_list.Add(unreached_list.Get(0)) 'first dot is our start point so we copy first dot and move it to reached list!
    unreached_list.RemoveAt(0) 'and here we delete it from the unreached list!
   
    Do While unreached_list.Size > 0
        Dim shortest_dist As Double = 100000.0 'we set here the shortest_distance to a very high number to avoid it to be shorter then the longest real distance between 2 dots
        Dim rindex, uindex As Int 'backup our shortest line between reached dot and unreached dot
        For i = 0 To reached_list.Size - 1
            For j = 0 To unreached_list.Size - 1
                Dim v2 As vertices = reached_list.Get(i)
                Dim v3 As vertices = unreached_list.Get(j)
                Dim d As Double = distance(v2.x,v3.x,v2.y,v3.y)
                If d < shortest_dist Then 'here we are looking for the shortest "reached dot" and "unreached dot" if it is found it will store the index of both and draw a line after we go through all reached dots
                    shortest_dist = d
                    rindex = i 'backup index of reached dot
                    uindex = j 'backup index of unreached dot
                End If
            Next   
        Next

        Dim v4, v5 As vertices
        v4 = reached_list.Get(rindex)
        v5 = unreached_list.Get(uindex)
        can.DrawLine(v4.x,v4.y,v5.x,v5.y,fx.Colors.Black,2)
        reached_list.Add(v5) 'here we add the unreached dot to the reached dot list
        unreached_list.RemoveAt(uindex) 'now that dot is reached so we need to delete it from the unreached list array
        line_length = line_length + shortest_dist 'we calculate the sum of all lines
    Loop   
   
    drawtext(line_length)
End Sub

Sub distance(x1 As Float, x2 As Float, y1 As Float, y2 As Float) As Double
    Return Sqrt(Power(x2-x1,2)+Power(y2-y1,2)) 'simple distance calculation
End Sub

 

[sorex]

interesting... in what is something like that used?

 

[ilan]

interesting... in what is something like that used?

Why minimum spanning trees?

The standard application is to a problem like phone network design. You have a business with several offices;
you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money
to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost.
It should be a spanning tree, since if a network isn't a tree you can always remove some edges and save money.

A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem.
A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.

Note that if you have a path visiting all points exactly once, it's a special kind of tree.
For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a
path visiting some vertices more than once, you can always drop some edges to get a tree. So in general
the MST weight is less than the TSP weight, because it's a minimization over a strictly larger set.

On the other hand, if you draw a path tracing around the minimum spanning tree, you trace each edge
twice and visit all points, so the TSP weight is less than twice the MST weight. Therefore this tour
is within a factor of two of optimal. There is a more complicated way (Christofides' heuristic)
of using minimum spanning trees to find a tour within a factor of 1.5 of optimal; I won't describe
this here but it might be covered in ICS 163 (graph algorithms) next year.

now open your imagination and try to find another use for it

 

[sorex]

nice theory

imagine living across a river. someone being farther away in bird flight my be a lot closer to the destination just because he lives on the right side of the river
just because there isn't a bridge within 10-20km to cross the river.

we have such case here. between the 2 nearest bridges that allow cars is almost 30km.

in that case you need to focus on that plotting system + real gps routing results.