I'm building a graph class represented as a dict. The graph class is used to perform path finding on a large 2D grid matrix. The nodes are stored as keys and the neighbour nodes are stored as values.
This works nice for fast path searches but I also need to get specific nodes out of the dict determined by their x and y coordinates.
class Node(object):
def __init__(self, x, y):
self.x = x
self.y = y
class Graph(dict):
def get_node_at(self, x, y):
for node in self:
if node.x == x and node.y == y:
return node
def set_neighbours(self):
pass
graph = Graph()
# build a 2d matrix of nodes
for x in range(10):
for y in range(10):
graph[Node(x,y)] = []
# set the neighbour nodes for each node
graph.set_neighbours()
mynode = graph.get_node_at(6,6) # will later be executed quite often
Is there a way to optimize the graph class so the get_node_at method performs better on a large grid?
add an index to Graph which would look like {(x,y):node}. this would require implementing __setitem__ to add the Node to the index, and remove it if another Node already exists and __delitem__ would also remove the Node from the index. this would allow get_node_at(self, x, y) to just do return self.index[(x,y)].