'========================================================
' find minimum total interconnect for n nodes
'========================================================
Const As Integer n = 1000

'--------------------------------------------------------
Type node
        x As Double
        y As Double
End Type

'--------------------------------------------------------
Dim As node p(1 To n)
Dim As Integer i

'--------------------------------------------------------
Screen 20   ' setup the display
Dim As Double rhs = 1.4 
Dim As Double lhs = -rhs
Dim As Double hi = 1
Dim As Double lo = -hi
Window (lhs, lo) - (rhs, hi)

'--------------------------------------------------------
' generate initial values
Randomize (Timer*1e6)
For i = 1 To n
    p(i).x = lhs + Rnd * (rhs - lhs)
    p(i).y =  lo + Rnd * ( hi -  lo)
    Circle (p(i).x, p(i).y), .005, 4   ' size and colour of nodes
Next i

'--------------------------------------------------------
' this algorithm is slow for large n. Order = n cubed ?
Dim As Integer freePoint, free, net, bestFree, bestNet
Dim As Double dx, dy, sos, sosMin, total = 0
For freePoint = 2 To n  ' first point is assumed part of network
    '--------------------------------------------------------
    ' find closest free node to the identified net of nodes 
    sosMin = 1e100          ' initial closest found 
    For net = 1 To freePoint - 1    ' search all the known net nodes
        For free = freePoint To n   '    against all free nodes
            dx = p(free).x - p(net).x
            dy = p(free).y - p(net).y
            sos = dx*dx + dy*dy     ' sum of squares
            If sos < sosMin Then    ' found a closer pair
                sosMin = sos
                bestFree = free
                bestNet = net
            End If
        Next free
    Next net
    '--------------------------------------------------------
    ' we now know the shortest available link between net and all others
    Line (p(bestFree).x, p(bestFree).y) - (p(bestNet).x, p(bestNet).y), 14
    Swap p(bestFree), p(freePoint)  ' move best new point onto known net
    total = total + Sqr(sosMin)
    If Inkey <> "" Then Exit For    ' interupt for large n
Next freePoint
Print " total ="; total;

'========================================================
Sleep
'======================================================== 
