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

С версией smack 4.2.0-rc2-SNAPSHOT легко получить доступ,

DelayInformation delayInformation = forwarded.getDelayInformation();
delayInformation.getStamp().getTime();
23
задан Pete Kirkham 20 August 2009 в 15:55
поделиться

2 ответа

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

30
ответ дан 29 November 2019 в 02:08
поделиться

Вам нужен поиск в глубину.

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.

9
ответ дан 29 November 2019 в 02:08
поделиться
Другие вопросы по тегам:

Похожие вопросы: