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.emissoes=[]
self.origens=[]
self.destinos=[]
self.distancias=[]

self.companhias.append(companhia)

self.companys1.append(company1)

self.emissoes.append(emissao)

self.origens.append(origem)

self.destinos.append(destino)

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":

elif ler[0]=="insert":

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])
``````

Edited by mike_2000_17: Fixed formatting

3
Contributors
3
Replies
4
Views
8 Years
Discussion Span
Last Post by faniryharijaona

Please follow the forum guidelines when posting, most importantly when you post code. If you don't use code tags the code turns out as it did above and nobody wants to look at the crazy wall of unformatted text.

Use code tags like this when posting code in this forum:
[code=python] # Put your code inside here

[/code]]/noparse]

It also helps if you give us the portion of code that causes your issue and a concise example of how to reproduce the issue... (ie provided input, expected output, actual output)[noparse]

``# Put your code inside here``

]/noparse]

It also helps if you give us the portion of code that causes your issue and a concise example of how to reproduce the issue... (ie provided input, expected output, actual output)

i tried to work with codetags it just doesnt work :/
Example of Inputs:

company:DHL:200:100
company:UPS:10:500
company:CTT:1000:200
company:FEDEX:500:300
insert:DHL:Coimbra:Porto:222
insert:CTT:Porto:Coimbra:2
insert:UPS:Coimbra:Porto:111
insert:DHL:Porto:Gottingen:111
insert:UPS:Coimbra:Lisboa:25
insert:UPS:Lisboa:Penacova:22
insert:CTT:Lisboa:Porto:33
printCities:Lisboa
insert:DHL:Lisboa:Porto:3
insert:DHL:Lisboa:Dundee:66
printCities:Lisboa
insert:UPS:Lisboa:Gottingen:10
printCities:Lisboa
insert:DHL:Gottingen:Dundee:5
insert:DHL:Gottingen:Porto:6
insert:FEDEX:Gottingen:Penacova:22
insert:FEDEX:Coimbra:Penacova:2
insert:FEDEX:Penacova:Aveiro:222
printCities:Coimbra
remove:FEDEX:Coimbra:Penacova
printCities:Coimbra
printCities:Dundee
printByDistance:Dundee:Penacova

Example of Outputs:

printCities(Lisboa):UPS:Penacova:CTT:Porto
printCities(Lisboa):DHL:Dundee:UPS:Penacova:CTT:Porto:DHL:Porto
printCities(Lisboa):DHL:Dundee:UPS:Gottingen:UPS:Penacova:CTT:Porto:DHL:Porto
printCities(Coimbra):UPS:Lisboa:FEDEX:Penacova:DHL:Porto:UPS:Porto
printCities(Coimbra):UPS:Lisboa:DHL:Porto:UPS:Porto
printCities(Dundee)
printByDistance
printByDistance:Lisboa:Penacova:22.00000000

ERROR:
I get this as
last output
printByDistance:Lisboa:Penacova:35.00000000

Hi,

I don't know if it helps but I have done this so long time ago, unfortunatly it is in Sage and it can be simplified. You can get idea from it.

``````def shortest_path(G,s,w):
P = [[s]] #start the counting from the vertice 0
step = 1
for l in P: # take every path in P
if len(l)==step:
N_l = [v for v in G.vertices() if not v in l[:len(l)-1] and G.distance(v,l[len(l)-1])==1] #take the neighboor of l
if len(N_l)!=0:
for v in N_l:
k = list(l)
k.append(v)
P.append(k)
if len(l)> step:
step +=1
N_l = [v for v in G.vertices() if not v in l[:len(l)-1] and G.distance(v,l[len(l)-1])==1] #take the neighboor of l
if len(N_l)!=0:
for v in N_l:
k = list(l)
k.append(v)
P.append(k)
#looking for the shortest in the list
P.remove(P[0])# remove the first element of P
min = 1e03
for path in P:
if path[len(path)-1]==w and path[0]==s:#take all the path which end is w
if len(path)< min:
min = len(path)
min_path = path
print 'The shortest path from '+str(s)+' to '+str(w)+' is ',min_path``````

The function takes a non oriented graph define as a dictionary

G=Graph({0:[1,2,5],1:[0,3],2:[5,4],3:[6],4:[2],5:[0,2],6:[5,3]})

every vertex is labeled, 0:[1,2,5] means, the vertex with label 0 is connected to 1 and so one....

>>>shortest_path(G,3,4)
The shortest path from 3 to 4 is [3, 1, 0, 2, 4]

Best wishes
Faniry

#######################################################################################################

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.