Last active
December 31, 2017 16:12
-
-
Save anikkon/2792747c486f9343d1d497f7f04b4e8d to your computer and use it in GitHub Desktop.
This file contains 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 heapq import heappop, heappush | |
| import itertools | |
| class Node: | |
| 'Represents a vertex in an undirected weighted graph' | |
| def __init__(self, index): | |
| self.index = index | |
| self.parent = None | |
| self.visited = False | |
| self.weight = 0 | |
| self.adj_list = [] | |
| class Graph: | |
| 'Represents undirected weighted graph' | |
| def __init__(self, num_of_nodes): | |
| self.nodes = [None for x in range(num_of_nodes)] | |
| self.edges = {} | |
| def add_node(self, node): | |
| 'Adds node to the list of nodes' | |
| self.nodes[node.index] = node | |
| def add_edge(self, start_node, end_node, distance): | |
| 'Adds edge to the list of edges' | |
| start_node.adj_list.append(end_node) | |
| end_node.adj_list.append(start_node) | |
| self.edges[(start_node.index, end_node.index)] = distance | |
| class PriorityQueue: | |
| REMOVED = '<removed-node>' # placeholder for a removed node | |
| def __init__(self): | |
| self.queue = [] # list of nodes arranged in a heap | |
| self.entry_finder = {} # mapping of nodes to entries | |
| self.counter = itertools.count() # unique sequence count | |
| def add_node(self, node): | |
| 'Add a new node or update the priority of an existing node' | |
| self.remove_node(node) | |
| count = next(self.counter) | |
| entry = [-node.weight, count, node] | |
| self.entry_finder[node] = entry | |
| heappush(self.queue, entry) | |
| def remove_node(self, node): | |
| '"Removes" node from a priority queue. Marks as REMOVED' | |
| try: | |
| entry = self.entry_finder.pop(node) | |
| entry[-1] = self.REMOVED | |
| except KeyError: | |
| pass | |
| def pop_node(self): | |
| 'Remove and return the lowest priority node from a priority queue' | |
| while self.queue: | |
| _, _, node = heappop(self.queue) | |
| if node is not self.REMOVED: | |
| del self.entry_finder[node] | |
| return node | |
| def read_from_file(filename): | |
| 'Reads input data from file into graph' | |
| with open(filename) as file: | |
| num_of_nodes = int(file.readline().split()[0]) + 1 | |
| lines = file.readlines() | |
| destination_node_index = int(lines.pop()) | |
| graph = Graph(num_of_nodes) | |
| add_node = graph.add_node | |
| add_edge = graph.add_edge | |
| nodes = graph.nodes | |
| for line in lines: | |
| start_node_index, end_node_index, weight = line.split() | |
| start_node = nodes[int(start_node_index)] | |
| end_node = nodes[int(end_node_index)] | |
| if start_node is None: | |
| start_node = Node(int(start_node_index)) | |
| add_node(start_node) | |
| if end_node is None: | |
| end_node = Node(int(end_node_index)) | |
| add_node(end_node) | |
| add_edge(start_node, end_node, int(weight)) | |
| return destination_node_index, graph | |
| def graph_search(graph, source_node_index, destination_node_index): | |
| 'Traverses over the graph searching for a path with highest weight' | |
| queue = PriorityQueue() | |
| # local variables are faster | |
| add_node = queue.add_node | |
| pop_node = queue.pop_node | |
| edges = graph.edges | |
| nodes = graph.nodes | |
| nodes[source_node_index].weight = float('inf') | |
| for n in nodes: | |
| if n is not None: | |
| add_node(n) | |
| while queue.queue: | |
| start_node = pop_node() | |
| if start_node.index == destination_node_index: | |
| return start_node | |
| for end_node in start_node.adj_list: | |
| if end_node.visited: | |
| continue | |
| start_node_index = start_node.index | |
| end_node_index = end_node.index | |
| if start_node_index > end_node_index: | |
| start_node_index, end_node_index = end_node_index, start_node_index | |
| edge_weight = edges[(start_node_index, end_node_index)] | |
| alt = min(start_node.weight, edge_weight) | |
| if alt > end_node.weight: | |
| end_node.weight = alt | |
| end_node.parent = start_node | |
| add_node(end_node) | |
| start_node.visited = True | |
| def print_path(node): | |
| 'Prints path from start node to end node recursively' | |
| if node.parent: | |
| print_path(node.parent) | |
| print(" -> ", end="") | |
| print(node.index, end="") |
This file contains 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
| ''' Algorithm to find a path with highest weight between 2 nodes in a weighted undirected graph. | |
| Solution is a modified version of Dijkstra's algorithm. | |
| Input data is read from a file, filename is passed as an argument. | |
| Output is the maximum weight and the best path between the chosen nodes. | |
| Nodes are indixed as positive integers. The start node is assumed to be 1. | |
| Input file is expected to be in format: | |
| " | |
| number_of_nodes number_of_edges | |
| ... | |
| node_1 node_2 edge_weight | |
| ... | |
| destination_node | |
| " | |
| Run as: | |
| # python <script name> <filename> | |
| Estimated complexity: | |
| O((E+V)*logV + E), V - number of vertices, E - number of edges | |
| ''' | |
| import sys | |
| from graph_search import * | |
| start_index = 1 | |
| def main(): | |
| if len(sys.argv) is not 2: | |
| print("Invalid arguments. Runt script as: \npython %s <filename>\n" % (__file__)) | |
| return | |
| filename = sys.argv[1] | |
| end_index, graph = read_from_file(filename) | |
| end_node = graph_search(graph, start_index, end_index) | |
| if end_node is None: | |
| print("No path found") | |
| return | |
| print("MAX WEIGHT: ", end_node.weight) | |
| print("PATH: ") | |
| print_path(end_node) | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment