3

Intento simular un grafo con diccionarios en python, de la siguiente forma:

G = {'a':{'b':3, 'c':4},
     'b':{'a':3, 'c':5},
     'c':{'a':4,'b':5},
   }

Donde G es un diccionario cuyas llaves tienen asociado un diccionario como valor. A su vez, estas llaves son los nodos adyacentes que tienen asociado como valor un respectivo peso.

He intentado con este codigo sin embargo, no he logrado mi objetivo

 def generarGrafo(num_nodos):   
        lista_nodos = []
        lista_nodos_asociados = []
        grafo = {}

    for i in range(num_nodos):
        nodo = raw_input(" ID Nodo %d:" %(i+1))
        lista_nodos.append(nodo)        
        num_nodos_asociados = input("  Numero de nodos asociados a nodo '%s':" %(lista_nodos[i]))
        lista_nodos_asociados.append([])    #Lista de listas para almacenar los nodos asociados a cada respectivo nodo i-esimo

        for j in range(num_nodos_asociados):
            nodo_asociado = raw_input("   ID nodo %d asociado:" %(j+1))
            lista_nodos_asociados[i].append(nodo_asociado)  #Se almacenan  y muestran en el elemento i-esimo de la lista    
            peso_asociado = input(" Peso asociado (Arista(%s,%s) ): " %(lista_nodos[i],lista_nodos_asociados[i][j] ) )
            grafo[lista_nodos[i]] = {}
            grafo[lista_nodos[i]][lista_nodos_asociados[i][j]] = peso_asociado
  return grafo

Obtengo como salida lo siguiente: G = {'a':{'c':4}, 'b':{'c':5}, 'c':{'b':5}, }

Por alguna rezon solo coloca el segundo item de la lista de nodos asociados,

1 respuesta 1

5

El problema esta en en ciclo for que usas para generar los nodos asociados, concretamente en la linea:

grafo[lista_nodos[i]] = {}

Con ella creas una nueva pareja clave/valor en cada iteración del for, como un diccionario tiene una clave única esto borra lo anterior por lo que al final solo quedara guardado el último nodo asociado que introduzcas. La solución es sencilla, saca esta linea del for y la pones antes de empezar éste:

 def generarGrafo(num_nodos):   
        lista_nodos = []
        lista_nodos_asociados = []
        grafo = {}

    for i in range(num_nodos):
        nodo = raw_input(" ID Nodo %d:" %(i+1))
        lista_nodos.append(nodo)        
        num_nodos_asociados = input("  Numero de nodos asociados a nodo '%s':" %(lista_nodos[i]))
        lista_nodos_asociados.append([])    #Lista de listas para almacenar los nodos asociados a cada respectivo nodo i-esimo

        grafo[lista_nodos[i]] = {}
        for j in range(num_nodos_asociados):
            nodo_asociado = raw_input("   ID nodo %d asociado:" %(j+1))
            lista_nodos_asociados[i].append(nodo_asociado)  #Se almacenan  y muestran en el elemento i-esimo de la lista    
            peso_asociado = input(" Peso asociado (Arista(%s,%s) ): " %(lista_nodos[i],lista_nodos_asociados[i][j] ) )
            grafo[lista_nodos[i]][lista_nodos_asociados[i][j]] = peso_asociado
  return grafo

Esta es la ejcución:

 ID Nodo 1:a
  Numero de nodos asociados a nodo 'a':2
   ID nodo 1 asociado:b
 Peso asociado (Arista(a,b) ): 3
   ID nodo 2 asociado:c
 Peso asociado (Arista(a,c) ): 4
 ID Nodo 2:b
  Numero de nodos asociados a nodo 'b':2
   ID nodo 1 asociado:a
 Peso asociado (Arista(b,a) ): 3
   ID nodo 2 asociado:c
 Peso asociado (Arista(b,c) ): 5
 ID Nodo 3:c
  Numero de nodos asociados a nodo 'c':2
   ID nodo 1 asociado:a
 Peso asociado (Arista(c,a) ): 4
   ID nodo 2 asociado:b
 Peso asociado (Arista(c,b) ): 5
{'a': {'c': '4', 'b': '3'}, 'c': {'a': '4', 'b': '5'}, 'b': {'a': '3', 'c':'5'}}

Por otro lado, tal y como esta la función es muy ineficiente, las dos listas no son necesarias y leer de ellas para crear el diccionario es mucho más lento que usar los valores de los input directamente. Puedes simplificar el código para hacerlo más eficiente, la siguiente fúncion hace lo mismo:

def generarGrafo(num_nodos):   
    grafo = {}

    for i in range(num_nodos):
        nodo = raw_input(" ID Nodo %d:" %(i+1))       
        num_nodos_asociados = input("  Numero de nodos asociados a nodo  '%s':" %(nodo))
        grafo[nodo] = {}

        for j in range(int(num_nodos_asociados)):
            nodo_asociado = raw_input("   ID nodo %d asociado:" %(j+1)) 
            peso_asociado = input(" Peso asociado (Arista(%s,%s) ): " %(nodo, nodo_asociado) )
            grafo[nodo][nodo_asociado] = peso_asociado
    return grafo

Si la función real es diferente a la que has publicado y si usas las listas lo que si te recomiendo es que crees el diccionario con los valores de los input y no obteniendo el valor de la lista correspondiente.

1
  • Muchas gracias por tu respuesta y recomendacion. Fue de gran ayuda el 8 oct. 2016 a las 1:42

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.