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

Edited 3 Years Ago by mike_2000_17: Fixed formatting

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 article has been dead for over six months. Start a new discussion instead.