pythongraphgraph-traversal
Is there a way to avoid revisiting/keep track of visited nodes in recursive traversal without class attribute or passed parameter?
Is there a way to do a graph based depth first traversal recursively without passing a "visited" parameter set of visited nodes (or having one as a class attribute or global variable)?
The pseudo code on wikipedia seems to indicate it is necessary.
My code (below) works after I added the default parameter to the signature given me. I didn't want to mess with the function signature at all because it's being called inside a unit test. However, a default parameter proved to be both useful and harmles, but is this the only way I could have done it, assuming I had to use recursion?
def dft_recursive(self, starting_vertex, visited = set()):
"""
Print each vertex in depth-first order
beginning from starting_vertex.
This should be done using recursion.
"""
print(starting_vertex)
visited.add(starting_vertex)
for neighbor in self.vertices[starting_vertex]:
if neighbor not in visited:
visited.add(neighbor)
self.dft_recursive(neighbor, visited)
Solution
In order to demonstrate this let's consider the following undirected graphs Graph:
1. Using Node Class instance
Implementing a Node's Class which which stores the Visited boolean Flag status itself.
Also note as se store the neighbours within the Node's Class itself.
class Node:
def __init__(self, name):
self.name = name
self.neighbours = []
self.visited = False
self.previous_node = None # NOTE: This is just to show the printed result not really needed
def __str__(self):
return f'{self.name} can go to = {self.neighbours}, is Visited? = {self.visited}'
def __repr__(self):
return f'{self.name}'
def add_path(self, node_to):
if isinstance(node_to, Node):
if node_to not in self.neighbours:
self.neighbours.append(node_to)
else:
print(f'Error, added node_to is already a neighbour of {self.name}')
else:
print(f'Error adding the new Node neighbour, it must be a instance of Node')
def has_unvisited_neighbour(self):
"""Check the Node's neighbours, return False if even one node is False hence not visited"""
check_neighbours = [node.visited for node in self.neighbours]
return all(check_neighbours)
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: Node(node) for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
get_node_from = self.nodes.get(node_from)
for node in nodes_to:
get_node_to = self.nodes.get(node)
self.nodes[node_from].add_path(get_node_to)
self.nodes[node].add_path(get_node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def __repr__(self):
return f'Graph({self.nodes})'
def show_nodes(self):
for node in self.nodes.values():
print(node)
def dft_recursive(self, starting_vertex):
starting_vertex = self.nodes[starting_vertex]
starting_vertex.visited = True
for neighbor in starting_vertex.neighbours:
if not neighbor.visited:
neighbor.visited = True
neighbor.previous_node = starting_vertex # NOTE: This is just to show the printed result not really needed
if not neighbor.has_unvisited_neighbour(): # If False means we reached a dead end
print(starting_vertex.name, end=' --> ')
self.dft_recursive(neighbor.name)
else:
print(neighbor.previous_node.name, '--> ', neighbor.name, '| ')
continue
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
path_earth = ['Earth', ('Moon', 'Mars', 'Venus')]
path_venus = ['Venus', ('Blackhole',)]
path_mercury = ['Mercury', ('Sun', 'Mars', 'Comet')]
path_mars = ['Mars', ('Jupiter', )]
path_jupiter = ['Jupiter', ('Saturn',)]
path_saturn = ['Saturn', ('Neptune',)]
path_neptune = ['Neptune', ('Uranus',)]
paths = [path_earth, path_venus, path_mercury, path_mars, path_jupiter, path_saturn, path_neptune]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')
2. Using A StateFul Closure
Python has first-class functions, meaning you can assign them to variables, pass them as arguments to other functions, compare them in expressions, etc.
A Closure is a function object that remembers values in enclosing scopes even if they are not present in memory, you can see it be implemented in the stateful_closure function.
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: [] for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
for node in nodes_to:
self.nodes[node_from].append(node)
self.nodes[node].append(node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def dft_recursive(self, starting_vertex):
"""Depth First Search using a stateful closure to keep track of Visited Node"""
visited_nodes = set()
def stateful_closure(starting_vertex):
"""Recursive stateful Closure function"""
visited_nodes.add(starting_vertex) # FAQ: This is a Closure
starting_vertex_name = starting_vertex
starting_vertex = self.nodes[starting_vertex]
for neighbor in starting_vertex:
if neighbor not in visited_nodes:
visited_nodes.add(neighbor)
if not all([bool(node in visited_nodes) for node in self.nodes[neighbor]]):
print(starting_vertex_name, end=' --> ')
stateful_closure(neighbor)
else:
print(starting_vertex_name, '--> ', neighbor, '| ')
continue
stateful_closure(starting_vertex)
# Same as prev function, shorted form to save space
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
paths = [['Earth', ('Moon', 'Mars', 'Venus')], ['Venus', ('Blackhole',)], ['Mercury', ('Sun', 'Mars', 'Comet')],
['Mars', ('Jupiter', )], ['Jupiter', ('Saturn',)], ['Saturn', ('Neptune',)], ['Neptune', ('Uranus',)]]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')