1

Estou criando um grafo com as seguintes regras:

  • O grafo é um dicionário.
  • Os vértices são as chaves desse dicionário e os valores são as arestas.
  • Como eu posso ter mais de uma aresta para um vértice, preciso criar um conjunto set() para os valores do dicionário.

O problema diz ainda que as arestas precisam conter vértices e 'pesos' e que portanto é necessário colocá-los em tuplas dentro desse conjunto.

Não sei se está claro, mas o código de implementação para adicionar arestas é o seguinte:

  • self.grafo é o dicionário.
  • vert_Origem é 'Jim' - Jim já é um vértice incluído no dicionário
  • vert_Destino é 'Liam'
def addArestas (self, vert_Origem, vert_Destino, peso=1):
     for key, value in self.grafo.items(): 
        aresta= tuple()
        aresta = (vert_Destino, peso)
        value.add(aresta)
        self.graph[vert_Origem] = aresta
     return True

Acontece que ele retorna todas as chaves com todas as arestas. Não estou conseguindo colocar as arestas específicas para cada vértice.

Quando eu coloco:

def addArestas (self, vert_Origem, vert_Destino, peso=1):
     for key, value in self.grafo.items(): 
        aresta= tuple()
        aresta = (vert_Destino, peso)
        conjunto = set()
        conjunto.add(aresta)
        self.graph[vert_Origem] = conjunto 
     return True

O método me retorna apenas a última aresta, sobrescrevendo as outras entradas.

Alguém consegue identificar o erro?

1 Resposta 1

1

Bom, existem dois erros que você está cometendo:

  1. Você está iterando sobre as chaves do dicionário sem necessidade. No primeiro código, isso faz com que você adicione a nova aresta para todos os nodos do grafo (e note que você nem usa as variáveis key e value no seu segundo código).

  2. No segundo código, você cria um novo set cada vez que adiciona uma nova aresta, o que faz com que as arestas que já existiam ali sejam perdidas.

O que voce deve fazer é:

  1. Recuperar o set correspondente ao vert_Origem, criando um novo apenas caso seja a primeira aresta do nodo.

  2. Atualizar esse set com o novo element (vert_Destino, peso)

def addArestas(self, vert_Origem, vert_Destino, peso=1):
    aresta = (vert_Destino, peso)

    if vert_Origem not in self.grafo: # Cria o set apenas se essa eh a primeira aresta do nodo.
        self.grafo[vert_Origem] = set()

    self.grafo[vert_Origem].add(aresta)

    return True

Note também que você não precisa criar uma tupla vazia tuple() antes de criar a tupla (vert_Destino, peso), pois ela simplesmente vai ser sobrescrita pelo novo objeto.

Uma outra coisa que eu te aconselho a tomar cuidado é quando usar um set cujo elementos são tuplas. Caso você insira um elemento (4, 5) (i.e., aresta pro vértice 4 com peso 5) e depois você decida modificar o peso dessa aresta (e.g., peso 6), não adianta simplesmente inserir um novo elemento (4, 6), pois o Python vai manter ambos os elementos no set (pois eles são distintos). Não sei qual o motivo de você estar usando set ao invés de list, mas se for para garantir que não haja duas arestas ligando os mesmo vértices, isso não vai funcionar.

A propósito, em um momento você usa self.grafo e em outro self.graph. Isso pode estar causando algum bug também.

2
  • Leafar, entendi a lógica, obrigado. Sobre a utilização de tuplas em set(), você quer dizer que se eu tiver que modificar o peso da aresta eu terei que remover a aresta atual primeiro antes de inserir a nova? 21/08/2019 às 11:44
  • 1
    Sim, se voce inserir a tupla (4, 5) e depois inserir a tupla (4, 6), ambas continuarão no set, pois elas não são exatamente iguais. O que voce pode fazer é armazenar apenas o nodo de destino no set, se tornando assim um set de inteiros e não de tuplas. Para armazenar os pesos, voce pode criar um novo dicionario dict_pesos que mapeia tuplas com os nodos de cada aresta (nodo1, nodo2) para o valor do peso correspondente.
    – Leafar
    21/08/2019 às 12:39

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .