93 lines
2.7 KiB
Python
93 lines
2.7 KiB
Python
from prettytable import PrettyTable
|
|
|
|
from utils import *
|
|
|
|
|
|
class Node:
|
|
|
|
def __init__(self, name, x=None, y=None):
|
|
self.parent = None
|
|
self.name = name
|
|
self.edges = []
|
|
self.value = float('inf') # cost reaching this node
|
|
|
|
|
|
class Edge:
|
|
|
|
def __init__(self, edge):
|
|
self.start = edge[0]
|
|
self.end = edge[1]
|
|
self.value = edge[2]
|
|
|
|
|
|
class Graph:
|
|
|
|
def __init__(self, node_list, edges):
|
|
self.nodes = []
|
|
for name in node_list:
|
|
self.nodes.append(Node(name))
|
|
|
|
for e in edges:
|
|
e = (getNode(e[0], self.nodes), getNode(e[1], self.nodes), e[2])
|
|
|
|
self.nodes[next((i for i, v in enumerate(self.nodes) if v.name == e[0].name), -1)].edges.append(Edge(e))
|
|
self.nodes[next((i for i, v in enumerate(self.nodes) if v.name == e[1].name), -1)].edges.append(
|
|
Edge((e[1], e[0], e[2])))
|
|
|
|
def print(self):
|
|
node_list = self.nodes
|
|
|
|
t = PrettyTable([' '] + [i.name for i in node_list])
|
|
for node in node_list:
|
|
edge_values = ['X'] * len(node_list)
|
|
for edge in node.edges:
|
|
edge_values[next((i for i, e in enumerate(node_list) if e.name == edge.end.name), -1)] = edge.value
|
|
t.add_row([node.name] + edge_values)
|
|
print(t)
|
|
|
|
|
|
class Queue:
|
|
def __init__(self, type, sort_by = ''):
|
|
self.type = type
|
|
self.items = []
|
|
self.sort_by = sort_by
|
|
|
|
def clear(self):
|
|
self.items.clear()
|
|
|
|
def is_empty(self):
|
|
if len(self.items) > 0:
|
|
return False
|
|
else:
|
|
return True
|
|
|
|
def push(self, element):
|
|
self.items.append(element)
|
|
'''
|
|
queue = [element_0, element_1, ... , element_n] <- element_n+1
|
|
'''
|
|
if self.type == 'PRIO':
|
|
'''
|
|
Sorting so lowest cost/ value is at [0]
|
|
queue = [element_0 < element_1 < ... < element_n < element_n+1]
|
|
'''
|
|
if self.sort_by == '':
|
|
self.items.sort(key=lambda item: item.value)
|
|
elif self.sort_by == 'f':
|
|
self.items.sort(key=lambda item: item.f)
|
|
|
|
def pop(self):
|
|
if not self.is_empty():
|
|
if self.type == 'LIFO':
|
|
''' LIFO
|
|
queue = [element_0, elemente_1, ... , element_n]
|
|
-> pop element_n
|
|
'''
|
|
return self.items.pop()
|
|
else:
|
|
''' FIFO & PRIO
|
|
queue = [element_0, element_1, ... , element_n]
|
|
-> pop element_0
|
|
'''
|
|
return self.items.pop(0)
|
|
return None |