In this code, I focused more on code readability rather than algorithmic complexity. I didn't really care about the code in the main
function because it was just used to test the code. Some of the classes have a D prefix to differentiate them from the regular Nodes
.
A few problems in particular I would like comments on:
- Storing the name of the node both in the dictionary key and the name field seems wrong. I would think it has some of the same problems as parallel lists.
- The
DGraph
class's only functionality is to be a wrapper for a list. On the otherhand, I like it because it is more verbose. - Should
connections
stay as(node, cost)
tuples or should I make a newDConnection
class? - I'm hoping to avoid external libraries
class DNode:
def __init__(self, name):
self.connections = []
self.name = name
self.total_cost = -1
self.last_connection = None
self.visited = False
def add_connection(self, node, cost):
self.connections.append((node, cost))
for connection in node.connections:
if connection[0] is self:
return
node.add_connection(self, cost)
class DGraph:
def __init__(self):
self.nodes = []
def new_node(self, name):
node = DNode(name)
self.nodes.append(node)
return node
class Dijkstra:
def __init__(self, graph, start_node, end_node):
self.graph = graph
self.start_node = start_node
self.end_node = end_node
self.dlist = DList(graph.nodes, start_node)
def calculate_shortest_path(self):
self.recursive_helper(self.start_node)
node = self.end_node
node_steps = []
while node != self.start_node:
node_steps.append(node)
node = node.last_connection
node_steps.append(self.start_node)
return reversed(node_steps)
def recursive_helper(self, current_node):
current_cost = current_node.total_cost
for connection in current_node.connections:
neighbor = connection[0]
if not neighbor.visited:
total_cost = current_cost + connection[1]
if neighbor.total_cost == -1 or total_cost < neighbor.total_cost:
neighbor.total_cost = total_cost
neighbor.last_connection = current_node
current_node.visited = True
if self.end_node.visited:
return
self.recursive_helper(self.dlist.get_smallest_unvisited_dnode())
class DList:
def __init__(self, node_list, start_node):
self.nodes = list(node_list)
start_node.total_cost = 0
def get_smallest_unvisited_dnode(self):
smallest = None
for node in self.nodes:
if not node.visited and node.total_cost != -1:
if smallest is None or node.total_cost < smallest.total_cost:
smallest = node
return smallest
class GraphParser:
def __init__(self, unparsed_string):
self.unparsed_string = unparsed_string
self.nodes = {}
self.graph = DGraph()
def create_nodes(self):
for line in self.unparsed_string.split("\n"):
if line[0:5] == "node ":
node_name = line[5:]
node = self.graph.new_node(node_name)
self.nodes[node_name] = node
def create_connections(self):
for line in self.unparsed_string.split("\n"):
if line[0:5] == "node ":
node_name = line[5:]
node = self.nodes[node_name]
elif line[0] == "\t":
connection_data = line[1:].split(",")
neighbor_name = connection_data[0].strip()
if len(connection_data) > 0:
cost = int(connection_data[1].strip())
else:
cost = 1
neighbor = self.nodes[neighbor_name]
node.add_connection(neighbor, cost)
def get_graph(self):
self.create_nodes()
self.create_connections()
return self.graph
def main():
filename = "graph.txt"
f = open(filename, "r")
content = f.read()
f.close()
gp = GraphParser(content)
graph = gp.get_graph()
start_node = gp.nodes["S"]
end_node = gp.nodes["E"]
d = Dijkstra(graph, start_node, end_node)
path = d.calculate_shortest_path()
for i in path:
print(i.name)
main()
Sample graph.txt
node A
D, 4
B, 3
S, 7
node B
S, 2
A, 3
D, 4
H, 1
node C
S, 3
L, 2
node D
A, 4
B, 4
F, 5
node E
K, 5
G, 2
node F
H, 3
D, 5
node G
H, 2
E, 2
node H
B, 1
F, 3
G, 2
node I
L, 4
J, 6
K, 4
node J
L, 4
I, 6
K, 4
node K
I, 4
K, 4
node L
I, 4
J, 4
node S
A, 7
B, 2
C, 3