Постановка задачи

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

Дан граф G = (V,E) , где V – множество вершин, E – множество ребер.

Чёрная дыра в графе G – слабо связный подграф (т.е. просто связный подграф, если не учитывать направление рёбер) B , состоящий из более чем одной вершины, такой что \forall \; v \in B \; \forall \; e(v, u) \in E: u \in B. Иными словами, чёрная дыра – это слабо связный подграф, состоящий хотя бы из двух вершин, в вершины которого могут идти ребра из остальных вершин графа, но не наоборот. Количество вершин в чёрной дыре будем называть размером чёрной дыры. Требуется найти как можно больше чёрных дыр заданного размера в графе G за фиксированное время (1 минута).

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

Пример черной дыры

На рисунке показан пример чёрной дыры размера 2 в графе.

Правила

  • Язык C/C++ и технологии MPI и OpenMP.
  • Можно использовать любой алгоритм.
  • Рейтинг участника определяется суммарным количеством найденных черных дыр на всех тестах.
  • Тест – граф и размер черных дыр, которые необходимо найти (размер не более 20 во всех тестах).
  • Тесты фиксированные и одинаковые для всех участников. Тестовые графы разных размеров, от нескольких сотен до миллиардов ребер.
  • В примере реализации на C++ реализовано решение задачи (полный перебор). Немного улучшив пример реализации, даже неопытные участники могут легко попасть в таблицу результатов.
  • Решение должно располагаться в файле solution_mpi.cpp. Функция run принимает необходимые данные: граф и размер черных дыр, которые необходимо найти, а также имя файла, в который необходимо записать ответ. В файле reference_mpi.cpp можно увидеть пример решения задачи.

Требования к результату работы реализации участника:

  • Ответ необходимо выводить в файл с именем outFilename – параметр функции run.
  • Выводить нужно информацию о найденных черных дырах: через пробел номера вершин, входящих в первую найденную черную дыру, далее, через пробел, номера вершин, входящих во вторую найденную черную дыру и т.д.
  • Одна и та же черная дыра может быть выведена более одного раза, при проверке повторы учитываться не будут.
  • Программа не должна выводить ничего, кроме информации о найденных черных дырах.
  • Информация о каждой найденной черной дыре, кроме последней (вывод последней черной дыры может оказаться неполным, если задача будет снята принудительно), должна быть правильной. В противном случае решение не будет принято.

Вычислительная система для реализации задачи: 36-узловой кластер "Ангара-К1", узлы которого объединены сетью Ангара с топологией 3D-тор.

Положение в таблице результатов

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

Проведение конкурса

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

  • В общей онлайн-таблице отображается лучшее решение каждого из участников.
  • Количество отправок в день ограничено для каждого участника.

Заморозка таблицы

За несколько дней до окончания конкурса таблица замораживается, в ней остаются видны только лучшие результаты участников на момент заморозки. Решения участников, отправленные после заморозки таблицы, будут видны только автору решения. Дата заморозки таблицы объявляется за несколько дней до заморозки. Итоговые результаты конкурса объявляются на закрытии конференции Russian Supercomputing Days 2018.

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

Пример реализации на С++ включает в себя простое решение задачи, а также необходимую инфраструктуру для генерации графов и проверки решения. Можно скачать здесь:

Вопросы

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

Литература

  1. Detecting Blackholes and Volcanoes in Directed Networks. 2010. PDF.