Проблемы с простым алгоритмом зависимостей

В моем webapp мы имеем много полей, которые суммируют другие поля, и эти поля суммируют больше полей. Я знаю, что это ориентированный ациклический граф.

Когда страница загружается, я вычисляю значения для всех полей. То, что я действительно пытаюсь сделать, - это преобразовать мою DAG в одномерный список, который будет содержать эффективный порядок расчета полей.

Например: A = B + D, D = B + C, B = C + E Эффективный расчетный порядок: E → C → B → D → A

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

Ответ 1

Вы ищете топологическую сортировку? Это налагает порядок (последовательность или список) на DAG. Он используется, например, для электронных таблиц, для определения зависимостей между ячейками для вычислений.

Ответ 2

То, что вы хотите, это поиск по глубине.

function ExamineField(Field F)
{
    if (F.already_in_list)
        return

    foreach C child of F
    {
        call ExamineField(C)
    }

    AddToList(F)
}

Затем просто вызовите ExamineField() в каждом поле по очереди, и список будет заполнен в оптимальном порядке в соответствии с вашим спецификацией.

Обратите внимание, что если поля являются циклическими (то есть у вас есть что-то вроде A = B + C, B = A + D), тогда алгоритм должен быть изменен так, чтобы он не переходил в бесконечный цикл.

В вашем примере вызовы будут идти:

ExamineField(A)
  ExamineField(B)
    ExamineField(C)
      AddToList(C)
    ExamineField(E)
      AddToList(E)
    AddToList(B)
  ExamineField(D)
    ExamineField(B)
      (already in list, nothing happens)
    ExamineField(C)
      (already in list, nothing happens)
    AddToList(D)
  AddToList(A)
ExamineField(B)
  (already in list, nothing happens)
ExamineField(C)
  (already in list, nothing happens)
ExamineField(D)
  (already in list, nothing happens)
ExamineField(E)
  (already in list, nothing happens)

И список будет заканчиваться C, E, B, D, A.