boman_et_al_graph_coloringфункции окрашивают вершины ненаправленного, распределенного графа таким образом, что никакие две соседние вершины не имеют одинакового цвета. Все вершины данного цвета образуют независимый набор в графе. Графическая окраска использовалась для решения различных задач, включая распределение регистров в компиляторах, задачи оптимизации и задачи планирования.
Проблема окрашивания графика с наименьшим количеством цветов является NP-полной, поэтому многие алгоритмы (в том числе реализованный здесь) являются эвристическими алгоритмами, которые пытаются минимизировать количество цветов, но не гарантируют оптимальное решение. Этот алгоритм[BBC05]является аналогомsequential_vertex_coloringалгоритм, который повторяется через вершины один раз и выбирает цвет с наименьшим числом, который может иметь текущая вершина. Поэтому окраска и количество цветов связаны с упорядочением вершин в последовательном случае.
Распределенныйboman_et_al_graph_coloringалгоритм будет производить различные окраски в зависимости от порядка и распределения вершин и количества параллельных процессов, сотрудничающих для выполнения окраски.
Алгоритм возвращает количество цветовnum_colors, используемых для окрашивания графика.
Stores the color of each vertex, which will be a value in the range
[0, num_colors). The type ColorMap must model the
Read/Write Property Map concept and must be a distributed
property map.
IN: vertices_size_types
The number of vertices to color within each superstep. After
s vertices have been colored, the colors of boundary vertices
will be sent to their out-of-process neighbors. Smaller values
communicate more often but may reduce the risk of conflicts,
whereas larger values do more work in between communication steps
but may create many conflicts.
Default: 100
IN: ChooseColorchoose_color
A function object that chooses the color for a vertex given the
colors of its neighbors. The function object will be passed a vector
of values (marked) and a marked_true value, and should
return a color value such that color>=marked.size() or
marked[color]!=marked_true.
Default:
boost::graph::distributed::first_fit_color<color_type>(), where
color_type is the value type of the ColorMap property map.
IN: VertexOrderingordering
A binary predicate function object that provides total ordering on
the vertices in the graph. Whenever a conflict arises, only one of
the processes involved will recolor the vertex in the next round,
and this ordering determines which vertex should be considered
conflicting (its owning process will then handle the
conflict). Ideally, this predicate should order vertices so that
conflicting vertices will be spread uniformly across
processes. However, this predicate must resolve the same way on
both processors.
Default: unspecified
IN: VertexIndexMapindex
A mapping from vertex descriptors to indices in the range [0,
num_vertices(g)). This must be a Readable Property Map whose
key type is a vertex descriptor and whose value type is an integral
type, typically the vertices_size_type of the graph.
Сложность этого алгоритма трудно охарактеризовать, поскольку она сильно зависит от количестваконфликтов, которые происходят во время алгоритма. Конфликт возникает, когдапограничной вершине(т.е. вершине, которая примыкает к вершине, хранящейся на другом процессоре) дается один и тот же цвет, является пограничной вершиной, смежной с ней (но на другом процессоре). Противоречивым вершинам должны быть присвоены новые цвета, требующие дополнительной работы и общения. Работа, связанная с переназначением цвета для конфликтующей вершины, являетсяO(d), гдеd- степень вершины иO(1)сообщенияO(1)размера необходимы для разрешения конфликта. Заметим, что число конфликтов увеличивается с (1) количеством процессов и (2) количеством межпроцессных краев.
Выполнение этой реализации алгоритма окраски графов Bomen et al. иллюстрируется следующими диаграммами. Масштабирование и производительность являются разумными для всех графиков, которые мы пробовали.
Copyright (C) 2005 Попечители Университета Индианы.
Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw H. Gebremedhin и Fredrik Manne. Алгоритм масштабируемого параллельного графического окрашивания для компьютеров с распределенной памятью. [принт]
Статья Parallel BGL Boman et al graph coloring раздела может быть полезна для разработчиков на c++ и boost.
