Skip to content

Instantly share code, notes, and snippets.

@s311354

s311354/graph.py

Last active December 16, 2022 08:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save s311354/67fd52a86ddd66fbf719f1c936d81404 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save s311354/67fd52a86ddd66fbf719f1c936d81404 to your computer and use it in GitHub Desktop.
Download ZIP
Basic Graph Traversal Algorithm
Raw
graph.py
from typing import List, Union, Set
class Graph():
"""Docstring for Graph. """
def __init__(self) -> None:
"""TODO: to be defined. """
# Adjacency set representation.
# key: node name, value: adjacency node name set
self.edges = dict()
def add_node(self, node: Union[int, str]) -> None:
"""TODO: Docstring for add_node.
"""
if node not in self.edges:
self.edges[node] = set()
def add_edge(self, source: Union[int, str], destination: Union[int, str]) -> None:
"""TODO: Docstring for add_edge.
"""
self.add_node(source)
self.add_node(destination)
self.edges[source].add(destination)
def get_nigihbors(self, node: Union[int, str]) -> Set[Union[int, str]]:
"""TODO: Docstring for get_nigihbors.
"""
if node not in self.edges:
raise RuntimeError(f"Node {node} does not exist in the graph.")
for u in self.edges[node]:
yield u
def get_num_nodes(self):
"""TODO: Docstring for get_num_nodes.
"""
return len(self.edges)
class UndirectedGraph(Graph):
"""Docstring for UndirectedGraph. """
def __init__(self):
"""TODO: to be defined. """
super(UndirectedGraph, self).__init__()
def add_edge(self, source: Union[int, str], destination: Union[int, str]) -> None:
"""TODO: Docstring for add_edge.
"""
self.add_node(source)
self.add_node(destination)
self.edges[source].add(destination)
self.edges[destination].add(source)
class DirectedGraph(Graph):
"""Docstring for DirectedGraph. """
def __init__(self):
"""TODO: to be defined. """
super(DirectedGraph, self).__init__()
# key: child name, value: parents set
self.parents = dict()
# key: parent name, value: children set
self.children = self.edges
def add_node(self, node: Union[int, str]) -> None:
"""TODO: Docstring for add_node.
"""
if node not in self.children:
self.children[node] = set()
if node not in self.parents:
self.parents[node] = set()
def get_parents(self, node: Union[int, str]) -> Set[Union[int, str]]:
"""TODO: Docstring for get_parents.
"""
if node not in self.parents:
raise RuntimeError(f"Node {node} does not exist in the graph.")
return self.parents[node]
def get_children(self, node: Union[int, str]) -> Set[Union[int, str]]:
"""TODO: Docstring for get_children.
"""
if node not in self.children:
raise RuntimeError(f"Node {node} does not exist in the graph.")
return self.children[node]
def create_dummy_directed_graph() -> DirectedGraph:
"""TODO: Docstring for create_dummy_directed_graph.
"""
graph = DirectedGraph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)
return graph
def create_dummy_undirected_graph() -> UndirectedGraph:
"""TODO: Docstring for create_dummy_undirected_graph.
"""
graph = UndirectedGraph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 5)
graph.add_edge(3, 5)
graph.add_edge(2, 4)
graph.add_edge(4, 5)
graph.add_edge(4, 6)
graph.add_edge(5, 6)
return graph
if __name__ == "__main__":
directed_graph = create_dummy_directed_graph()
undirectedGraph = create_dummy_undirected_graph()
Raw
graph_search.py
# Graph search/traversal algorithm
from typing import List, Union, Set
from queue import Queue
from graph import Graph, DirectedGraph, UndirectedGraph
def breadth_first_traversal(graph: Graph, start_nodes: List[int]) -> List[int]:
"""TODO: Docstring for breadth_first_traversal.
BFS supports multiple start nodes, the data structure used by queue
O(V+E) where V is the number of nodes and E is the number of edges
"""
search_order = []
num_nodes = graph.get_num_nodes()
# Store the nodes that have been visited
visited = set()
# FIFO
q = Queue(maxsize=num_nodes)
# Mark the source node as visited and enqueue it
for node in start_nodes:
q.put(node)
visited.add(node)
while not q.empty():
src_node = q.get()
search_order.append(src_node)
for neighbor in graph.get_nigihbors(src_node):
if neighbor not in visited:
q.put(neighbor)
visited.add(neighbor)
return search_order
def iterative_depth_first_traversal(graph: Graph, start_node: int) -> List[int]:
"""TODO: Docstring for iterative_depth_first_traversal.
DFS supports the data structure used by stack
O(V+E) where Vis the number of nodes ad E is the number of edges
"""
search_order = []
# Store the nodes that have been visited
visited = set()
# LIFO (in python, the list data structure can be used as stack)
stack = []
stack.append(start_node)
while len(stack) != 0:
src_node = stack.pop()
if src_node not in visited:
search_order.append(src_node)
visited.add(src_node)
for neighbor in graph.get_nigihbors(src_node):
stack.append(neighbor)
return search_order
def recursive_depth_first_traversal(graph: Graph, start_node: int) -> List[int]:
"""TODO: Docstring for recursive_depth_first_traversal.
Recursive algorithm is not favored for large graphs because if stack overflow
O(V+E) where V is the number of nodes and E is the number of edges
"""
def depth_first_recursion(graph: Graph, visited: Set, src_node: int, search_order: List[int]):
"""TODO: Docstring for depth_first_recursion.
"""
visited.add(src_node)
search_order.append(src_node)
for neighbor in graph.get_nigihbors(src_node):
if neighbor not in visited:
depth_first_recursion(graph=graph,
visited=visited,
src_node=neighbor,
search_order=search_order)
search_order = []
# Store the nodes that have been visited
visited = set()
if start_node not in visited:
depth_first_recursion(graph=graph,
visited=visited,
src_node=start_node,
search_order=search_order)
return search_order
def create_dummy_directed_graph() -> DirectedGraph:
"""TODO: Docstring for create_dummy_directed_graph.
"""
graph = DirectedGraph()
graph.add_edge(0, 1)
graph.add_edge(0, 5)
graph.add_edge(1, 2)
graph.add_edge(2, 4)
graph.add_edge(2, 6)
graph.add_edge(3, 2)
graph.add_edge(5, 8)
graph.add_edge(6, 5)
graph.add_edge(7, 5)
return graph
def create_dummy_undirected_graph():
"""TODO: Docstring for create_dummy_undirected_graph.
"""
graph = UndirectedGraph()
graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(1, 7)
graph.add_edge(3, 7)
graph.add_edge(7, 8)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)
graph.add_edge(5, 6)
graph.add_edge(6, 7)
graph.add_edge(5, 8)
return graph
if __name__ == "__main__":
directed_graph = create_dummy_directed_graph()
undirectedGraph = create_dummy_undirected_graph()
# Directed Graph
search_order = breadth_first_traversal(graph=directed_graph, start_nodes=[0, 1])
print(search_order)
search_order = iterative_depth_first_traversal(graph=directed_graph, start_node=0)
print(search_order)
search_order = recursive_depth_first_traversal(graph=directed_graph, start_node=0)
print(search_order)
# Undirected Graph
search_order = breadth_first_traversal(graph=undirectedGraph, start_nodes=[0, 1])
print(search_order)
search_order = iterative_depth_first_traversal(graph=undirectedGraph, start_node=0)
print(search_order)
search_order = recursive_depth_first_traversal(graph=undirectedGraph, start_node=0)
print(search_order)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment