Алговики - Вклад [ru]

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

2025-11-29T10:30:20Z

Lizord:

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

=== Схема реализации последовательного алгоритма ===
Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа. Описание её алгоритма можно получить, убрав параллельные секции из описания алгоритма Джонса-Плассмана (т.е исполняя их последовательно).

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png|center|800px|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]

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

Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.

Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

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

2025-11-29T10:23:19Z

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

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

=== Схема реализации последовательного алгоритма ===
Последовательной версией алгоритма Джонса-Плассмана является обычная жадная раскраска графа. Описание её алгоритма можно получить, убрав параллельные секции из описания алгоритма Джонса-Плассмана (т.е исполняя их последовательно).

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png|center|800px|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]

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

Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.

Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

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

2025-11-29T10:21:53Z

Lizord: /* Результаты прогонов */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png|center|800px|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]

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

Тесты проводились на синтетических графах с 8 миллионами вершинами и количеством ребёр равным 40, 60, 80, 100, 120, 140 и 160 миллионам.

Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

Файл:Результаты прогона алгоритма Джонса-Плассмана.png

2025-11-29T10:19:16Z

Lizord: Lizord загрузил новую версию Файл:Результаты прогона алгоритма Джонса-Плассмана.png

Результаты прогона алгоритма Джонса-Плассмана

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

2025-11-29T10:17:47Z

Lizord: /* Результаты прогонов */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
[[Файл:Результаты прогона алгоритма Джонса-Плассмана.png|center|800px|Рисунок 2. Результаты прогона алгоритма Джонса-Плассмана]]

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

Производительность в данном случае измеряется в GTEPS - миллиардах обработанных ребёр в секунду. Это классическая метрика производительности для задач на графах.

=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

Файл:Результаты прогона алгоритма Джонса-Плассмана.png

2025-11-29T10:12:14Z

Lizord:

Результаты прогона алгоритма Джонса-Плассмана

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

2025-11-23T13:58:18Z

Lizord: /* Ресурс параллелизма алгоритма */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Как видно из информационного графа, параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

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

2025-11-23T13:45:29Z

Lizord:

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />

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

2025-11-23T13:44:50Z

Lizord: Updated references

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math> <ref name="compl">Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020</ref>
| pf_width = <math>O(log(V))</math> <ref name="compl"></ref>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-11-23T13:38:11Z

Lizord: /* Выводы для классов архитектур */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

Несмотря на хорошую масштабируемость в рамках одного устройства (без необходимости обмениваться данными с другими процессами), алгоритм обладает слабой масштабируемостью на кластере ввиду роста расходов на коммуникацию между независимыми потоками (после каждой итерации каждый из потоков должен синхронизировать своё состояние с остальными). Для раскраски графов на распределенных системах следует использовать специализированные алгоритмы, основанные на разбиении графа <ref>Ian Bogle and George M. Slota, Parallel Graph Coloring Algorithms for Distributed GPU Environments</ref>.

== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-11-23T13:29:43Z

Lizord: /* Возможные способы и особенности параллельной реализации алгоритма */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-11-23T13:23:17Z

Lizord: /* Особенности реализации последовательного алгоритма */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

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

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

Эту же оптимизацию можно перенести и на ядра для параллельной реализации.

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-11-18T12:43:29Z

Lizord: /* Информационный граф */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
Далее представлен информационный граф '''одной итерации''' алгоритма. После её завершения, вершины, которые не были раскрашены прогоняются ещё раз - алгоритм работает, пока все вершины не будут раскрашены.

