Why does my code take different values when i switch the order in a set (knowing that order doesn't matter with sets)

  • A+
Category:Languages

I'm trying to implement a method that returns the edges of a graph, represented by an adjacency list/dictionary.

So to iterate through the dictionary, first I iterated through the keys, then through every value stored in the corresponding key. Inside the nested for-loop, I had a condition where, if a particular edge, say (a,b) is not in the set of edges, then add it to the set -- pass otherwise. On my first run, the method took in edges that are the same -- that is, in the set of edges, there are (a,b) and (b,a).

class Graph():     def __init__(self, grph={}):         self.graph = grph      def get_vertices(self):         for keys in self.graph:             yield keys      def get_edges(self):         edges = set()         for key in self.graph:             for adj_node in self.graph[key]:                 if (key, adj_node) not in edges:                     edge = (key, adj_node)                     edges.add(edge)                 else:                     pass         return edges   def main():     graph1 = {         'A': ['B','C','D'],         'B': ['A','E'],         'C': ['A', 'D'],         'D': ['A', 'C'],         'E': ['B'],     }     graph_one = Graph(graph1)     print(list(graph_one.get_vertices()))     print(graph_one.get_edges())  if __name__ =='__main__':     main() 

the output is:

{('A','B'),('D','A'),('B','A'),('B','E'),('A','D'),('D','C'),('E','B'),('C','D'),('A','C'),('C','A')}

So what I did was that, I just changed the if statement:

"if (adj_node, key) not in edges:"

def get_edges(self):         edges = set()         for key in self.graph:             for adj_node in self.graph[key]:                 if (adj_node, key) not in edges:                     edge = (key, adj_node)                     edges.add(edge)                 else:                     pass         return edges 

Now the output was:

{('C','D'),('A','B'),('E','B'),('A','C'),('A','D')}

Im very curious as to why it is so, and I'd be so thankful if you guys could explain it to me. Thanks in advance!

 


When we say that sets have no order or that order doesn't matter, it means that {x, y} == {y, x}. But (a, b) and (b, a) are tuples, order matters for them, so (a, b) != (b, a) and therefore {(a, b), (b, a)} is a set with two distinct elements, although it's equal to {(b, a), (a, b)}.

When your code looks like this:

        if (adj_node, key) not in edges:             edge = (key, adj_node)             edges.add(edge) 

then when the edge a <-> b is first encountered, it's as (key, adj_node) == (a, b) and is added to the set. When it's encountered the second (and only other) time, it's as (key, adj_node) == (b, a), meaning (adj_node, key) == (a, b) which is already in the set so (adj_node, key) not in edges is false and (b, a) doesn't get added to the set.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: