Как проверить дополнительную информацию о конфликте в графе зависимостей? - PullRequest
Новая
       40

Как проверить дополнительную информацию о конфликте в графе зависимостей?

0 голосов
/ 05 октября 2011

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

Но как насчет информации о конфликте? Я имею в виду структуру, где у вас есть: 

V - a set of items
E - a set of dependency edges: E\subset V\times V
C - a set of conflict edges: C\subset V\times V

Каков стандартный алгоритм проверки наличия в графе зависимостей информации о конфликте, которая не может быть удовлетворена?

Например: 

V = { a, b, c }
E = { ( a -> b), (b->c) }
C = { (a -> c) }

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

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

1 Ответ

2 голосов
/ 07 октября 2011

Я не знаю о стандартном алгоритме , но это работает:

  1. Как обычно, найдите топологический вид (V,E) (возвращая нестабильную, если циклическая зависимостьнайдено).
  2. В DFS / BFS пометьте каждый след / компонент зависимости однозначно (пояснение ниже).
  3. Обход C и убедитесь, что пары (u,v) не существует, так чтоlabel(u) = label(v).Если есть такая пара ==> вернуть нестабильно, иначе ==> вернуть стабильно.

Время выполнения O(|E|+|V|+|C|):
Поскольку топологическая сортировка и DFS являются линейнымив (V,E), а третья часть является линейной в C.

Объяснение этапа 2:

Мы начинаем с вершины графа зависимостей (илиесли хотите, начало топологической сортировки), выберите первый узел и первую метку, скажем 1.Мы пересекаем каждое ребро в графе способом DFS (или BFS);пока мы все еще на связи, мы продолжаем маркировать узлы одной и той же меткой.Как только подключение «заканчивается», мы увеличиваем метку и продолжаем в DFS / BFS.

Т.е. все достижимое с первого узла помечено 1.Как только мы исчерпали достижимость этого узла (внешний цикл в алгоритме DFS или BFS), мы увеличиваем метку и выбираем следующий неисследованный узел.

Подтверждение правильности:

Мы делаем одно ключевое замечание - что график нестабилен, если существует некоторая пара (u,v) в C такая, что label(u) = label(v).

Во-первых, я не имею в виду элементы в C как указано, потому что существует симметрия.Если (u -> v) в C, это означает, что, по вашим словам, данное u, v не может существовать.Таким образом, они не могут существовать вместе, то есть ни u не может зависеть от v (потому что для существования u должно существовать v, что невозможно), ни наоборот.

С этим пониманием мы можем доказать вышеупомянутое наблюдение:
Мы отмечаем, что label(u) = label(v), если либо u зависит от v, либо наоборот.Это простой результат построения, где достижимость (и, следовательно, зависимость) определяла метки.Поэтому, если мы предположим, что у нас есть такая пара, график нестабилен (как объяснено в предыдущем параграфе).

Другое направление наблюдения (пара неустойчивых ==>) также легко увидеть.Если мы предположим, что график нестабилен, то существует некий u, который не может существовать.Этот u зависит либо от чего-то конфликтующего, либо от него зависит какой-то другой узел, и эта пара конфликтует.В любом случае, мы нашли пару (u,v) в C с одинаковой меткой.

...