File:SPFADemo.gif

'''
Shortest path covering (SVG) using SP Faster algorithm with queue.
Firstly use this code to generate SVG frames.
Then transform to bitmaps and convert to GIF.
'''

# range size
N = 500
margin = 20

def norm(px, py):
    return ((px[0]-py[0])**2+(px[1]-py[1])**2)**.5

def saveToSVG(nFrames, points, edges, firmed, relaxing):
    f = open('demo_'+'0'*(3-len(str(nFrames)))+str(nFrames)+'.svg', 'w')
    f.write("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n")
    for p in points:
        f.write("<circle cx=\"" +str(p[0]+margin)+ "\" cy=\""+ str(N-p[1]+margin) +"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")
    for i in range(len(edges)):
        for j in edges[i]:
            f.write("<line x1=\"" +str(points[i][0]+margin)+ "\" y1=\""+ str(N-points[i][1]+margin) +"\" x2=\"" + str(points[j][0]+margin) + "\" y2=\"" + str(N-points[j][1]+margin) + "\" stroke=\"grey\" stroke-width=\".5\"/>\n")
    for L in firmed:
        f.write("<line x1=\"" +str(L[0][0]+margin)+ "\" y1=\""+ str(N-L[0][1]+margin) +"\" x2=\"" + str(L[1][0]+margin) + "\" y2=\"" + str(N-L[1][1]+margin) + "\" stroke=\"red\" stroke-width=\"5\"/>\n")
    for L in relaxing:
        f.write("<line x1=\"" +str(L[0][0]+margin)+ "\" y1=\""+ str(N-L[0][1]+margin) +"\" x2=\"" + str(L[1][0]+margin) + "\" y2=\"" + str(N-L[1][1]+margin) + "\" stroke=\"blue\" stroke-width=\"5\"/>\n")
    f.write("</svg>\n")
    f.close()

def generatePoints(n):
    import random as r
    r.seed(10)
    
    res = []
    for i in range(n):
        pt = [r.randint(0,N) for _ in [0, 1]]
        if [pt] not in res:
            res += [pt]
    return res

# heuristic: neighbor with radius e.g. N/3
def generateEdges(n, points):
    import random as r
    r.seed(10)
    edges = []
    for i in range(n):
        dst = []
        for j in range(n):
            if i!=j and norm(points[i], points[j]) < N/3:
                dst.append(j);
        edges.append(dst)
    return edges

def spfa(n, points, edges):
    nframe = 0
    dist = [float("inf") for i in range(n)]
    prev = [-1 for _ in range(n)]
    cover = []
    dist[0] = 0.0
    Q = [0]
    while len(Q)>0:
        u = Q[0]
        Q.pop(0)
        if prev[u]!=-1:
            cover.append([points[prev[u]], points[u]])
        saveToSVG(nframe, points, edges, cover, [])
        nframe+=1
        for i in edges[u]:
            if i!=u and dist[i] > dist[u] + norm(points[i], points[u]):
                dist[i] = dist[u] + norm(points[i], points[u])
                prev[i] = u
                if i not in set(Q): Q.append(i)
                for k in range(len(cover)):
                    if cover[k][1] == points[i]:
                        cover.pop(k)
                        break
                saveToSVG(nframe, points, edges, cover, [[points[u], points[i]]])
                nframe+=1
    
    return dist, prev

# test 50 points temporarily
n = 50
pts = generatePoints(n)
es = generateEdges(n, pts)
spfa(n, pts, es)