Оптимизировать график для поиска пути и получения узлов в определенных координатах - PullRequest
Новая
       23

Оптимизировать график для поиска пути и получения узлов в определенных координатах

0 голосов
/ 15 июля 2011

Я строю графовый класс, представленный как dict. Класс графа используется для поиска пути в большой двумерной матрице сетки. Узлы хранятся в виде ключей, а соседние узлы хранятся в виде значений.

Это хорошо работает для поиска по быстрому пути, но мне также нужно вывести определенные узлы из условия, определяемого их координатами x и y. 

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

Есть ли способ оптимизировать класс графа, чтобы метод get_node_at работал лучше на большой сетке?

1 Ответ

1 голос
/ 15 июля 2011

добавить индекс к Graph, который будет выглядеть как {(x,y):node}. это потребовало бы реализации __setitem__ для добавления Node к индексу и удаления его, если другой Node уже существует, а __delitem__ также удалил бы Node из индекса. это позволило бы get_node_at(self, x, y) просто сделать return self.index[(x,y)].

...