Постепенно обнаруживая доминаторы в DAG - PullRequest
Новая
       37

Постепенно обнаруживая доминаторы в DAG

6 голосов
/ 06 февраля 2012

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

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

1 Ответ

3 голосов
/ 06 февраля 2012

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

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

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. Современные компиляторы могут выполнять автоматическую векторизацию для достижения этой цели.

...