Basically i'm creating a software to calculate the shorting distance between two graphs. I use dictionarys to organize this information
I sort the path's as keys , each key has different paths according to the given inputs through the command: PrintByDistance.
The inputs are made through the command: insert:company:City1:City2:Distance
Company it's the company who's responsible to make the transportation between the 2 Cities.
My Dictionary is correctly built and works perfectly, the problem comes in the Algorithm that always picks the last element of the values of each key in dictionary...
I'm really sorry this is complex, if anyone has the time to help me solve this, i would apreciate very much.
thank you,
#######################################################################################################
from __future__ import generators
class priorityDictionary(dict):
def __init__(self):
'''Initialize priorityDictionary by creating binary heap
of pairs (value,key). Note that changing or removing a dict entry will
not remove the old pair from the heap until it is found by smallest() or
until the heap is rebuilt.'''
self.__heap = []
dict.__init__(self)
def smallest(self):
'''Find smallest item after removing deleted items from heap.'''
if len(self) == 0:
raise IndexError, "smallest of empty priorityDictionary"
heap = self.__heap
while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:
lastItem = heap.pop()
insertionPoint = 0
while 1:
smallChild = 2*insertionPoint+1
if smallChild+1 < len(heap) and \
heap[smallChild] > heap[smallChild+1]:
smallChild += 1
if smallChild >= len(heap) or lastItem <= heap[smallChild]:
heap[insertionPoint] = lastItem
break
heap[insertionPoint] = heap[smallChild]
insertionPoint = smallChild
print heap[0][1]
return heap[0][1]
def __iter__(self):
'''Create destructive sorted iterator of priorityDictionary.'''
def iterfn():
while len(self) > 0:
x = self.smallest()
yield x
del self[x]
return iterfn()
def __setitem__(self,key,val):
'''Change value stored in dictionary and add corresponding
pair to heap. Rebuilds the heap if the number of deleted items grows
too large, to avoid memory leakage.'''
dict.__setitem__(self,key,val)
heap = self.__heap
if len(heap) > 2 * len(self):
self.__heap = [(v,k) for k,v in self.iteritems()]
self.__heap.sort() # builtin sort likely faster than O(n) heapify
else:
newPair = (val,key)
insertionPoint = len(heap)
heap.append(None)
while insertionPoint > 0 and \
newPair < heap[(insertionPoint-1)//2]:
heap[insertionPoint] = heap[(insertionPoint-1)//2]
insertionPoint = (insertionPoint-1)//2
heap[insertionPoint] = newPair
def setdefault(self,key,val):
'''Reimplement setdefault to call our customized __setitem__.'''
if key not in self:
self[key] = val
return self[key]
#####################################
Priority Library
###############################################################
class Grafos:
"Classe principal "
def __init__(self):
self.companhias=[]
self.companys1=[]
self.velocidades=[]
self.emissoes=[]
self.origens=[]
self.destinos=[]
self.distancias=[]
def add_company(self,companhia):
self.companhias.append(companhia)
def add_companys1(self,company1):
self.companys1.append(company1)
def add_velocity(self,velocidade):
self.velocidades.append(velocidade)
def add_emissoes(self,emissao):
self.emissoes.append(emissao)
def add_origin(self,origem):
self.origens.append(origem)
def add_destiny(self,destino):
self.destinos.append(destino)
def add_distance(self,distancia):
self.distancias.append(distancia)
eu=Grafos()
def verifica(s):
if s == None:
return
else:
return s.strip()
def shortestPath(G,start,end):
#print "*****"
D,P = Dijkstra(G,start,end)
#print "tested"
Path = []
while 1:
Path.append(end)
if end == start:
#print "*****"
break
#print Path
#print P
#print end
end = P[end]
#print Path
Path.reverse()
return Path
def ShortestPathByDistance(G,start,end):
soma=0
return DijkstraByDistance(G,start,end)
def Dijkstra(G,start,end=None):
D = {}
P = {}
Q = priorityDictionary()
Q[start] = 0
for v in Q:
if v in G.keys():
D[v] = Q[v]
if v == end: break
for w in G[v]:
vwLength = D[v] + int(G[v][w])
if w in D:
if vwLength < D[w]:
raise ValueError
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
return (D,P)
def DijkstraByDistance(G,start,end=None):
D = {}
P = {}
Q = priorityDictionary()
Q[start] = 0
soma=0
#print "mae"
print Q
#print "estou aqui"
for v in Q:
if v in G.keys():
D[v] = Q[v]
if v == end: break
for w in G[v]:
vwLength = D[v] + int(G[v][w])
if w in D:
if vwLength < D[w]:
raise ValueError
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
soma=Q[w]
#if ler[0] == "printByCarbon":
# soma=soma+40
print soma
aux=ler[0]+':'
a=shortestPath(h,ler[1],ler[2])
for i in range(len(a)):
aux+=a[i]+':'
print aux + str('%.8f' %soma)
while(1):
try:
lerja=raw_input("")
except EOFError:
break
if not lerja:
break
a=verifica(lerja)
ler=a.split(":")
if ler[0]=="company":
eu.add_companys1(ler[1])
eu.add_velocity(ler[2])
eu.add_emissoes(ler[3])
elif ler[0]=="insert":
eu.add_company(ler[1])
eu.add_origin(ler[2])
eu.add_destiny(ler[3])
eu.add_distance(ler[4])
elif ler[0]=="remove":
listai=[]
for b in range(len(eu.companhias)):
if ler[1] == eu.companhias[b]:
listai.append(b)
aux2=[]
for o in listai:
if eu.origens[o]==ler[2]:
aux2.append(o)
for o in aux2:
if eu.destinos[o]==ler[3]:
eu.origens.pop(o)
eu.destinos.pop(o)
eu.companhias.pop(o)
break
elif ler[0]=="printCities":
lista=[]
lista1=[]
listaindices=[]
for j in range(len(eu.origens)):
if(ler[1] == eu.origens[j]):
listaindices.append(j)
for h in range(len(listaindices)):
lista.append(eu.destinos[listaindices[h]])
lista1.append(eu.companhias[listaindices[h]])
tup=zip(lista,lista1)
aux1=[]
aux2=[]
for i in range(len(tup)):
aux1.append(tup[i][0])
aux2.append(tup[i][0])
aux1.sort()
temp1=[]
for i in range(len(tup)):
for j in range(len(tup)):
if aux1[i]==aux2[j]:
aux2[j]='a'
temp1.append(j)
break
cm=[]
for i in temp1:
cm.append(tup[i][1])
tup=zip(aux1,cm)
if len(tup)==0:
s='printCities('+ler[1]+')'
else:
for i in range(len(tup)):
if i==0:
s='printCities('+ler[1]+'):'+tup[i][1]+':'+tup[i][0]
if i>0:
s+=':'+tup[i][1]+':'+tup[i][0]
print s
elif ler[0] =="printByDistance":
h={}
if ler[2] not in eu.destinos:
print ler[0]
else:
for i in range(len(eu.origens)):
if eu.origens[i] not in h:
d={}
for j in range(len(eu.origens)):
if eu.origens[i]==eu.origens[j]:
if eu.destinos[j] in d and eu.distancias[j] < d[eu.destinos[i]]:
d[eu.destinos[j]]=eu.distancias[j]
elif eu.destinos[j] not in d.keys():
d[eu.destinos[j]]=eu.distancias[j]
h[eu.origens[i]]=d
print h
ShortestPathByDistance(h,ler[1],ler[2])
a=shortestPath(h,ler[1],ler[2])
elif ler[0] == "printByNumber":
h={}
if ler[2] not in eu.destinos:
print ler[0]
else:
for i in range(len(eu.origens)):
if eu.origens[i] not in h:
d={}
for j in range(len(eu.origens)):
if eu.origens[i]==eu.origens[j]:
d[eu.destinos[j]]=1
h[eu.origens[i]]=d
print h
ShortestPathByDistance(h,ler[1],ler[2])
a=shortestPath(h,ler[1],ler[2])
elif ler[0] == "printByCarbon":
if ler[2] not in eu.destinos:
print ler[0]
else:
h={}
for i in range(len(eu.origens)):
if eu.origens[i] not in h:
d={}
for j in range(len(eu.origens)):
if eu.origens[i]==eu.origens[j]:
for k in range(len(eu.companys1)):
if eu.companhias[j]==eu.companys1[k]:
aux1=float(eu.emissoes[k])
aux=float(aux1/1000)
d[eu.destinos[j]]=aux*float(eu.distancias[j])
h[eu.origens[i]]=d
print h
ShortestPathByDistance(h,ler[1],ler[2])
a=shortestPath(h,ler[1],ler[2])
