Last active
April 13, 2023 20:56
-
-
Save ad-1/6cba3268348422fc1a9b3a3bd9a1c613 to your computer and use it in GitHub Desktop.
Graph Traversal and Pathfinding Algorithm Visualisation in Python: https://medium.com/p/99595c414293
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from get_adjacent_nodes import get_adj_list | |
| from progress_state import progress_state | |
| from state import State | |
| class BFS: | |
| def __init__(self, nodes, recursive, start_node, finish_node, root, animate=False): | |
| """ initialise bredth first search solver """ | |
| self.subscriber = root | |
| self.nodes = nodes | |
| self.start_node = start_node | |
| self.finish_node = finish_node | |
| self.state_consts = [start_node, finish_node] | |
| self.adjacency_list = get_adj_list(nodes) | |
| self.prev = {} | |
| self.path = [] | |
| self.queue = [start_node] | |
| if animate: | |
| self.render_delay = 0.01 | |
| else: | |
| self.render_delay = 0 | |
| if recursive: | |
| self.bfs_recursive(start_node) | |
| else: | |
| self.bfs() | |
| self.backtrack(finish_node) | |
| self.visualise_path() | |
| def bfs(self): | |
| """ breadth first search iterative """ | |
| node = self.queue[-1] | |
| while node != self.finish_node and node in self.adjacency_list: | |
| progress_state(node, self.state_consts, State.VISITING, self.render_delay) | |
| for edge in self.adjacency_list[node]: | |
| if edge.state == State.VISITED or edge.state == State.QUEUE: | |
| continue | |
| self.prev[edge] = node | |
| self.queue.append(edge) | |
| progress_state(edge, self.state_consts, State.QUEUE, self.render_delay) | |
| self.queue.pop(0) | |
| progress_state(node, self.state_consts, State.VISITED, self.render_delay) | |
| if not self.queue: | |
| break | |
| node = self.queue[0] | |
| def backtrack(self, node): | |
| """ build shortest path """ | |
| if node == self.start_node or node not in self.prev: | |
| return | |
| prev_node = self.prev[node] | |
| self.path.append(prev_node) | |
| self.backtrack(prev_node) | |
| def visualise_path(self): | |
| for node in reversed(self.path): | |
| progress_state(node, self.state_consts, State.PATH, self.render_delay) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from get_adjacent_nodes import get_adj_list | |
| from progress_state import progress_state | |
| from state import State | |
| class DFS: | |
| def __init__(self, nodes, recursive, start_node, finish_node, root, animate=False): | |
| """ initialise dfs solver """ | |
| self.subscriber = root | |
| self.nodes = nodes | |
| self.adjacency_list = get_adj_list(nodes) | |
| self.path = [] | |
| self.stack = [start_node] | |
| self.start_node = start_node | |
| self.finish_node = finish_node | |
| self.state_consts = [start_node, finish_node] | |
| if animate: | |
| self.render_delay = 0.01 | |
| else: | |
| self.render_delay = 0 | |
| self.recursive = recursive | |
| if recursive: | |
| if self.dfs_recursive(start_node): | |
| self.backtrack() | |
| else: | |
| if self.dfs(start_node): | |
| self.backtrack() | |
| def dfs(self, node): | |
| """ depth first search iterative solution """ | |
| stack = [node] | |
| while node != self.finish_node: | |
| node = stack[-1] | |
| pop_from_stack = True | |
| progress_state(node, self.state_consts, State.VISITING, self.render_delay) | |
| self.path.append(node) | |
| for edge in self.adjacency_list[node]: | |
| if edge.state == State.VISITED or edge.state == State.VISITING or edge.state == State.START: | |
| continue | |
| stack.append(edge) | |
| pop_from_stack = False | |
| break | |
| if pop_from_stack: | |
| progress_state(stack[-1], self.state_consts, State.VISITED, self.render_delay) | |
| stack.pop(-1) | |
| if not stack: | |
| return False | |
| self.path = [node for node in self.path if node.state != State.VISITED] | |
| return True | |
| def backtrack(self): | |
| """ backtrack through path to finish node """ | |
| if self.recursive: | |
| for node in reversed(self.path): | |
| progress_state(node, self.state_consts, State.PATH, self.render_delay) | |
| else: | |
| for node in self.path: | |
| progress_state(node, self.state_consts, State.PATH, self.render_delay) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from math import inf | |
| from state import State | |
| from progress_state import progress_state | |
| class Dijkstra: | |
| def __init__(self, nodes, a_star, start_node, finish_node, root, animate=False): | |
| """ initialize solver """ | |
| self.subscriber = root | |
| self.nodes = nodes | |
| self.start_node = start_node | |
| self.finish_node = finish_node | |
| self.state_consts = [start_node, finish_node] | |
| self.prev_node_key = 'prev_node' | |
| self.distance_key = 'distance' | |
| self.heuristic_key = 'manhattan' | |
| self.a_star = a_star | |
| self.priority_queue = {start_node: 0} | |
| self.adjacency_list, self.path_info = self.init_dijkstra() | |
| self.path_info[start_node][self.prev_node_key] = None | |
| self.path_info[start_node][self.distance_key] = 0 | |
| self.path_info[start_node][self.heuristic_key] = self.manhattan_distance(start_node) | |
| self.shortest_path = [] | |
| if animate: | |
| self.render_delay = 0.01 | |
| else: | |
| self.render_delay = 0 | |
| if self.dijkstra(start_node): | |
| self.backtrack() | |
| self.visualise_path() | |
| def dispatch(self, node): | |
| """ dispatch node info """ | |
| self.subscriber.render_node(node) | |
| def init_dijkstra(self): | |
| """ create graph adjacency list and distance array """ | |
| adjacency_list = {} | |
| path_info = {} | |
| for i, row in enumerate(self.nodes): | |
| for j, node in enumerate(row): | |
| path_info[node] = {self.prev_node_key: None, self.distance_key: inf, self.heuristic_key: self.manhattan_distance(node)} | |
| for c in node.connections: | |
| if 0 <= c[0] < len(self.nodes) and 0 <= c[1] < len(self.nodes[0]): | |
| edge = self.nodes[c[0]][c[1]] | |
| if edge.state == State.WALL: | |
| continue | |
| adjacency_list.setdefault(node, {edge}).add(edge) | |
| return adjacency_list, path_info | |
| def pythagoras(self, node): | |
| """ euclidean distance - A* heuristic """ | |
| a = node.col - self.finish_node.col | |
| b = node.row - self.finish_node.row | |
| c = ((a ** 2) + (b ** 2)) ** (1/2) * 1000 | |
| return c | |
| def manhattan_distance(self, node): | |
| """ manhattan distance - A* heuristic """ | |
| return abs(self.finish_node.col - node.col) + abs(self.finish_node.row - node.row) | |
| def dijkstra(self, node): | |
| """ dijkstra and a* algorithm implementation """ | |
| while self.finish_node != self.get_next_priority(): | |
| if node is None or node not in self.adjacency_list: | |
| return False | |
| progress_state(node, self.state_consts, State.VISITING, self.render_delay) | |
| self.priority_queue.pop(node, None) | |
| edges = self.adjacency_list[node] | |
| self.relaxation(node, edges) | |
| progress_state(node, self.state_consts, State.VISITED, self.render_delay) | |
| node = self.get_next_priority() | |
| return True | |
| def relaxation(self, node, edges): | |
| """ update distance array """ | |
| for edge in edges: | |
| if edge.state == State.VISITED: | |
| continue | |
| if self.a_star: | |
| new_dist = edge.weight + self.path_info[edge][self.heuristic_key] | |
| else: | |
| new_dist = edge.weight + self.path_info[node][self.distance_key] | |
| if new_dist < self.path_info[edge][self.distance_key]: | |
| self.path_info[edge][self.prev_node_key] = node | |
| if self.a_star: | |
| self.path_info[edge][self.heuristic_key] = new_dist | |
| else: | |
| self.path_info[edge][self.distance_key] = new_dist | |
| self.priority_queue[edge] = new_dist | |
| def get_next_priority(self): | |
| """ get next priority node based on minimum distance in queue """ | |
| if not self.priority_queue: | |
| return | |
| return min(self.priority_queue, key=self.priority_queue.get) | |
| def backtrack(self): | |
| """ backtrack through path info to find shortest path to finish node """ | |
| node = self.finish_node | |
| while node != self.start_node: | |
| prev_node = self.path_info[node][self.prev_node_key] | |
| self.shortest_path.append(prev_node) | |
| node = prev_node | |
| def visualise_path(self): | |
| for node in reversed(self.shortest_path): | |
| progress_state(node, self.state_consts, State.PATH, self.render_delay) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from state import State | |
| from math import inf | |
| class Node: | |
| def __init__(self, x1, y1, x2, y2, row, col, idx, root): | |
| """ initialize node with graph positional info """ | |
| self.subscriber = root | |
| self.id = 'n_' + str(idx) | |
| self.x1, self.y1 = x1, y1 | |
| self.x2, self.y2 = x2, y2 | |
| self.row, self.col = row, col | |
| self.idx = idx | |
| self.weight = 1 | |
| self._state = State.NORMAL | |
| self.connections = [(self.row - 1, self.col), | |
| (self.row, self.col + 1), | |
| (self.row + 1, self.col), | |
| (self.row, self.col - 1)] | |
| def __repr__(self): | |
| return '<Node {}, State \'{}\'>'.format(self.idx, self.state.name) | |
| @property | |
| def state(self): | |
| return self._state | |
| @state.setter | |
| def state(self, val): | |
| """ set state """ | |
| state, render_delay, w = val | |
| self._state = state | |
| if state == State.WALL: | |
| self.weight = inf | |
| elif state != State.VISITED and state != State.VISITING and state != State.PATH and state != State.QUEUE: | |
| self.weight = w | |
| self.dispatch(self, render_delay) | |
| def dispatch(self, node, render_time): | |
| """ dispatch node info """ | |
| self.subscriber.render_node(node, render_time) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from enum import Enum | |
| class State(Enum): | |
| """ different states a node may be in """ | |
| NORMAL = '#f6f4f2' | |
| START = '#71DE5F' | |
| FINISH = '#F15353' | |
| WEIGHT = '#eba173' | |
| WALL = '#434343' | |
| QUEUE = '#ebbfff' | |
| VISITING = '#fc03c6' | |
| VISITED = '#83fce0' | |
| PATH = '#f2fc83' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment