Dict obj 在查找图的度数时没有属性计数

Question

我正在实现一个图 class 并且想编写一个函数来计算给定顶点的度数。我的 degree 函数出现类型错误，因为我想使用 .count 来计算顶点 v.

的实例数

我的图表表示为{a:{b:c}} 其中a和b是相互连接的顶点，c是边的权重

鉴于：

{0: {1: 5, 2: 5}, 2: {3: 5}, 1: {3: 5}, 4: {1: 5, 3: 5}}

顶点 1 的度数为 3，因为它连接到顶点 0,3 和 4。

我的class:

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 degree(self, v):
        adj_vertices =  self.vertex[v]
        degree = len(adj_vertices) + adj_vertices.count(v) #ERROR in .count
        return degree

主要功能：

def main():
    g = Graph(5)
    g.insert_edge(0,1,5)
    g.insert_edge(0,2,5)
    g.insert_edge(2,3,5)
    g.insert_edge(1,3,5)
    g.insert_edge(4,1,5)
    g.insert_edge(4,3,5)

    print(g.vertex) #print the graph
    print(g.degree(1)) #error, should print out 3

if __name__ == '__main__':
    main()

我的错误：

AttributeError: 'dict' object has no attribute 'count'

Answer 1

您将图形表示为字典中的字典，并尝试调用内部字典的计数，这不是一般字典的函数。为什么你不简单 return

def degree(self, v):
    return len(self.vertex[v])

您是否想看一下包 networkx。

Answer 2

.count() 是列表的一种方法，不是字典。在这种情况下，您想找到所有其他以 v 作为元素的顶点。

def degree(self, v):
        adj_vertices =  self.vertex[v]
        others_connecting = [other for other in self.vertex.values() if v in other]
        degree = len(adj_vertices) + len(others_connecting)
        return degree

这是我的方法，self.vertex.values() 给你一个字典对象列表，列表理解过滤器使结果列表只包含其他连接的顶点。

Answer 3

我会重构你的度数函数的逻辑如下。我正在检查键是否等于顶点 v，我计算该字典中有多少项，或者如果在子字典中，其中有多少包含顶点 v 作为字典

def degree(self, v):
    degree = 0
    for key, value in self.vertex.items():
        if key == v:
            degree += len(value)
        elif v in value:
            degree += 1
    return degree

一旦我运行这个，我得到


print(g.vertex)
print(g.degree(0))
print(g.degree(1))
print(g.degree(2))
print(g.degree(3))
print(g.degree(4))
#{0: {1: 5, 2: 5}, 2: {3: 5}, 1: {3: 5}, 4: {1: 5, 3: 5}}
#2
#3
#2
#3
#2

Answer 4

graph = {0: {1: 5, 2: 5}, 2: {3: 5}, 1: {3: 5}, 4: {1: 5, 3: 5}}
v = 1
len (graph [v]) + reduce (lambda x, y: x + (1 if v in graph [y] else 0), graph, 0)

为我输出 3。

说明

如果图中有从 y 到 v 的边，

1 if v in graph [y] else 0 的计算结果为 1，否则为 0。

reduce (lambda x, y: x + (1 if v in graph [y] else 0), graph, 0) 计算出边从它们到 v.

的顶点数

len (graph [v]) 计算出从 v 到其他顶点的边数。

整个表达式计算从v到其他顶点的边数加上从那时到v有边的顶点数，即计算v的度数。

Dict obj 在查找图的度数时没有属性计数

Dict obj has no attribute count when finding degree of a graph

python

graph

graph-algorithm