Алгоритм "Авто код" для программирования потока сигналов?

Question

Давайте предположим, что у меня есть график "программы", основанной на потоке сигналов (например, что-то похожее на Simulink). То есть У меня есть ориентированный граф с несколькими начальными узлами и несколькими конечными узлами, а также множеством промежуточных узлов (и, надеюсь, без кругового отношения)

Есть ли хороший и / или хорошо известный алгоритм (возможно, даже доступный в виде библиотеки Python), который будет обходить этот граф и определять порядок вычислений?

Пример (направление не указано, предположите очевидное):

In1     In2
   \       \
    [-]     [*]-- Out1
   /   \   /
In3     [+]------ Out2
       /
    In4 

Это должно привести к инструкциям / заказу:

1. tmp1 := In1 - In3
2. Out2 := tmp1 + In4
3. Out1 := In2 * Out2

Спасибо!

Answer 1

Вы ищете какой-то вариант топологической сортировки ?

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

Чтобы реализовать это в Python, вам нужна хорошая библиотека графов (например, NetworkX ). Топологическая сортировка очень проста в реализации, и многие библиотеки графов уже используют ее как реализованный алгоритм. Например, в случае NetworkX - networkx.algorithms.dag.topological_sort . Однако, как упоминалось выше, это, вероятно, не точно топологический тип, а его разновидность.