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

user_10907846 0
Viewed 489

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!

data-structures python-3.x python
2 Answers

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.

user_24827440

I think it just needs a little change, try this:

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) and ((adj_node, key) not in edges):
                edge = (key, adj_node)
                edges.add(edge)
            else:
                pass
    return edges

Update:
So it is an Undigraph.
And it's me overcomplicated this.
And your way is actually better than my checking both ways.

The reason your code succeed, is that set will only contain one instance of any value.
So each time do the add, if there's already same tuple exists, it simply won't change the set.
And you already used the if to check the tuple of opposite direction, so it won't create duplicate edges.

For example, when (a, b) hits the if checking, it will check (b,a) exists in the set or not, if exists, then pass. If not, add (a, b) in the set, if (a, b) exists, the set won't change since only one instace will be in the set.
And later when looped to (b, a), since (a, b) already in the set, the if will be false and passed.
So by this way, the set is safe, free of duplicate edges.

user_54034680
Related