Python adding elements to list of set updates all sets in list

Question

I have a Graph object with an attribute adj_list, which is initialized to a list of empty sets. When I call my addEdge(self, u, v) function, the expected behavior is that u gets added to the set at adj_list[v] and v gets added to the set at adj_list[u], but after printing out what gets added in the console, it seems that calling self.adj_list[u].add(v) adds v to every single set in the list.

Here's my constructor:

def __init__(self, n):
        """
        Constructor
        ------------
        Parameters:
        n: int
            number of nodes in the graph
        ------------
        Attribute:
        adj_list: list of int lists
        int list at index i contains the neighbors of node i (nodes represented as ints 
        from 0 to n-1)
        """
        # adjacency list of graph (entry at index i = list of neighbors of node i) 
        initialized with empty neighbor lists
        self.adj_list = [set()] * n

And here's the add_edge function:

def addEdge(self, u, v):
        """
        Adds an edge between vertices u & v
        -----------
        Parameters:
        u: int
            vertex at one end of edge
        v: int
            vertex at another end of edge
        -----------
        Returns:
        void
        """
        if u < 0 or u > len(self.adj_list) - 1 or v < 0 or v > len(self.adj_list) - 1:
            raise Exception("Invalid start/end vertices for edge")

        # add edge by adding to list of neighbors if it's not already in
        if v not in self.adj_list[u] and u not in self.adj_list[v]:
            # undirected graph -> add edge in both directions
            print("before", self.adj_list)
            self.adj_list[u].add(v)
            print("one add", self.adj_list)
            self.adj_list[v].add(u)
            print("after", self.adj_list)

This is how I called the function:

if __name__ == "__main__":
    g = Graph(3)
    g.addEdge(0, 1)

This is what printed out:

before [set(), set(), set()]
one add [{1}, {1}, {1}]
after [{0, 1}, {0, 1}, {0, 1}]

Could anyone help me figure out why this is happening and how to fix it? Thank you.

This is because you are having three references to set and not three sets itself because of `[set()] * n`. — Austin, Apr 27 '20 at 03:14
Try comparing the different elements in the list to each other with the 'is' operator. e.g. adj_list[0] is adj_list[1] > and if that returns True, then youre just creating multiple references to the same object, hence they all update at the same time by editing one of them. — befunkt, Apr 27 '20 at 03:15
I closed as a duplicate - I understand that you have a list of sets rather than a list of lists, but the underlying problem is the same. — Karl Knechtel, Apr 27 '20 at 03:29

score 4 · Accepted Answer · answered Apr 27 '20 at 03:14

4

self.adj_list = [set()] * n creates 3 references to the same set. Use self.adj_list = [set() for _ in range(3)] to create three different sets.

answered Apr 27 '20 at 03:14

Mark Tolonen

166,664
26
169
251

Python adding elements to list of set updates all sets in list

1 Answers1