Как вывести список зависимых узлов?

Question

Я создаю программу, которая запрашивает, сколько существует узлов, если они есть, зависят от другого, и затем выводит окончательный упорядоченный список. Например, если есть 3 узла ['a', 'b', 'c'], если b зависит от c, то окончательный список будет выглядеть следующим образом: ['a', 'c', 'b'] (поскольку c будет предшествовать b).

Я искал что-то, что называется инъекцией зависимости, однако это не совсем понятно для меня и еще больше сбивает с толку.

Пока мой код:

import string
alpha = string.ascii_lowercase          # Importing the alphabet to convert

def convert(x):                         # Converting the numeric value into alphabetic character
    for i in range(1, x):
        return list(alpha[0:x])

x = int(input("Enter how many nodes there are:  "))
print(convert(x))

new_list = []

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

Я хочу знать, как сделать что-то вроде:

Which node is node 'a' dependent on?  (Input: None)
Which node is node 'b' dependent on?  (Input: c)
Which node is node 'c' dependent on?  (Input: None)

output: ['a', 'c', 'b']

Если есть узел, который не связан ни с каким другим, не имеет значения, в каком порядке он находится, поэтому выходные данные также могут быть ['c', 'a', 'b'] или ['c', 'b', 'a'], пока узел «родитель» находится перед зависимый узел.

Редактировать: Круговые зависимости недействительны. Поэтому, если a зависит от c и наоборот, появится сообщение об ошибке.

Answer 1

Предисловие: Я вижу это как проблему теории графов / поиска путей Однако почти все можно представить как проблему теории графов - для меня эта интерпретация кажется самой простой, что-то еще может работать лучше для вас.
Обратите внимание, что я разбил задачу на несколько небольших этапов: получение упрощенного «графа зависимостей», генерация всех возможных путей и проверка каждого пути до тех пор, пока не будет найден тот, который проверяет.

Решение

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

Я не тестировал подробно приведенный ниже код, но что-то вроде этого - хорошее начало:

import itertools
import string


def get_nodes():
    alpha = string.ascii_lowercase  # Importing the alphabet to convert
    x = int(input("Enter how many nodes there are:  "))
    return list(alpha[0:x])


def get_dependency_graph(nodes):
    dependency_graph = {}

    for node in nodes:
        dependent_node = input(f"Which node is node {node} dependent on? (press Enter if none) ") or None
        dependency_graph[node] = dependent_node
    return dependency_graph


def generate_all_paths(nodes):
    return itertools.permutations(nodes)


def validate_path(path, dependency_graph):
    for i, node in enumerate(path):
        head = path[:i]
        dependency = dependency_graph[node]
        if not dependency:
            continue
        if dependency_graph[node] not in head:
            return False
    return True


def get_valid_path(nodes, dependency_graph):
    possible_paths = generate_all_paths(nodes)
    for path in possible_paths:
        if validate_path(path, dependency_graph):
            return path
    print("No path found :(")


def run():
    nodes = get_nodes()
    dependency_graph = get_dependency_graph(nodes)
    path = get_valid_path(nodes, dependency_graph)
    print(path)


if __name__ == "__main__":
    run()

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