Pointer error in Directed Graph in Python

Question

I'm trying to implement a Directed graph in python by creating a class Vertex. A vertex has the name and the adjacent as a list containing another instance of class Vertex . below is the code.

The problem is that when I assign node b as the adjacent node from node a. the pointer of node b is assigned to both adjacent of a and b which is not my intention.

I also have the picture debug mode below the code showing that the pointer of node b is also assigned to itself.

how to fix it?

class Vertex:

    def __init__(self, name, adjacent=[]):
        self.name = name
        self.adjacent = adjacent

    def add_adjacent(self, vertex):
        
        self.adjacent.append(vertex)
        
        
class Graph:
    # directed graph
    def __init__(self, edge_list):
        vertices = {}
        for o, d in edge_list:
            
            # print(o, d)
            if o not in vertices:
                v = Vertex(o)
                vertices[o] = v
            else:
                v = vertices[o]
                
            if d not in vertices:
                u = Vertex(d)
                vertices[d] = u
            else:
                u = vertices[d]
            

            if u not in v.adjacent:
                print(v.name, ' adds ', u.name)
                v.add_adjacent(u)
            
        self.vertices = vertices
    
    def get_vertex_names(self):
        return list(self.vertices.keys())
    
    def get_adjacent(self, vertex):
        return self.vertices[vertex].adjacent
    


# test Vertex
edges = [
           ['a', 'b'],
           ['a', 'c'],
           ['a', 'd'],
           ['b', 'c'],
           ['c', 'b'],
         ]

g = Graph(edges)
# g.vertices

error can be seen in debug mode

J_H · Accepted Answer · 2022-07-03 22:11:27Z

0

You wrote this:

    def __init__(self, name, adjacent=[]):

There is a subtle "gotcha", summarized by a simple rule,

Avoid using mutable container as a default arg.

You want this:

    def __init__(self, name, adjacent=None):
        self.name = name
        self.adjacent = adjacent or []

In the original, there is a single list for all vertices (since caller always lets it default). That list was created at def time. In contrast, the or [] clause constructs a new list at execution time each time through, rather than once during definition.

https://dollardhingra.com/blog/python-mutable-default-arguments/

https://towardsdatascience.com/python-pitfall-mutable-default-arguments-9385e8265422

edited Jul 3, 2022 at 22:11

answered Jul 3, 2022 at 22:05

J_H

21.2k5 gold badges29 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Pointer error in Directed Graph in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related