I'm trying to implement a uniform cost search algorithm using node-edge-graph structure. And these are my classes
class Node:
def __init__(self, name: str, edges:list = [] ) -> None:
self.name = name
self.edges = edges
class Edge:
def __init__(self, start_node: Node, end_node: Node, weight: int) -> None:
self.start_node = start_node
self.end_node = end_node
self.weight = weight
class Graph:
def __init__(self, nodes:list = [], edges:list = []) -> None:
self.node_list = nodes
self.edge_list = edges
def add_node(self, node: Node) -> None:
self.node_list.append(node)
def add_edge(self,start_node:Node, end_node: Node, weight: int) -> None:
edge = Edge(start_node, end_node, weight)
self.edge_list.append(edge)
start_node.edges.append(edge)
end_node.edges.append(edge)
def get_node(self, name: str) -> Node:
for node in self.node_list:
if name == node.name:
return node
else:
raise CityNotFoundError(name)
def get_edges(self, node:str) -> list:
for node in self.node_list:
return node.edges
def get_weight(self, start: str, end: str) -> int:
start_node = self.get_node(start)
for edge in start_node.edges:
if edge.end_node.name == end:
return edge.weight
I implement a build_graph(filepath:str)->Graphfunction that reads a csv file and builds a graph:
def build_graph(path: str) -> Graph:
file = open(path, "r")
next(file)
graph = Graph()
read_cities = list()
for line in file:
vars = line.strip().split(",")
city1 = vars[0]
city2 = vars[1]
distance = int(vars[2])
if city1 not in read_cities:
node1 = Node(city1)
read_cities.append(city1)
if city2 not in read_cities:
node2 = Node(city2)
read_cities.append(city2)
start_node = graph.get_node(city1)
end_node = graph.get_node(city2)
graph.add_edge(start_node, end_node, distance)
return graph
Finally this is my uniform_cost_search(graph, start, end) function
def uniform_cost_search(graph: Graph, start: Node, end: Node):
if start not in graph.node_list:
raise CityNotFoundError(start.name)
if end not in graph.node_list:
raise CityNotFoundError(end.name)
frontier = PriorityQueue()
explored = set()
path = list()
frontier.put((0, start, path.append(start)))
while not frontier.empty():
cost, current_node, node_path = frontier.get()
if current_node == end:
return node_path, cost
explored.add(current_node)
for edge in graph.get_edges(current_node.name):
neighbor = edge.end_node
weight = edge.weight
if neighbor not in explored:
total_cost = cost + weight
path.append(neighbor)
frontier.put((total_cost, neighbor, path))
raise CityNotFoundError(end)
When I run my code I'm having an error like this
Traceback (most recent call last):
File "c:\Users\kamil\Desktop\PythonProjects\Project-1\last.py", line 115, in <module>
graph = build_graph(file_path)
^^^^^^^^^^^^^^^^^^^^^^
File "c:\Users\kamil\Desktop\PythonProjects\Project-1\last.py", line 73, in build_graph
graph.add_edge(start_node, end_node, distance)
File "c:\Users\kamil\Desktop\PythonProjects\Project-1\last.py", line 32, in add_edge
start_node.edges.append(edge)
AttributeError: 'NoneType' object has no attribute 'edges'
^^^^^^^^^^^^^^^^
Does not start_node have a list named edges that I declared as it is? Why is this happening?
Change if name == node.list to if name == node.name
in class Graph: get_node
with input as test_OP_2.csv:
city1,city2,distance
A,B,95
B,C,125
A,C,155
A,E,50
B,E,60
A,E,55
and my super print to debug code (sorry I am really slow at this thing and don't know about uniform cost search algorithm using node-edge-graph structure) :
class Node:
def __init__(self, name: str, edges:list = [] ) -> None:
self.name = name
self.edges = edges
class Edge:
def __init__(self, start_node: Node, end_node: Node, weight: int) -> None:
self.start_node = start_node
self.end_node = end_node
self.weight = weight
class Graph:
def __init__(self, nodes:list = [], edges:list = []) -> None:
self.node_list = nodes
self.edge_list = edges
def add_node(self, node: Node) -> None:
self.node_list.append(node)
def add_edge(self,start_node:Node, end_node: Node, weight: int) -> None:
edge = Edge(start_node, end_node, weight)
self.edge_list.append(edge)
start_node.edges.append(edge)
end_node.edges.append(edge)
def get_node(self, name: str) -> Node:
for node in self.node_list:
# if name == node.list: # --> ##AttributeError: 'Node' object has no attribute 'list'
if name == node.name:
# if name in self.node_list : #--> AttributeError: 'NoneType' object has no attribute 'edges'
return node
else:
# raise CityNotFoundError(name)
print('error')
def get_edges(self, node:str) -> list:
for node in self.node_list:
return node.edges
# return [(i.start_node.name, i.end_node.name, i.weight) for i in node.edges]
def get_weight(self, start: str, end: str) -> int:
start_node = self.get_node(start)
for edge in start_node.edges:
if edge.end_node.name == end:
return edge.weight
def build_graph(path: str) -> Graph:
file = open(path, "r")
next(file)
graph = Graph()
read_cities = list()
for line in file:
print('read_cities : ', read_cities)
print('node_list names : ', [i.name for i in graph.node_list])
var = line.strip().split(",")
print(var)
city1 = var[0]
city2 = var[1]
distance = int(var[2])
print('city1 : ', city1)
print('city2 : ', city2)
print('distance : ', distance)
if city1 not in read_cities:
node1 = Node(city1)
print('node1 : ', node1, type(node1),
'node1.name : ', node1.name , 'node1.edges : ',node1.edges)
read_cities.append(city1)
graph.add_node(node1)
if city2 not in read_cities:
node2 = Node(city2)
print('node2 : ', node2, type(node2),
'node2.name : ', node2.name , 'node2.edges : ',node2.edges)
read_cities.append(city2)
graph.add_node(node2)
start_node = graph.get_node(city1)
end_node = graph.get_node(city2)
print('start_node : ', start_node)
print('end_node :', end_node)
graph.add_edge(start_node, end_node, distance)
return graph
a = build_graph('test_OP_2.csv')
print('a : ', a)
print("a.get_edges('A') : " , a.get_edges('A'))
print("a.get_weight('A', 'B') : ", a.get_weight('A', 'B'))
print("a.get_weight('C', 'E') : ",a.get_weight('C', 'E'))
print('a.node_list : ', [i.name for i in a.node_list])
print('a.edge_list ; ', [(i.start_node.name, i.end_node.name, i.weight) for i in a.edge_list])
print(type(a))
I get as output:
read_cities : []
node_list names : []
['A', 'B', '95']
city1 : A
city2 : B
distance : 95
node1 : <__main__.Node object at 0x7f47d467a2e0> <class '__main__.Node'> node1.name : A node1.edges : []
node2 : <__main__.Node object at 0x7f47d467a370> <class '__main__.Node'> node2.name : B node2.edges : []
error
start_node : <__main__.Node object at 0x7f47d467a2e0>
end_node : <__main__.Node object at 0x7f47d467a370>
read_cities : ['A', 'B']
node_list names : ['A', 'B']
['B', 'C', '125']
city1 : B
city2 : C
distance : 125
node2 : <__main__.Node object at 0x7f47d467a520> <class '__main__.Node'> node2.name : C node2.edges : [<__main__.Edge object at 0x7f47d467a4c0>, <__main__.Edge object at 0x7f47d467a4c0>]
error
error
error
start_node : <__main__.Node object at 0x7f47d467a370>
end_node : <__main__.Node object at 0x7f47d467a520>
read_cities : ['A', 'B', 'C']
node_list names : ['A', 'B', 'C']
['A', 'C', '155']
city1 : A
city2 : C
distance : 155
error
error
start_node : <__main__.Node object at 0x7f47d467a2e0>
end_node : <__main__.Node object at 0x7f47d467a520>
read_cities : ['A', 'B', 'C']
node_list names : ['A', 'B', 'C']
['A', 'E', '50']
city1 : A
city2 : E
distance : 50
node2 : <__main__.Node object at 0x7f47d467a6a0> <class '__main__.Node'> node2.name : E node2.edges : [<__main__.Edge object at 0x7f47d467a4c0>, <__main__.Edge object at 0x7f47d467a4c0>, <__main__.Edge object at 0x7f47d467a5b0>, <__main__.Edge object at 0x7f47d467a5b0>, <__main__.Edge object at 0x7f47d467a610>, <__main__.Edge object at 0x7f47d467a610>]
error
error
error
start_node : <__main__.Node object at 0x7f47d467a2e0>
end_node : <__main__.Node object at 0x7f47d467a6a0>
read_cities : ['A', 'B', 'C', 'E']
node_list names : ['A', 'B', 'C', 'E']
['B', 'E', '60']
city1 : B
city2 : E
distance : 60
error
error
error
error
start_node : <__main__.Node object at 0x7f47d467a370>
end_node : <__main__.Node object at 0x7f47d467a6a0>
read_cities : ['A', 'B', 'C', 'E']
node_list names : ['A', 'B', 'C', 'E']
['A', 'E', '55']
city1 : A
city2 : E
distance : 55
error
error
error
start_node : <__main__.Node object at 0x7f47d467a2e0>
end_node : <__main__.Node object at 0x7f47d467a6a0>
a : <__main__.Graph object at 0x7f47d467a1c0>
a.get_edges('A') : [<__main__.Edge object at 0x7f47d467a4c0>, <__main__.Edge object at 0x7f47d467a4c0>, <__main__.Edge object at 0x7f47d467a5b0>, <__main__.Edge object at 0x7f47d467a5b0>, <__main__.Edge object at 0x7f47d467a610>, <__main__.Edge object at 0x7f47d467a610>, <__main__.Edge object at 0x7f47d467a670>, <__main__.Edge object at 0x7f47d467a670>, <__main__.Edge object at 0x7f47d467a700>, <__main__.Edge object at 0x7f47d467a700>, <__main__.Edge object at 0x7f47d467a760>, <__main__.Edge object at 0x7f47d467a760>]
a.get_weight('A', 'B') : 95
error
error
a.get_weight('C', 'E') : 50
a.node_list : ['A', 'B', 'C', 'E']
a.edge_list ; [('A', 'B', 95), ('B', 'C', 125), ('A', 'C', 155), ('A', 'E', 50), ('B', 'E', 60), ('A', 'E', 55)]
<class '__main__.Graph'>
I believe that given a = build_graph('test_OP_2.csv') having :
a.node_list : ['A', 'B', 'C', 'E']
a.edge_list ; [('A', 'B', 95), ('B', 'C', 125), ('A', 'C', 155), ('A', 'E', 50), ('B', 'E', 60), ('A', 'E', 55)]
is the expected result, I hope.
Need to point out that the algorithm is fouled by my input and accepts duplicates edges with different values.
Also changed vars to var as is not a good practice to use built-in functions as variable name.
I realized that Graph.get_node() doesn't raise exception if node requested isn't in graph, so I tried to reformulate the method as:
def get_node(self, name: str) -> Node:
node = next((x for x in self.node_list if x.name == name), None)
if node != None :
return node
else:
raise CityNotFoundError(name)