Блог

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

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

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

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

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

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

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