Add tuple in Python set

Question

I am creating a graph with the following rules:

• The graph is a dictionary.
• The vertices are the keys of this dictionary and the values are the edges.
• Since I can have more than one edge for a vertex, I need to create a set set() for the dictionary values.

The problem also says that the edges need to contain vertices and 'weights' and that it is therefore necessary to place them in tuples within this set.

I don’t know if it’s clear, but the implementation code for adding edges is as follows::

• self.grafo is the dictionary.
• vert_Origem is 'Jim' - Jim is already a vertex included in the dictionary
• vert_Destino is '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

It turns out that it returns all keys with all edges. I’m not able to place the specific edges for each vertex.

When I put:

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

The method returns me only the last edge, overwriting the other entries.

Someone can identify the mistake?

Answer 1

Well, there are two mistakes you’re making:

1. You’re iterating over the dictionary keys unnecessarily. In the first code, this causes you to add the new edge to all the graph nodes (and note that you don’t even use the variables key and value in its second code).

2. In the second code, you create a new set each time it adds a new edge, which causes the edges that already existed there to be lost.

What you must do is:

1. Retrieve the set corresponding to vert_Origem, creating a new one only if it is the first edge of the node.

2. Update this set with the new 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

Also note that you don’t need to create an empty tuple tuple() before creating the tuple (vert_Destino, peso), because it will simply be overwritten by the new object.

Another thing I advise you to be careful of is when using a set which elements are tuples. If you enter an element (4, 5) (i.e., edge pro vertex 4 with weight 5) and then you decide to modify the weight of that edge (e.g., weight 6), it is no use simply inserting a new element (4, 6), because Python will keep both elements in set (because they are distinct). I don’t know why you are using set instead of list, but if it’s to ensure that there are no two edges connecting the same vertices, it won’t work.

By the way, in a moment you use self.grafo and in another self.graph. This may be causing some bug as well.