# 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:
B4X:
``````'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
End Sub

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)
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
B4X:
``````<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<title>B4J - Minimum Spanning Tree</title>
<script src="/b4j_ws.js"></script>
<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;
ctx = document.getElementById('cvs').getContext('2d')
b4j_connect("/mst/ws");

});
function Clear() {
ctx.clearRect(0, 0, \$(cvs).width(), \$(cvs).height());
}
ctx.beginPath();
ctx.fill();
}
function Line(x1, y1, x2, y2) {
ctx.beginPath();
ctx.moveTo(x1,y1);
ctx.lineTo(x2,y2);
ctx.stroke();
}

</script>

</body>``````

#### ilan

##### Expert
Longtime User
wonderful, this is my solution:

B4X:
``````#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

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
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

##### Expert
Longtime User
interesting... in what is something like that used?

#### ilan

##### Expert
Longtime User
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

##### Expert
Longtime User
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.

Replies
12
Views
1K
Replies
16
Views
5K
Replies
15
Views
5K
Replies
164
Views
66K