Проблема с сортировкой зависимостей сложных модулей Python

У меня есть набор "модулей" с зависимостями.

модуль B зависит от A модуль C зависит от A и B модуль D зависит от C

Я могу представить каждый модуль как объект, а их зависимости как свойство:

class Module():

    def __init__(self, name):
        self.dependencies = []
        self.name = name

    def __repr__(self):
        return self.name


A = Module("A")
A.dependencies = []

B = Module("B")
B.dependencies = [A]

C = Module("C")
C.dependencies = [A, B]

D = Module("D")
D.dependencies = [C]

modules = [C, D, B, A]

Предположим, у меня есть список модулей в произвольном порядке, например, [C, D, B, A]

Нужно написать функцию, которая будет принимать этот входной список и возвращать список всех этих модулей в порядке зависимости:

Например, [A, B, C, D], начиная с A, потому что у него нет зависимостей, затем B, потому что он зависит только от A, затем C, D по тем же причинам. Я застрял в этом, пожалуйста, помогите с кодом, псевдокодом

"""

class Module():
    def __init__(self, name):
        self.dependencies = []
        self.name = name

    def __repr__(self):
        return self.name

# normal modules
A = Module("A")
B = Module("B")
C = Module("C")
D = Module("D")
E = Module("E")
F = Module("F")

A.dependencies = []
B.dependencies = [A]
C.dependencies = [B]
D.dependencies = [A, C]
E.dependencies = []
F.dependencies = [B]

# modules that do not follow alphabetical order, so that just sorting modules don't work either
M = Module("M")
N = Module("N")

M.dependencies = [N]
N.dependencies = []

#simple circular dependency
X = Module("X")
Y = Module("Y")

X.dependencies = [Y]
Y.dependencies = [X]

# advanced circular dependency
P = Module("P")
Q = Module("Q")
R = Module("R")
S = Module("S")

P.dependencies = [S]
Q.dependencies = [P]
R.dependencies = [Q]
S.dependencies = [R]

def is_answer_valid(the_input):
    # don't worry about changing this method. Just believe me: it works!
    answer = sort_modules(list(the_input))
    answer_temp = list(answer)
    if len(answer) != len(the_input):
        print("{} is not a valid answer for {}".format(answer, the_input))
        return False
    # print("------------")
    # print(answer_temp)
    loaded_modules = []
    while len(answer_temp) > 0:
        module = answer_temp.pop(0)
        if module in loaded_modules:
            print("{} is not a valid answer for {}".format(answer, the_input))
            return False
        for dep in module.dependencies:
            if dep not in loaded_modules:
                print("{} is not a valid answer for {}".format(answer, the_input))
                return False
        loaded_modules.append(module)
        # print("-- {}-{}".format(answer_temp, loaded_modules))
    # print("{}->{}".format(the_input, answer))
    return True

def answer_is_circular(the_list):
    # don't worry about changing this method either. Just believe me: it works!
    result = None
    try:
        result = sort_modules(the_list)
    except:
        return True
    msg = "You code did not detect circular dependencies for {}. It returned {} instead of raising an exception."
    print(msg.format(the_list, result))

##################################################################

def sort_modules(modules):
    #this is the method that needs to be implemented. Feel free to add submethods if you want. It may or may not be necessary.
    return list()

##################################################################

print("Tests will run below. Only errors will be shown. If nothing is shown, its fine!")
is_answer_valid([C, D, B, A])

is_answer_valid([A, B, C, D, E])
is_answer_valid([A, B, D, C, E])
is_answer_valid([A, E, D, C, B])
is_answer_valid([A, B, D, C, E])
is_answer_valid([B, A, E, C, D])
is_answer_valid([C, B, A, D, E])

is_answer_valid([D, C, E, B, A])
is_answer_valid([D, C, B, A])
is_answer_valid([A, C, B, D])
is_answer_valid([])
is_answer_valid([E])
is_answer_valid([A])
is_answer_valid([A, E])
is_answer_valid([B, A])
is_answer_valid([A, B])
is_answer_valid([A, B, C])
is_answer_valid([A, C, B])
is_answer_valid([B, A, C])
is_answer_valid([B, C, A])
is_answer_valid([C, B, A])
is_answer_valid([C, A, B])

is_answer_valid([M, N])
is_answer_valid([N, M])
is_answer_valid([C, B, A, D, M, E, N])
is_answer_valid([C, N, B, A, D, M, E])

answer_is_circular([A, C, X, B, Y, D])
answer_is_circular([X, Y])
answer_is_circular([P, Q, R, S])
answer_is_circular([A, P, C, X, R, B, S, Q, Y, D])
answer_is_circular([A, P, C, R, B, S, Q, D])

Вернуться на верх