0

我正在实现一个图形类，并想编写一个计算给定路径是否有效的函数。我的 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
4

1 回答 1

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)它不是图表的一部分。

于 2019-04-12T17:50:09.967 回答