Что это за тип графика и какой алгоритм я могу использовать для его перемещения?

Question

У меня есть сеть «узлов», каждый узел производит «результаты». Каждый узел и результат имеют уникальное имя/id. Результаты используются как входные, так и выходные данные для каждого узла. Когда все входные результаты доступны для узла, он может быть выполнен. Когда узел завершит выполнение своих выходных результатов, будет доступно.

Так, например:

input node output 
     A x 
x  B y,z 
x,z C q 

В данной сети. Узел A не имеет входных данных и может быть выполнен первым. Тогда B можно выполнить, когда результат x станет доступным. Когда выполняются как A, так и B, C может выполняться, потому что это зависит от результатов от A и B. Результат также может быть конечным продуктом, например y в этом случае, который не используется как вход для любого узла.

Сеть может быть намного сложнее. Каждый узел может создавать ряд результатов и может иметь несколько зависимостей ввода.

Я хотел был бы иметь возможность выбрать результат, сказать «q» и выяснить, какие узлы необходимо выполнить, чтобы добраться туда. Я хочу сделать это для нескольких результатов в более широкой сети узлов.

Я чувствую, что это общий алгоритм, но у меня нет опыта в этой области. Он не является иерархическим, как дерево, поскольку зависимости могут создавать круги. Из того, что я читал, я думаю, что это должен быть тип графа леса.

В любом случае он должен быть проезжим. Всегда есть хотя бы один узел, который может быть выполнен первым, а все остальные должны иметь возможность следовать в некотором порядке, не создавая тупик, где два узла ждут друг друга.

Каков общий способ описания этой сети/ее узлов в коде и что будет официальным названием для такой сети?

Answer 1

Имя, которое вы ищите, является 'graph graph'.

Алгоритм, используемый для разрушения называется «топологической сортировки» (см: http://en.wikipedia.org/wiki/Topological_sorting)

Один из самых известных инструментов разрешающих таких зависимостей называется сделать.

Makefile, соответствующий ваш пример будет выглядеть примерно так:

x : 
    echo node A 

y z : x 
    echo node B 

q : x z 
    echo node C 

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

Ввод make <TARGET> вы можете легко проверить, что он разрешает узлы в том порядке, в котором вы хотите.Вот некоторые примеры:

make q 
    * node A 
    * node B 
    * node C 

make x 
    * node A 

make z 
    * node A 
    * node B 

(Для того, чтобы сделать вывод немного покрасивее это версия используется для вывода выше:

x : 
    @echo " * node A" 

y z : x 
    @echo " * node B" 

q : x z 
    @echo " * node C" 

)

Answer 2

Помимо просто быть тип графика , похоже, что семантика, которую вы хотите, это что-то вроде Petri net с цветными жетонами. Анализ достижимости сетей Петри - это хорошо известная проблема, для которой существуют алгоритмы в литературе. Возможно, статья Википедии даст вам некоторые идеи, с которых можно начать.