KeyError при проверке правильности пути к графу

Question

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

Мой график представлен в виде {a: {b: c}}, где a и b - вершины, соединенные друг с другом, а c - весребро

Дано:

{0: {1: 5.0, 2: 10.0}, 1: {3: 3.0, 4: 6.0}, 3: {2: 2.0, 4: 2.0, 5: 2.0}, 4: {6: 6.0}, 5: {6: 2.0}, 7: {9: 1.0}, 8: {7: 2.0, 9: 4.0}}

Вершины от 2 до 3 являются допустимым путем.

Мой класс графиков:

class Graph:
    def __init__(self, n):
        """
        Constructor
        :param n: Number of vertices
        """
        self.order = n
        self.size = 0
        self.vertex = {}

    def insert_edge(self, u, v, w): #works fine
        if u in self.vertex and v < self.order:
            if not v in self.vertex[u]:
                self.vertex[u][v] = w
                self.size += 1
        elif u not in self.vertex and u < self.order and v < self.order:
            self.vertex[u] = {}
            self.vertex[u][v] = w
            self.size += 1
        else:
            raise IndexError

    def is_path_valid(self, path):
        while True:
            try:
                s = path.pop(0)
            except IndexError:
                break
            if path:
                d = path.pop(0)
            if s not in self.vertex and d not in self.vertex[s]: #ERROR
                return False
            s = d
        return True

Моя основная функция:

def main():

    g = Graph(10)
    g.insert_edge(0,1,5.0)
    g.insert_edge(0,2,10.0)
    g.insert_edge(1,3,3.0)
    g.insert_edge(1,4,6.0)
    g.insert_edge(3,2,2.0)
    g.insert_edge(3,4,2.0)
    g.insert_edge(3,5,2.0)
    g.insert_edge(4,6,6.0)
    g.insert_edge(5,6,2.0)
    g.insert_edge(7,9,1.0)
    g.insert_edge(8,7,2.0)
    g.insert_edge(8,9,4.0)

True(g.is_path_valid([0, 2]))
True(g.is_path_valid([2, 3]))
True(g.is_path_valid([0, 2, 3]))
False(g.is_path_valid([0, 1, 8]))
False(g.is_path_valid([0, 4, 3]))

    print(g.vertex) #to see the graph
    print(g.is_path_valid([2,3]))

if __name__ == '__main__':
    main()

Моя ошибка:

if s not in self.vertex and d not in self.vertex[s]:
KeyError: 2

Answer 1

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

С другой стороны, вы можете иметь ориентированный граф и при этом иметь функцию, которая добавит «ребра» в том смысле, что она добавит как дуги (u, v), так и (v, u).У меня есть ребра в кавычках, потому что они на самом деле не ребра (термин ребро имеет значение только в неориентированном графе).

from collections import defaultdict

class Graph:
    def __init__(self):
        self._arcs = defaultdict(dict)

    def insert_arc(self, u, v, w):
        self._arcs[u][v] = w

    def is_arc(self, u, v):
        return u in self._arcs and v in self._arcs[u]

    def is_path_valid(self, path):
        for u, v in zip(path, path[1:]):
            if not self.is_arc(u, v):
                return False
        return True

    # We add the notion of "edges" with the following methods:

    def insert_edge(self, u, v, w):
        self.insert_arc(u, v, w)
        self.insert_arc(v, u, w)

    @property
    def edges(self):
        return {((u, v), w) for u, Nu in self._arcs.items() for v, w in Nu.items() if self.is_edge(u, v)}

    def is_edge(self, u, v):
        is_symetric = self.is_arc(u, v) and self.is_arc(v, u)
        if not is_symetric: 
            return False
        return self._arcs[u][v] == self._arcs[v][u]

Теперь вы можете добавить ребра или дуги к вашему графику:

g = Graph()

# This is an arc:
g.insert_arc(1, 8, 1.)

# Weight is not symmetric but this still look like an edge:
g.insert_arc(1, 0, 3.)
g.insert_arc(0, 1, 2.)

# These are all symmetric (ie. "edges")
g.insert_edge(1, 2, 7.)
g.insert_edge(2, 3, 5.)
g.insert_edge(0, 3, 13.)

# we added an arc (1, 8): 
print(g.is_path_valid([1, 8])) # True
print(g.is_path_valid([8, 1])) # False

# All true:
print(g.is_path_valid([0, 3]))  
print(g.is_path_valid([2, 3]))
print(g.is_path_valid([0, 1, 2, 3, 0]))

# Adding one step make this false since (0, 2) doesn't exist:
print(g.is_path_valid([0, 1, 2, 3, 0, 2]))

Мы можем использовать свойство edges, чтобы найти все «ребра» (симметричные дуги с одинаковым весом в обоих направлениях):

>>> print(g.edges)
{((3, 0), 13.0), ((3, 2), 5.0), ((2, 1), 7.0), ((1, 2), 7.0), ((2, 3), 5.0), ((0, 3), 13.0)} 

Обратите внимание, что (0, 1) не является частьюиз набора ребер, это потому, что ссылка существует в обоих направлениях, но вес не одинаков.Дуги (1, 8) здесь явно нет, поскольку (8, 1) не является частью графика.