Метод, который добавляет ребра графа до всех узлов данной степени


Тренировки 2-3 в думаю сложность: сложность науки и компьютерного моделирования Аллен Б. Дауни просит нас реализовать метод для класса неориентированных графов:

Написать метод с именем add_regular_edges что начинается с пейзажным график и добавляет ребра так, что каждая вершина имеет такой же степени. На степень узла-количество ребер он подключен.

Чтобы создать регулярный граф степени 2, вы могли бы сделать что-то вроде этого:

vertices = [ ... list of vertices ...]
g = Graph(vertices, [])
g.add_regular_edges(2)

Это не всегда возможно создать регулярный граф с заданной степенью, так что вы должны выяснить и задокументировать предпосылки для этого способ.

Это было немного трудно для меня, так как я до сих пор получаю комфортно с Python. Здесь было то, что мое решение выглядело бы (тяжело прокомментировал для себя и других):

def add_regular_edges(self, deg):

    #for every node in the graph
    for v in self:

        #set the degree tolerance to 1
        tol = 1

        #while the degree of current node is less than the given degree
        while self.degree(v) < deg:

            #traverse over every node
            for w in self:

                '''if the 2 nodes do not equal one another, the current degree (v) is less than the given degree,
                and the other node (w) is less than the current tolerance -> add the edge'''
                if v != w and (self.degree(v) < deg) and (self.degree(w) < tol):
                    self.add_edge(Edge(v,w))

            #increase the tolerance in case we could not fill all nodes in the first pass
            tol += 1

            #if at any point the tolerance is more than the degree, then we cannot complete the graph with the given degree
            if tol > (deg+1):
                raise ValueError("The graph cannot be converted to the given degree")

Однако, у меня есть сильное подозрение, что это не самый оптимальный способ пойти об этом. Один из моих друзей заметил, что я мог бы сделать это с помощью списков и перечисление за них?



99
2
задан 4 февраля 2018 в 09:02 Источник Поделиться
Комментарии