Постепенно обнаруживать доминаторов в Дагс

Предположим, что у нас есть DAG с одним источником. Я хотел бы найти узлы n такие, что любой полный путь от источника проходит через n (т. е. n доминирует над всеми приемниками). Другими словами: если мы удалим все последователи n, то все пути закончатся в n. Проблема заключается в том, что узлы постепенно помечаются как удаленные в DAG. Поскольку узлы помечены как удаленные, другие узлы могут начать удовлетворять вышеуказанному свойству. Как я могу эффективно обнаружить это, когда это происходит?

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

1 6
algorithm data-structures directed-acyclic-graphs

1 ответ:

Топологически отсортировать эта группа, чтобы установить какой-то порядок для его узлов. Для каждого узла его значение будет равно числу исходящих ребер из всех предыдущих узлов минус число входящих ребер во все предыдущие узлы и текущий узел. Значение для узла "доминатор" всегда равно нулю.

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

delete(delNode):
  for each predecessor in delNode.predecessors: queue.add(predecessor)
  for each successor in delNode.successors: queue.add(successor)
  for each node in DAG:
    if queue.top.priority == node.priority > delNode.priority:
      ++accumulator

    node.value += accumulator
    if node.value == 0: dominatorDetected(node)

    if node.priority == delNode.priority:
      accumulator += (delNode.predecessors.size - delNode.successors.size)
      node.value = -1

    if queue.top.priority == node.priority:
      queue.pop()
      if node.priority < delNode.priority:
        --accumulator

    if queue.empty: stop

Для нескольких в исходном случае можно использовать тот же алгоритм, но сохранить список "значений" для каждого узла, по одному значению для каждого источника. Сложность алгоритма O(Nodes * Sources) такая же, как и для независимого поиска по каждому из источников. Но программа может быть сделана более эффективной, если используется векторизация. "значения" могут обрабатываться параллельно с инструкциями SIMD. Современные компиляторы могут выполнять автоматическую векторизацию для достижения этой цели.

3