See full working directory here: https://github.com/sharpvik/python-libs/tree/alpha/Testing
So I was working on some Graph theory and coding stuff in Python. I created a class called Graph as follows (don't worry about indentation, in the file itself it's fine):
class Graph: # undirected graph; no values for the edges;
def __init__(self):
self.nodes_counter = 0
self.nodes_dict = dict()
def node_add(self, name): # name(int / str) -- name of the node;
self.nodes_dict.update( { name : list() } )
self.nodes_counter += 1
return name
def node_del(self, name): # name(int / str) -- name of the node;
self.nodes_dict.pop(name, None)
for each in self.nodes_dict:
self.nodes_dict[each].remove(name)
self.nodes_counter -= 1
return name
def connection_add(self, one, two): # one(int / str) and two(int / str) -- two nodes you want to connect;
self.nodes_dict[one].append(two)
self.nodes_dict[two].append(one)
return [one, two]
def connection_del(self, one, two): # one(int / str) and two(int / str) -- two nodes you want to disconnect;
self.nodes_dict[one].remove(two)
self.nodes_dict[two].remove(one)
return [one, two]
def nodes_count(self): # --> function returns the number of nodes in the graph;
return self.nodes_counter
def nodes_return(self): # --> function returns the whole dict containing nodes and their connections;
return self.nodes_dict
def node_return(self, name): # name(int / str) -- name of the node you're checking;
# --> function returns connections of the given node;
return self.nodes_dict[name]
# search
## --> breadth first search using class Queue
def bfs( self, final, queue=Queue(None), checked=list() ): # final(int / str) -- name of the node you're trying to establish connection with;
# queue(class Queue) -- Queue containing the element you are beginning with (format: element);
# checked(list) -- leave empty *** internal use ***;
# --> function returns True if the two nodes are connected, otherwise it returns False;
if queue.length() == 0:
return False
temp = queue.pop()
if temp == final:
return True
else:
checked.append(temp)
for child in self.node_return(temp):
if child not in checked:
queue.ins(child)
return self.bfs(final, queue, checked)
## breadth first search using class Queue <--
## --> depth first serach using class Stack
def dfs( self, final, stack=Stack(None), checked=list() ): # final(int / str) -- name of the node you're trying to establish connection with;
# stack(class Stack) -- Stack containing the element you are beginning with (format: element);
# checked(list) -- leave empty *** internal use ***;
# --> function returns True if the two nodes are connected, otherwise it returns False;
if stack.length() == 0:
return False
temp = stack.pop()
if temp == final:
return True
else:
checked.append(temp)
for child in self.node_return(temp):
if child not in checked:
stack.add(child)
return self.dfs(final, stack, checked)
## depth first serach using class Stack <--
The bfs and dfs functions in the end rely on my other two classes:
class Stack:
def __init__(self, element):
if isinstance(element, list):
self.storage = element
else:
self.storage = [element]
def add(self, element):
self.storage.append(element)
return element
def pop(self):
temp = self.storage[-1]
self.storage.pop(-1)
return temp
def length(self):
return len(self.storage)
and
class Queue:
def __init__(self, element):
if isinstance(element, list):
self.storage = element
else:
self.storage = [element]
def ins(self, element):
self.storage.insert(0, element)
return element
def pop(self):
temp = self.storage[0]
self.storage.pop(0)
return temp
def length(self):
return len(self.storage)
Now, in another file I've initialized a new Graph that I called g for simplicitiy and tested on it.
print("BFS for 1 and 2 # --> should return True")
print( g.bfs(2, Queue(1) ), end="\n\n" )
print("BFS for 1 and 4 # --> should return True") # but returns False!!!
print( g.bfs(4, Queue(1) ), end="\n\n" )
Now, when I started debugging it, I've noticed that the checked list that keeps track of checked nodes for some reason stays full of the nodes checked by the first call to the function, even though I have implicitly set it to be checked=list() in the def bfs(...) declaration so that it will be empty every time someone calls the function. This unusual behaviour causes it to not check the node 4 because it thinks that it had already been checked (checked = [1, 3, 4]), therefore the second time function decides that two nodes aren't connected and returns False.
This problem can be solved if I pass [] empty list after the Queue(1) like that:
print( g.bfs(4, Queue(1), [] ) )
However this would complicate things and I also just want to know why it does that anyways. So if anyone knows what the hell is happening here, I am looking forward to your response.
