1

假设我有一个基于信号流的“程序”图(例如类似于 Simulink 的东西)。即我有一个有向图,有几个起始节点和几个结束节点以及中间的许多节点(希望没有循环关系)

是否有一个好的和/或众所周知的算法(甚至可以作为 Python 库使用)来遍历该图并给我计算顺序?

示例(方向未显示,假设显而易见):

输入 1 输入 2
   \ \
    [-] [*]-- 输出 1
   / \ /
输入 3 [+]----- 输出 2
       /
    In4

这应该导致说明/顺序:

1. tmp1 := In1 - In3
2. Out2 := tmp1 + In4
3. 输出 1 := 输入 2 * 输出 2

谢谢!

4

1 回答 1

3

您是否正在寻找拓扑排序的某种变体?

由于您知道起始节点,因此您可以从它们开始算法。当您遇到“操作”节点时,您将使用引导您到达它的节点创建计算。自然地,图表应该在某些特定于您的问题的方面保持一致。

要在 Python 中实现这一点,您需要一个好的图形库(例如NetworkX)。拓扑排序实现起来非常简单,许多图形库已经将其作为实现算法。例如,对于 NetworkX - networkx.algorithms.dag.topological_sort。但是,如上所述,它可能不完全是拓扑排序,而是其变体。

于 2011-04-27T08:22:27.880 回答