Описание задачи

Предлагается задача Minimum Spanning Tree (MST) построения минимального остовного дерева в неориентированном графе с весами, значения которых являются действительными неотрицательными числами. Подробнее можно прочитать в книге Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание. — М.: «Вильямс», 2013. — 1328 с.

Для оценки производительности реализаций используются два вида синтетических графов: RMAT-графы и SSCA2-графы. R-MAT-графы хорошо моделируют реальные графы из социальных сетей, Интернета: R-MAT: A Recursive Model for Graph Mining (English paper, PDF). В конкурсе рассматриваются RMAT-графы со средней степенью связности вершины 32, количество вершин является степенью двойки. В таком RMAT-графе имеется одна большая связная компонента и некоторое количество небольших связных компонент или висящих вершин. SSCA2-граф представляет собой набор независимых компонент, соединенных ребрами друг с другом: Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors (English paper, разделы 2 и 3, PDF). Параметры SSCA2-графа для конкурса подобраны таким образом, что в графе создается большое количество разных по размеру связных компонент. Параллельный и последовательный генераторы графов встроены в пример реализации.

Участники конкурса могут самостоятельно выбирать размер графа, который будет использован для тестирования реализации. В таблице результатов конкурса отправки участников ранжируются по средней производительности, полученной на RMAT- и SSCA2- графах заданного размера.

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

Допустимые преобразования на этапе изменения внутреннего представления графа:

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

Нельзя выполнять содержательные вычисления на этапе изменения внутреннего представления, например:

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

Требования к результату работы алгоритма MST. Выходные данные должны содержать:

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

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

Для проверки правильности работы реализованных алгоритмов предусмотрена процедура валидации, состоящая из нескольких этапов. Вначале сравнивается общее число деревьев в реализации MST участника и примере реализации. Далее происходит сортировка всех деревьев по их весу. Затем каждое дерево рассматривается по очереди. Проверяется, совпадает ли вес рассматриваемого дерева с весом дерева из примера реализации. После этого выясняется, является ли рассматриваемое дерево действительно деревом. Для этого происходит проверка, что дерево — связный граф и содержит N вершин и N – 1 ребро. На последнем этапе валидации проверяется, покрывают ли рассматриваемые деревья все неизолированные вершины исходного графа.

Вычислительные системы

Предлагается две категории систем для реализации задачи:

  1. Один вычислительный узел.
  2. Многоузловой кластер.

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

Пример реализации

Версию 1.0 примера реализации алгоритма MST, а также необходимую инфраструктуру для последовательной (одноузловой) и распределенной генерации графов, проверки правильности работы алгоритмов можно скачать здесь: GraphHPC-1.0.tgz.

Вопросы

Если у Вас возникли какие-то вопросы, просьба писать по адресу contest@dislab.org.