使用 networkx (Python) 创建并执行任务工作流

Question

总结：

目标是运行从步骤集合（图节点）及其依赖项（图边）创建的工作流。

是否可以创建一个 networkx.DiGraph() 和运行在不同节点上执行回调的遍历？

示例：

请查看示例图：

对于那组任务和依赖项，执行的可能性是：

步骤a作为切入点
步骤 b 紧接着步骤 a
步骤 c 和 d 在步骤 b 之后并行（步骤 c 先完成）
步骤 g 紧跟在步骤 c 之后（步骤 d 仍在进行中）
步骤 e 紧跟在步骤 d 之后（因为步骤 c 已经完成）
步骤 f 紧接着步骤 e

或者，

步骤a作为切入点
步骤 b 紧接着步骤 a
步骤 c 和 d 在步骤 b 之后并行（步骤 d 先完成）
步骤 g 和 e 并行（因为步骤 d 在步骤 c 之前完成）
步骤 f 紧接着步骤 e

请在下方找到用于在 networkx 中创建此示例图的代码片段：

import networkx as nx

W = nx.DiGraph()

nodes = ["a", "b", "c", "d", "e", "f"]
edges = [("a", "b"), ("b", "c"), ("c", "g"), ("b","d"), ("c", "e"), ("d", "e"), ("e", "f")]
W.add_nodes_from(nodes)
W.add_edges_from(edges)

是否有已知的解决方案以前面描述的方式遍历图形，打印节点的值（步骤名称）并随机休眠几秒以模拟任务运行ning 并执行一些计算？（使用基本的多线程）

谢谢。

Answer 1

拓扑排序 (nx.topological_sort) 将 return 是任务的有效序列。
示例：

>>> list(nx.topological_sort(W))
['a', 'b', 'd', 'c', 'e', 'f', 'g']

如果您想要可以同时执行的任务组，您可以稍微更改它以执行分组。

def topological_sort_grouping(g):
    # copy the graph
    _g = g.copy()
    res = []
    # while _g is not empty
    while _g:
        zero_indegree = [v for v, d in _g.in_degree() if d == 0]
        res.append(zero_indegree)
        _g.remove_nodes_from(zero_indegree)
    return res

示例：

>>> topological_sort_grouping(W)
[['a'], ['b'], ['c', 'd'], ['e', 'g'], ['f']]

给定组，您可以迭代它们并同时执行同一组中的组。

使用 networkx (Python) 创建并执行任务工作流

Create and execute a workflow of tasks with networkx (Python)

python

multithreading

graph

task

networkx

总结：

示例：