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

Question

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

1

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

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

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

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

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

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

Спасибо!

Chris 27 апр. 2011, в 11:03

Источник

Теги:

python

algorithm

graph

graph-theory

graph-traversal

1 ответ

Ещё вопросы

Eli Bendersky · Accepted Answer · 2011-04-27T05-42-00.000Z

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

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

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

Спасибо! «Топологическая сортировка» - это ключевое слово, которое я искал и не смог найти себя!