Блог

Я пытаюсь представить такой график на Python:

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

 G = {(i, j): [(i-1, j), (i, j 1), (i 1, j), (i, j-1)] for i in range(0, n) for j in range(0, n)}
 

Затем я могу добавить 4 цикла 4 случая для углов графика или выполнить итерацию по приведенному выше графику и отфильтровать плохие случаи. Какое самое элегантное решение?

PS Я не могу использовать нестандартные библиотеки. Ответ, в котором график представлен списком списков, где индекс каждой строки — это номер вершины, а его значение — узлы, к которым он подключен, был бы еще лучше.

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

Это можно сделать как функцию, но на всякий случай, если вам нужны дополнительные типы графиков или вам нужны дополнительные функциональные возможности (например, какой-нибудь метод, который возвращает, соединены ли две точки), вы также можете запустить класс, вот только один пример того, как вы могли бы это сделать:

 import typing
import itertools

class Graph(object):
    def __init__(self,
                 shape: typing.Tuple[int, int],
                 connectivity: str = "grid"):

        self.nodes = {} # type: typing.Dict[tuple, list]

        self.shape = shape
        self.connectivity = connectivity

        self._init_nodes()

    def _init_nodes(self):
        # iterate through all combinations of coordinates
        for x, y in itertools.product(range(self.shape[0]), range(self.shape[1])):

            # switch in case there are other connectivity types, but for this example just grid
            if self.connectivity == "grid":
                # make and all possible neighbors
                neighbors = [(x-1, y), (x 1, y), (x, y-1), (x, y 1)]
                # filter impossible neighbors
                neighbors = [n for n in neighbors if 0 <= n[0] <= self.shape[0]-1 and 0 <= n[1] <= self.shape[1]-1]
                self.nodes[(x,y)] = neighbors
                    
            else:
                raise NotImplementedError('only grid for now!!!')

 

Который дает словарь подключенных узлов, как у вас в вашем OP, хотя я не совсем уверен, отвечает ли это на вопрос, b / c не может сказать, о чем вы просите в последнем абзаце (мой плохой), поэтому дайте мне знать, если нет:

 >>> a_graph = Graph((5,5))
>>> pprint(a_graph.nodes)

{(0, 0): [(1, 0), (0, 1)],
 (0, 1): [(1, 1), (0, 0), (0, 2)],
 (0, 2): [(1, 2), (0, 1), (0, 3)],
 (0, 3): [(1, 3), (0, 2), (0, 4)],
 (0, 4): [(1, 4), (0, 3)],
 (1, 0): [(0, 0), (2, 0), (1, 1)],
 (1, 1): [(0, 1), (2, 1), (1, 0), (1, 2)],
 (1, 2): [(0, 2), (2, 2), (1, 1), (1, 3)],
 (1, 3): [(0, 3), (2, 3), (1, 2), (1, 4)],
 (1, 4): [(0, 4), (2, 4), (1, 3)],
 (2, 0): [(1, 0), (3, 0), (2, 1)],
 (2, 1): [(1, 1), (3, 1), (2, 0), (2, 2)],
 (2, 2): [(1, 2), (3, 2), (2, 1), (2, 3)],
 (2, 3): [(1, 3), (3, 3), (2, 2), (2, 4)],
 (2, 4): [(1, 4), (3, 4), (2, 3)],
 (3, 0): [(2, 0), (4, 0), (3, 1)],
 (3, 1): [(2, 1), (4, 1), (3, 0), (3, 2)],
 (3, 2): [(2, 2), (4, 2), (3, 1), (3, 3)],
 (3, 3): [(2, 3), (4, 3), (3, 2), (3, 4)],
 (3, 4): [(2, 4), (4, 4), (3, 3)],
 (4, 0): [(3, 0), (4, 1)],
 (4, 1): [(3, 1), (4, 0), (4, 2)],
 (4, 2): [(3, 2), (4, 1), (4, 3)],
 (4, 3): [(3, 3), (4, 2), (4, 4)],
 (4, 4): [(3, 4), (4, 3)]}