Участник:Lizord/Алгоритм Джонса Плассмана

Файл:Warning sign font awesome.svg

Данная страница в настоящее время активно редактируется участником Lizord (обсуждение). Пожалуйста, не вносите в неё никаких изменений до тех пор, пока не исчезнет это объявление. В противном случае могут возникнуть конфликты редактирования.

Основные авторы описания: Демаков М. А.

Алгоритм Джонса-Плассмана
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(|V| + |E|) }[/math]
Объём входных данных	[math]\displaystyle{ 8|E| }[/math]
Объём выходных данных	[math]\displaystyle{ |V| }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(\frac{log(V)}{log log(V)}) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(log(V)) }[/math]

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм Джонса-Плассмана - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей.

Математическое описание алгоритма

Исходные данные: граф [math]\displaystyle{ G = G(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, а [math]\displaystyle{ E }[/math] - множество ребёр.
Вычисляемые данные: вектор цветов [math]\displaystyle{ c = \{c_i\} }[/math] размерности [math]\displaystyle{ |V| }[/math]

Для раскраски графа, необходимо проделать следующие шаги:

1. Обозначим множество нераскрашенных вершин как [math]\displaystyle{ V' = V }[/math].
   
2. На каждой итерации будем выделять максимальное независимое подмножество вершин [math]\displaystyle{ I \subset V' }[/math], которое раскрашивается параллельно.
   1. Для каждой вершины [math]\displaystyle{ v_i \in V' }[/math] назначается уникальная случайная метка [math]\displaystyle{ p(v_i) }[/math]
   2. [math]\displaystyle{ v_i \in I \Leftrightarrow p(v_i) \gt p(w), \forall w \in adj(v_i) }[/math]
3. После этого полагаем [math]\displaystyle{ V' = V'\;\backslash\;I }[/math]. Алгоритм работает, пока [math]\displaystyle{ V' \neq \emptyset }[/math].

Для раскраски вершины [math]\displaystyle{ v_i \in I }[/math] необходимо назначить ей цвет [math]\displaystyle{ c_i }[/math] такой, что [math]\displaystyle{ c_i \notin N_c(v_i) }[/math], где [math]\displaystyle{ N_c(v_i) }[/math] - цвета вершин, соседних для [math]\displaystyle{ v_i }[/math]. Это можно сделать последовательным перебором, это займёт в худшем случае Δ итераций (Δ - наибольшая из степеней графа).

Функции приоритета

Существуют различные способы определять функцию приоритета [math]\displaystyle{ p(v_i) }[/math], которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:

• First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
• Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
• Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
• Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
• Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
• и др.

Вычислительное ядро алгоритма

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

Макроструктура алгоритма

Псевдокод алгоритма:

Входные данные:
  граф с вершинами V, рёбрами E.
Выходные данные: цветовые метки с(v) для каждой вершины v ∈ V

color := []
w := []
for each v ∈ V:
     color[v] := 0
     w[v] := PRIORITY(v)

while v с color[v] == 0:
     S := ∅
     for each v с color[v] == 0 in parallel:
         isMax := true
         for each u ∈ N(v):
             if color[u] == 0 и ( w[u] > w[v] или (w[u] == w[v] и u.id > v.id) ):
                 isMax := false
                 break
         if isMax:
             S.append(v)

     for each v ∈ S in parallel:
         used := { color[u] : u ∈ N(v) и color[u] ≠ 0 }
         c := 1
         while c ∈ used:
             c := c + 1
         color[v] := c

Схема реализации последовательного алгоритма

Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа.

Последовательная сложность алгоритма

Для каждой вершины v алгоритм проделывает следующие шаги:

1. Просматривает её соседей.
2. Собирает цвета уже окрашенных соседей.
3. Выбирает минимальный свободный цвет.
4. Присваивает его v.

Инициализация начальных структур (расстановка приоритетов и цветов) требует один проход на [math]\displaystyle{ |V| }[/math] итераций, что даёт сложность [math]\displaystyle{ O(|V|) }[/math]. Для выбора доступного цвета необходимо просмотреть всех соседей вершины, что требует в сумме для всех вершин [math]\displaystyle{ \sum\limits_{v \in V} {deg(v)} = 2|E| }[/math] итераций, что даёт вклад [math]\displaystyle{ O(|E|) }[/math]. Выбор минимального свободного цвета требует, в простейшем случае, также [math]\displaystyle{ \sum\limits_{v \in V} {O(deg(v))} = O(|E|) }[/math] итераций, однако при эффективной реализации это можно делать за O(1) (например, при хранении доступных цветов в битовой карте).

Итого получаем суммарную сложность [math]\displaystyle{ O(|V| + |E|) }[/math]

Входные и выходные данные алгоритма

Входные данные: Граф [math]\displaystyle{ G = G(V, E) }[/math]
Объём входных данных: [math]\displaystyle{ 8|E| }[/math] если граф представлен списком связности, либо [math]\displaystyle{ |V|^2 }[/math], если матрицей смежности

Выходные данные: Вектор [math]\displaystyle{ c = \{c_i\} }[/math], содержащий итоговые цвета вершин.
Объём выходных данных: [math]\displaystyle{ |V| }[/math]

Свойства алгоритма

Жадные алгоритмы дают раскраски хорошего качества с точки зрения количества цветов (получаемые раскраски имеют не более, чем Δ + 1 цвет), однако эти раскраски не будут являться сбалансированными (количество цветов в цветовых классах будет распределено неравномерно)

Литература

Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020