[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

=== Свойства алгоритма ===
Жадные алгоритмы дают раскраски хорошего качества с точки зрения количества цветов (получаемые раскраски имеют не более, чем Δ + 1 цвет), однако эти раскраски не будут являться сбалансированными (количество цветов в цветовых классах будет распределено неравномерно)
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-11-18T12:39:16Z

Lizord: /* Информационный граф */

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Основные авторы описания: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(|V| + |E|)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>|V|</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, предложен американскими исследователями Марком Джонсом и Паулем Плассманом в 1991 году. Алгоритм основан на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Способ выделения такого подмножества вершин был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref>

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

Для раскраски графа, необходимо проделать следующие шаги:
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>. 
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.
## Для каждой вершины <math>v_i \in V'</math> назначается уникальная случайная метка <math>p(v_i)</math>
## <math>v_i \in I \Leftrightarrow p(v_i) > p(w), \forall w \in adj(v_i) </math>
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>.

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

==== Функции приоритета ====
Существуют различные способы определять функцию приоритета <math>p(v_i)</math>, которая используется для выбора независимых вершин для раскраски. Помимо классического варианта с назначением случайных меток, вершины могут также выбираться следующими способами:
* First Fit: вершины рассматриваются в некотором заранее выбранном порядке. Например, в порядке появления в графе.
* Saturation-Degree-Ordering: выбирается вершина с максимальной насыщенной степенью, то есть с максимальным числом различно раскрашенных смежных вершин.
* Incidence-Degree-Ordering: выбирается вершина с максимальным числом раскрашенных смежных вершин.
* Largest-Degree-First: вершины раскрашиваются в порядке уменьшения степеней
* Smallest-Degree-Last: из графа удаляются все вершины с минимальной степенью, затем рекурсивно раскрашивается оставшийся граф. Удаленные вершины раскрашиваются в последнюю очередь.
* и др.

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

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

<source>
Входные данные:
граф с вершинами 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
</source>

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

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

Для каждой вершины v алгоритм проделывает следующие шаги:
# Просматривает её соседей.
# Собирает цвета уже окрашенных соседей.
# Выбирает минимальный свободный цвет.
# Присваивает его v.

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

Итого получаем суммарную сложность <math>O(|V| + |E|)</math>

=== Информационный граф ===
[[Файл:Информационный граф итерации алгоритма Джонса Плассмана.png|center|thumb|500px|Рисунок 1. Информационный граф одной итерации алгоритма Джонса-Плассмана]]

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

=== Ресурс параллелизма алгоритма ===
Параллелизм достигается за счёт выделения из множества вершин независимых подмножеств, между которыми нет ребёр. Очевидно, что вершинам из таких подмножеств можно назначить цвет независимо, т.е параллельно.

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

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

=== Свойства алгоритма ===
Жадные алгоритмы дают раскраски хорошего качества с точки зрения количества цветов (получаемые раскраски имеют не более, чем Δ + 1 цвет), однако эти раскраски не будут являться сбалансированными (количество цветов в цветовых классах будет распределено неравномерно)
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
<references />
Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

Файл:Информационный граф итерации алгоритма Джонса Плассмана.png

2025-11-18T12:35:30Z

Lizord:

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

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

2025-11-18T12:05:47Z

Lizord: /* Ресурс параллелизма алгоритма */

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

2025-11-18T12:00:37Z

Lizord: Исправлена ошибка в размере выходных данных

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

2025-11-18T11:59:37Z

Lizord: Исправлена ошибка в последовательной сложности

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

2025-11-18T11:58:50Z

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

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

2025-11-18T11:42:21Z

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

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

2025-11-18T11:38:48Z

Lizord: /* Макроструктура алгоритма */

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

2025-10-22T08:44:24Z

Lizord: /* Общее описание алгоритма */

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

2025-10-22T08:40:34Z

Lizord: Улучшен раздел 1.1

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

2025-10-22T08:36:11Z

Lizord: Добавлено описание различных функций приоритетов

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

2025-10-22T08:21:18Z

Lizord: Небольшие исправления

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

2025-10-22T07:29:32Z

Lizord: Различные исправления, добавлены свойства алгоритма

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

2025-10-16T13:29:48Z

Lizord: Удалён лишний тег

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

2025-10-16T13:29:19Z

Lizord: /* Входные и выходные данные алгоритма */

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

2025-10-16T13:25:02Z

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

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

2025-10-16T13:23:12Z

Lizord: Исправлено описание алгоритма

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

2025-10-16T12:26:27Z

Lizord: Поправлена опечатка

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

2025-10-16T12:25:42Z

Lizord: /* Математическое описание алгоритма */

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

2025-10-16T11:39:55Z

Lizord: Добавлено общее описание алгоритма

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

2025-10-16T11:26:26Z

Lizord: Корректные сноски на литературу

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

2025-10-16T11:14:17Z

Lizord: Исправлен объем входных данных

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Автор: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(V + E)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>8|E|</math>
| output_data = <math>V</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
# M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
# Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-10-16T11:09:40Z

Lizord: Добавлена информация о сложности алгоритма

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Автор: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(V + E)</math>
| pf_height = <math>O(\frac{log(V)}{log log(V)})</math>
| pf_width = <math>O(log(V))</math>
| input_data = <math>V + E</math>
| output_data = <math>V</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==
# M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
# Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020

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

2025-10-15T13:28:03Z

Lizord: Stub

{{in use|[[Участник:Lizord|Lizord]] ([[Обсуждение участника:Lizord|обсуждение]])}}

Автор: [[Участник:Lizord|Демаков М. А.]]

{{algorithm
| name = Алгоритм Джонса-Плассмана
| serial_complexity = <math>O(n^3)</math>
| pf_height = <math>O(n)</math>
| pf_width = <math>O(n^2)</math>
| input_data = <math>V + E</math>
| output_data = <math>V</math>
}}

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Результаты прогонов ===
=== Выводы для классов архитектур ===
== Литература ==

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

2025-10-15T13:22:46Z

Lizord: Stub