Блог

Я пытаюсь реализовать графическую структуру данных, представленную списком смежности. Я использую словарь с вершинами в качестве ключей, и каждый ключ может иметь одно или несколько значений. Значение состоит из списка, содержащего другую вершину, к которой подключена ключевая вершина, а также стоимость перехода между вершинами (неориентированный граф). Поскольку вершина может быть соединена с несколькими другими вершинами, значение определенного ключа может состоять из вложенного списка.

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

У меня возникли проблемы с функцией is_connected(self, node1, node2). Я пытаюсь проверить, соединены ли две вершины (в списке смежности), сначала скопировав значения каждого ключа в два отдельных списка. Затем я выполняю понимание списка для каждого списка, чтобы сгладить любой вложенный список. Идея заключалась в том, чтобы проверить, находится ли каждая вершина в списке значений друг друга, и, таким образом, сделать вывод, связаны они или нет.

Проблема, однако, возникает при попытке выполнить понимание списка.

 class UndirectedGraph():
    def __init__(self):
        self.vertices = my_dict = {
                                    'A' : ['B', 10],
                                    'B' : [['A', 10], ['C', 5]],
                                    'C' : [['B', 5], ['D', 15]],
                                    'D' : [['C', 15], ['E', 25]],
                                    'E' : ['D', 25]
                                                    }
    def __str__(self):
        return str(self.vertices)

    def add(self, new_node):
        if new_node in self.vertices:
            return False
        else:
            self.vertices[new_node] = []
            return True

    def connect(self, node1, node2, cost):
        if node1 in self.vertices and node2 in self.vertices:
            if self.is_connected(node1, node2):
                for x, y in [(x, y) for x in self.vertices.get(node1) for y in self.vertices.get(node2)]:
                    if node2 in x and node1 in y:
                        x[1] = cost
                        y[1] = cost
            else:
                if node1 == node2:
                    node1_values = [node2, cost]
                    self.vertices[node1].append(node1_values)
                else:
                    node1_values = [node2, cost]
                    self.vertices[node1].append(node1_values)
                    node2_values = [node1, cost]
                    self.vertices[node2].append(node2_values)

    def is_connected(self, node1, node2):
        node1_values = self.vertices[node1]
        node2_values = self.vertices[node2]
        n1 = [str(item) for sublist in node1_values for item in sublist]
        n2 = [str(item) for sublist in node2_values for item in sublist]

        if node2 in n1 and node1 in n2:
            print(node1, "and", node2, "are connected")
            return True
        else:
            print(node1, "and", node2, "are not connected")
            return False
  

Я создаю n экземпляров класса и вызываю метод is_connected(self, node1, node2)

 g = UndirectedGraph()
g.is_connected('A', 'B')
  

Я получаю следующую ошибку:

 Traceback (most recent call last):
  File ".UndirectedGraph.py", line 83, in <module>
    g.is_connected('A', 'B')
  File ".UndirectedGraph.py", line 53, in is_connected
    n1 = [str(item) for sublist in node1_values for item in sublist]
  File ".UndirectedGraph.py", line 53, in <listcomp>
    n1 = [str(item) for sublist in node1_values for item in sublist]
TypeError: 'int' object is not iterable
  

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

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

Как мне решить эту проблему?

Заранее спасибо! Или есть какой-либо

Сравните эти два узла (из вашего self.vertices dict):

 'A' : ['B', 10],
'B' : [['A', 10], ['C', 5]],
  

Я предполагаю, что это должно представлять, что узел ‘A’ имеет ребро к узлу ‘B’ стоимостью 10, а узел ‘B’ имеет то же ребро плюс другое ребро к узлу ‘C’ стоимостью 5. По сути, ваш vertices dict должен отображать имя узла (например, ‘A’) в «список ребер с их стоимостью». Однако для узла ‘A’ вы забыли включить внешний список: значение dict не является вложенным списком. Исправление простое:

         # in you __init__ function
        self.vertices = my_dict = {
                                    'A' : [['B', 10]],
                                    'B' : [['A', 10], ['C', 5]],
                                    'C' : [['B', 5], ['D', 15]],
                                    'D' : [['C', 15], ['E', 25]],
                                    'E' : [['D', 25]]
                                                    }
  

С этим исправлением я получаю:

 >>> g = UndirectedGraph()
>>> g.is_connected('A', 'B')
('A', 'and', 'B', 'are connected')