1

Estoy trabajando en la elaboración de una lista de adyacencia a partir de una matriz de adyacencia, con este código. El grafo es de 10 nodos

from collections import defaultdict
from pprint import pprint


graph = defaultdict(list)
edges = set()

for i, v in enumerate(adjacency_matrix, 1):
    for j, u in enumerate(v, 1):
        if u != 0 and frozenset([i, j]) not in edges:
            edges.add(frozenset([i, j]))
            graph[i].append({j: u})

for node in graph:
   graph[node] = graph[node][0]

me imprime como resultado lo siguiente

defaultdict(<class 'list'>,
            {1: {6: 1.0},
             2: {8: 1.0},
             3: {4: 1.0},
             4: {9: 1.0},
             5: {10: 1.0},
             6: {7: 1.0},
             7: {2: 1.0},
             8: {3: 1.0},
             9: {5: 1.0}})

El problema es que no me imprime la última fila, la del nodo 10 porque es una fila de solo 0 (es un grafo dirigido y ese el nodo final)

¿Alguien sabe cómo podría decir que si el diccionario o la lista está vacía, que muestre que está vacío? Gracias

Edit: la matriz de adyacencia es así

[[0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
 [0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]
3
  • El problema es que un defaultdict(list) no crea la lista vacía hasta que no intentas acceder a la clave correspondiente. Si en ningún momento intentas acceder a graph[10], ese elemento no existe (ni siquiera como lista vacía), por lo que no puedes mostrarlo. ¿Cómo sabes tú que hay un nodo 10? Imagino que se deduce de tu adjacency_matrix, por lo que podrías extraer de algún modo la lista de nodos existentes de esa variable, y usarla para acceder a graph[node] para cada uno de ellos (asegurando así que se crean incluso los vacíos)
    – abulafia
    el 7 sep. 2019 a las 12:49
  • Sí, es de 10 nodos. Agregué lo que me imprime la matriz de adyacencia. No entendí muy bien lo de extraer la lista de nodos. Lo que pasa es que en un grafo dirigido el nodo final siempre va a ser una fila de ceros, porque de él no parte ninguna arista
    – Andres
    el 7 sep. 2019 a las 12:57
  • Habría que modificar el if de una forma que considere el 10 el 7 sep. 2019 a las 14:09

1 respuesta 1

2

Un par de cambios en el código pueden lograr lo que (creo) buscas.

De entrada, tu defaultdict() es de listas, pero cada una de las listas que formas tiene un solo elemento, que es un diccionario (o al menos así es en este ejemplo). De hecho, una vez has terminado de crear graph haces otro bucle cuya única finalidad parece ser extraer el (único) diccionario que tiene cada una de esas listas.

Por tanto ¿por qué crear esas listas si tienen un solo elemento? Un enfoque más apropiado podría ser que cada elemento del defaultdict() sea a su vez un dict(). Cada vez que quieras "añadir" algo al diccionario, en vez de graph[i].append(), usarías graph[i].update(). Esto te evita tener que hacer el bucle final para extraer los diccionarios de las listas, pues ya tendrías directamente los diccionarios buscados.

Por otro lado, la clave 10 no puede estar en tu graph final, porque al tener todo ceros en la última fila, nunca se intenta acceder a graph[10] para actualizarlo, por lo que no se crea ese elemento (ni siquiera como vacío). Los elementos en un defaultdict() se crean sólo cuando se intenta acceder a ellos por primera vez.

Pero puedes crearlo (vacío) en el momento de imprimirlo, pues para ese caso puedes recorrer uno a uno todos los nodos existentes (y el número de ellos es simplemente el número de filas de la matriz de adyacencia) y tratar de imprimir graph[i] para cada uno. Si ese nodo existía en graph, imprimirá su valor. Si no existía, lo creará (con un valor vacío) y lo imprimirá seguidamente.

Es decir, el código que propongo quedaría así:

from collections import defaultdict
from pprint import pprint

adjacency_matrix = [
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 0,],
 [0, 0, 0, 1, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1,],
 [0, 0, 0, 0, 0, 0, 1, 0, 0, 0,],
 [0, 1, 0, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1, 0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,]]


graph = defaultdict(dict)
edges = set()

for i, v in enumerate(adjacency_matrix, 1):
    for j, u in enumerate(v, 1):
        if u != 0 and frozenset([i, j]) not in edges:
            edges.add(frozenset([i, j]))
            graph[i].update({j: u})

# Bucle de impresión, que de paso crea los elementos "vacíos"
for i in range(1, len(adjacency_matrix)+1):
    print("{}: {}".format(i, graph[i]))

Sale lo siguiente:

1: {6: 1}
2: {8: 1}
3: {4: 1}
4: {9: 1}
5: {10: 1}
6: {7: 1}
7: {2: 1}
8: {3: 1}
9: {5: 1}
10: {}

Y lo que es mejor, los elementos vacíos creados en el momento de imprimir forman ya parte de graph a partir de ese momento, como puedes comprobar:

>>> pprint(graph)
defaultdict(<class 'dict'>,
            {1: {6: 1},
             2: {8: 1},
             3: {4: 1},
             4: {9: 1},
             5: {10: 1},
             6: {7: 1},
             7: {2: 1},
             8: {3: 1},
             9: {5: 1},
             10: {}})
1
  • Muchas gracias hombre, me acabas de salvar la tesis de grado. Tengo que evaluar una matriz 760x760 y cuando hice el algoritmo me salía un error con las distancias. Por eso recurrí a una matriz 10x10 para poder saber qué podría estar mal. Ahora lo de la pregunta pasada ya se me resolvió, lo de los negativos y eso, sólo que no sé cómo ponerlo aquí en el comentario. Muchas gracias
    – Andres
    el 7 sep. 2019 a las 13:21

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.