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