时间戳

首页 > 解决方案 > 返回依赖节点的有序列表

python - 返回依赖节点的有序列表

问题描述

我正在创建一个程序，询问有多少节点，如果有的话依赖于另一个，然后输出最终的有序列表。例如，如果有 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']or ['c', 'b', 'a']，只要“父”节点在从属节点之前。

编辑：循环依赖是无效的。因此，如果a依赖于c，反之亦然，则会出现错误消息。

标签： pythonpython-3.xinheritancegraphnodes

解决方案

前言： 我认为这是一个图论/寻路问题。然而，几乎所有事情都可以表示为图论问题——对我来说，这种解释似乎最简单，其他方法可能对你更有效。
请注意，我将任务分解为几个较小的步骤：获取一个简单的“依赖关系图”，生成所有可能的路径，并验证每个路径，直到找到一个可以验证的路径。

解决方案

如果节点的数量相对较少，您可以尝试生成所有路径，然后检查每个路径以查看其中一个是否有效。

我没有对下面的代码进行广泛的测试，但这样的事情是一个好的开始：

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 个）。

推荐阅读