Блог

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

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

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

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

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

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

Спасибо!

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

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

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