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
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