-
Notifications
You must be signed in to change notification settings - Fork 2
/
unshortest_path.py
73 lines (67 loc) · 3.03 KB
/
unshortest_path.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# the following should be copy pasted
# problem: currently this algorythm favour shortest path with low weight rather than high
# solution (with bugs to be fixed): favour high weight by adding the opposite of the weight 1./ e.weight
# this way: high weight = good easy connection
# buggy: does not seem to behave well, hilights only last steps of the path. try it out...
class Punto:
pass
def unshortest_path(start, end):
# initialize distances and predecessor edges
all_edges=[] # all_edges=g.edges # gi.edges()# damaged= start ? end#if len(damaged) !=0:# all_edges.discard(damaged.pop())
for x in range(0,len(g.edges)):
if list(g.edges)[x].weight !=0:
all_edges.append(list(g.edges)[x])
dist, prev , distinv= {}, {}, {}
for v in g.nodes:
dist[v], prev[v] = float('inf'), None
dist[start] = 0
for i in range(len(g.nodes)): # Bellman-Ford algorithm, tweaked so that high weight = faster
for e in all_edges: # TODO: exclude from the count the original AB
if e != (start ? end).pop()
if dist[e.target] > dist[e.source] + 1./ e.weight: #... + 1./ e.weight
dist[e.target] = dist[e.source] + 1./ e.weight #... + 1./ e.weight
prev[e.target] = e
print ( i, e.source, e.target, e.weight, ' ', e)
if e.source==start or e.target ==start:
print ('!!!!!!', e.source,e.target, prev[e.source], prev[e.target])
prev[start]=e
if dist[e.source] > dist[e.target] + 1./ e.weight: #... + 1./ e.weight
dist[e.source] = dist[e.target] + 1./ e.weight #... + 1./ e.weight
prev[e.source] = e
print ( i, e.source, e.target, e.weight, ' ', e)
if e.target==start or e.source ==start:
print ('!!!!!!', e.source, e.target, prev[e.source],prev[e.target])
print('prev(start) + prev(end)', prev[start], prev[end])
for v in g.nodes:# color all the nodes and edges as RGB 200, 200, 200
v.color = color(200, 200, 200)
for e in g.edges:
e.color = color(200, 200, 200)
vv=end #e_path, v_path, w_path=[],[],[]
mypath=Punto()
mypath.v, mypath.e, mypath.w, mypath.winv =[],[],[],[]
start.color=green
while vv != start:
e=prev[vv]
mypath.v.append(vv)
mypath.e.append(e)
mypath.w.append(e.weight)
mypath.winv.append(1./e.weight)
vv.color=green
e.color=green
s,t =e.source, e.target
if vv==s:
vv=t
else:
vv=s
return (dist[end], prev, dist,mypath) # return the total weight of the path (distance)
[a,prev,dist,mypath]=unshortest_path(v30,v21) # v33, v67)
def harmean(a):
hm= float(len(a)) / sum([1.0 /x for x in a])
return(hm)
alldist=[]
for s in g.nodes:
for t in g.nodes:
if s!=t:
[a,prev,dist,mypath]=unshortest_path(s,t)
alldist.append(a)
cpl=harmean(a)