Dict obj не имеет счетчика атрибутов при поиске степени графа

Question

Я реализую класс графа и хотел бы написать функцию, которая вычисляет степень заданной вершины. Я получаю ошибку типа в своей функции степени, потому что я хотел бы использовать .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 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

.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 2

Я бы реорганизовал логику вашей функции степени следующим образом.Я проверяю, равен ли ключ вершине 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 3

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 для меня.

Объяснение

1 if v in graph [y] else 0 оценивается как 1, если на графике есть ребро от y до v, и до 0 в противном случае.

reduce (lambda x, y: x + (1 if v in graph [y] else 0), graph, 0) оценивается числом вершин, ребра которых от них до v.

len (graph [v]) определяет количество ребер от v до других вершин.

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

Answer 4

Вы представляете график как dict of dicts и пытаетесь вызвать счетчик внутреннего dict, который не является функцией общего dict. Почему бы вам просто не вернуть

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

и, возможно, вы захотите взглянуть на пакет networkx.