Участник:Full/Поиск автоморфизмов графов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 38 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Алгоритм: Поиск автоморфизмов графов<br>
 
Алгоритм: Поиск автоморфизмов графов<br>
−
Автор статьи: Ефремов С.С. группа 419
+
Автор статьи: Ефремов С.С. (группа 419)
  
 
= Свойства и структура алгоритмов =
 
= Свойства и структура алгоритмов =
Строка 70: Строка 70:
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
 +
Вычислительным ядром алгоритма является последовательность множеств  <math>M'_1 \ldots M'_n</math>. Вычисляется на основе соответствующих <math>M_1 \ldots M_n</math>. Построение <math>M_1 \ldots M_n</math> занимает несущественную часть времени.
 +
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
 +
Каждое множество <math> M_i (i = 2 \ldots n) </math> вычисляется из <math> M'_{i-1} </math> путем добавления в каждый элемент (частичная перестановка, представленная вектором целых чисел) из <math> M'_{i-1} </math> всех возможных оставшихся чисел, которых нет в соответствующем элементе.
 +
 +
Для этого удобно использовать 2 не фиксированных по количеству строк двумерных массива размера t на n (t может увеличиваться), хранящих частичные отображения, такого вида:
 +
 +
:<math>
 +
\begin{pmatrix}
 +
a_{11} & a_{12} & \ldots &a_{1i} & ? & \ldots & ? \cr
 +
a_{21} & a_{22} & \ldots &a_{2i} & ? & \ldots & ? \cr
 +
\ldots \cr
 +
a_{k1} & a_{k2} & \ldots &a_{ki} & ? & \ldots & ? \cr
 +
?      & ?      & \ldots &  ?  & ? & \ldots & ? \cr
 +
\ldots \cr
 +
?      & ?      & \ldots &  ?  & ? & \ldots & ? \cr
 +
\end{pmatrix}
 +
</math>
 +
 +
? - эти значения не известны и заполняются постепенно.
 +
 +
Один массив для <math> M'_{i-1} </math>, другой для вычисления из предыдущего <math> M_i </math>.
 +
Из каждой строки множества <math> M'_{i-1} </math> (первый массив), в соответствие с алгоритмом, получается <math> n </math> новых строк длины i, которые записываются во второй массив (расширяется, если нужно).
 +
 +
После этого, второй массив копируется в первый и запускается цикл по всем векторам. Вектор исключается из массива, если <math> a_{ji} </math> равен какому-либо числу в данном векторе или вектор с <math> a_{ji} </math> является частичной перестановкой, не удовлетворяющей критерию;
 +
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
 +
 +
Схема реализации представлена на языке C++
 +
 +
<source lang=c>
 +
#define GRAPH_SIZE 300
 +
#define ROW_ARR_SIZE 10000
 +
#define COL_ARR_SIZE GRAPH_SIZE
 +
 +
const int N = GRAPH_SIZE;
 +
 +
vector<array<unsigned short,COL_ARR_SIZE>> Mi(ROW_ARR_SIZE, COL_ARR_SIZE);
 +
vector<array<unsigned short,COL_ARR_SIZE>> M'i(ROW_ARR_SIZE, COL_ARR_SIZE);
 +
unsigned char **matrix;
 +
 +
struct_M'i make_M'i(Mi) {
 +
    struct_M'i M'i;
 +
    for (auto x: Mi) {
 +
        for (int i = 0; i < n; ++i) {
 +
            if (check_h(x) && !eq(x, i)) {
 +
                M'i.push_back(x.add(i));
 +
            }
 +
        }
 +
    }
 +
    return M'i;
 +
}
 +
 +
struct_Mi make_Mi(M'i) {
 +
    struct_Mi Mi;
 +
    for (auto x: M'i) {
 +
        for (int i = 0; i < n; ++i) {
 +
          Mi.push_back(x.add(i));
 +
        }
 +
    }
 +
    return Mi;
 +
}
 +
 +
int main() {
 +
 +
    //заполнение матрицы смежности
 +
    init_automorphisms(matrix);
 +
 +
    //распараллеливание
 +
    switch(process) {
 +
    case 0:
 +
        begin = 0;
 +
        end = stop_0;
 +
    case 1:
 +
        begin = start_1;
 +
        end = stop_1;
 +
    ...
 +
    case N:
 +
        begin = start_n;
 +
        end = M_0.size();
 +
 +
    //основной цикл
 +
    for (i = begin; i < end; ++i) {
 +
        Mi = make_Mi(M'i-1);
 +
        M'i = make_M'i(Mi);
 +
    }
 +
 +
    //сохранение результата (вывод автоморфизмов)
 +
    final_automorphism(M'i);
 +
}
 +
</source>
 +
 
== Последовательная сложность алгоритма ==
 
== Последовательная сложность алгоритма ==
 +
Сложность всего алгоритма представляет собой сумму сложностей вычисления <math>M'_1 \ldots M'_n</math>.
 +
 +
Количество элементов в каждом множестве (с вероятностью близкой к единице):
 +
 +
<math> |M'_{k}| \thickapprox \frac{n!}{(n-k-2)!~2^{(k)^2}} \thickapprox \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} </math>
 +
 +
Можно оценить: <math> |M'_k| = \frac{n(n-1)\ldots(n-k-1)}{2^{(k)^2}} \le \frac{n^{k}}{2^{(k)^2}} </math>
 +
 +
Количество операций сравнения для подсчета всех множеств:
 +
 +
<math> \sum_{k = 1}^{n} \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1)</math>
 +
 +
Оценка (были учтены точка стабилизации и точка максимума последовательности множеств):
 +
 +
<math> n \times \frac{n^{(5/7) \ln(n)}}{2^{((5/7)\ln(n))^2}}\times n(2(\frac{5}{7}\ln(n)) + 1)\times \log_2(n) = O(n^2(\frac{e}{2})^{\ln(n)^2} \ln(n))</math>
 +
 +
Сложность экспоненциальная.
 +
 
== Информационный граф ==
 
== Информационный граф ==
 +
[[глоссарий#Граф алгоритма|Граф алгоритма]]<ref>Воеводин В.В.  Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref> для <math>n = 4</math> (при росте <math>n</math> изменения графа будут аналогичны, а отклонения не существенны:
 +
 +
 +
 +
[[file:Граф_автоморфизмов.png|thumb|center|1100px|Рисунок 1. Граф алгоритма. CHECK - проверка по критерию.]]
 +
 +
 +
 +
При больших <math>n</math> ширина ярусов будет расти до яруса под номером <math>\lceil\frac{5}{7}\log_2(n) - 1\rceil</math>, после начнет убывать.
 +
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
 +
 +
Для поиска автоморфизмов матрицы порядка <math>n</math> итерационным алгоритмом в параллельном варианте требуется выполнить:
 +
 +
* <math>n</math> ярусов сравнений (количество сравнений <math> k = 1 \ldots n: \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1) </math>)
 +
 +
При классификации по высоте ЯПФ, таким образом, алгоритм имеет сложность <math> O(n) </math>.
 +
 +
При классификации по ширине ЯПФ его сложность <math> O(n(\frac{e}{2})^{\ln(n)^2} \ln(n))) </math>.
 +
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
 +
 +
'''Входные данные''': матрица смежности <math>A</math> (элементы <math>a_{ij}</math>) графа .
 +
Дополнительные ограничения:
 +
* <math>a_{ij}</math> – любые, но в данной статье рассматриваются из множества {0,1}.
 +
 +
'''Объём входных данных''': <math>n^2</math>.
 +
 +
'''Выходные данные''': множество <math>M'_n</math>, представленное матрицей (элементы <math>g^s_n</math> - полученные автоморфизмы).
 +
 +
'''Объём выходных данных''': <math>l \times n</math>, где <math>l</math> количество всевозможных автоморфизмов для данного графа.
 +
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
 
= Программная реализация алгоритма =
 
= Программная реализация алгоритма =
 
== Особенности реализации последовательного алгоритма ==
 
== Особенности реализации последовательного алгоритма ==
 
== Локальность данных и вычислений ==
 
== Локальность данных и вычислений ==
 +
== Возможные способы и особенности параллельной реализации алгоритма ==
 
== Масштабируемость алгоритма и его реализации ==
 
== Масштабируемость алгоритма и его реализации ==
 +
==== Масштабируемость реализации алгоритма ====
 +
Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
 +
 +
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
 +
 +
* число процессоров [4 : 128] с шагом <math> 2^n</math> (точки отображены с шагом 4, усреднив результаты);
 +
* размер матрицы [300 : 1000].
 +
 +
В результате проведённых экспериментов был получен следующий диапазон алгоритма:
 +
 +
* минимальная эффективность реализации 17,44%;
 +
* максимальная эффективность реализации 88,73%.
 +
 +
На следующих рисунках приведены графики производительности и эффективности выбранной реализации поиска автоморфизмов графов в зависимости от изменяемых параметров запуска.
 +
 +
[[file:График_производительности_поиска_автоморфизмов.jpg|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
 +
[[file:График_эффективности.jpg|thumb|center|700px|Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]
 +
 +
Оценки масштабируемости выбранной реализации:
 +
* По числу процессов: -0,00837.
 +
* По размеру задачи: 0,04612.
 +
* По двум направлениям: 0,00253.
 +
 
== Динамические характеристики и эффективность реализации алгоритма ==
 
== Динамические характеристики и эффективность реализации алгоритма ==
 
== Выводы для классов архитектур ==
 
== Выводы для классов архитектур ==
 
== Существующие реализации алгоритма ==
 
== Существующие реализации алгоритма ==
 +
 +
Информация о реализациях данного алгоритма не найдена. При анализе алгоритма было разработано 2 программы: <br/>
 +
 +
:1) приложение с графическим интерфейсом, написанное на '''Qt'''
 +
:::* не поддерживает распараллеливание
 +
:::* справляется с графами размера до 500 вершин
 +
:::* удобный анализ графов
 +
:::* помимо нахождения автоморфизмов, решает задачи изоморфизма и гомоморфизма графов
 +
:2) программа на языки '''C++''' с поддержкой '''OpenMPI'''
 +
:::* поддерживает распараллеливание средствами OpenMPI
 +
:::* помимо нахождения автоморфизмов, сохраняет много информации для анализа графов с большим количеством вершин
 +
 
= Литература =
 
= Литература =
 
<references />
 
<references />
  
 
[[en:Description of algorithm properties and structure]]
 
[[en:Description of algorithm properties and structure]]

Текущая версия на 21:10, 12 декабря 2017

Алгоритм: Поиск автоморфизмов графов
Автор статьи: Ефремов С.С. (группа 419)

Содержание

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

Данный алгоритм, описанный в статье Егорова В.Н.[1], предназначен для поиска автоморфизмов графов, которые можно представить в виде матриц смежности, а также для исследования изоморфности графов. Так как алгоритм работает с матрицами, можно решать эти же задачи и на других комбинаторных объектах, представимых матрицами смежности[2].

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

На вход подается матрица смежности графа. При отображение вершины v1 в вершину v2 в соответсвующей графу матрице меняются местами строка и столбец v1 со строкой и столбцом v2. Автоморфизмом является отображение множества вершин графа на себя, сохраняющее смежность. Это есть такая перестановка строк и столбцов матрицы, после применения которой, матрица останется той же.

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

1.2.1 Определения и обозначения

[math]A = A^{n\times n}[/math] - матрица смежности графа [math]G(V,E)[/math] размера [math]n\times n[/math]; [math]a_{ij}[/math] - элементы матрицы ,[math]\ i,j = 1,\ldots,n=|V|[/math].

Частичным отображением [math]g^s_k[/math] ([math]s[/math] - обозначает индекс элемента в множестве [math]M_k[/math]) называется подстановка вида

[math] \begin{pmatrix} 1 & 2 & \ldots & k & k+1 &\ldots & n\cr r_1 & r_2 & \ldots & r_k & q_{k+1} & \ldots & q_n \end{pmatrix} [/math]

, где [math]r_1,\ldots,r_k[/math] - фиксированные (заданные) элементы, [math]q_{k+1},\ldots,q_n[/math] - произвольные, причем последовательность [math]r_1,\ldots,r_k[/math], [math]q_{k+1},\ldots,q_n[/math] является перестановкой вершин заданного графа.

[math]M_k[/math] - множество, состоящее из элементов [math]g^s_k[/math], [math]\ s = 1,\ldots,n_k=|M_k|[/math].

[math]|M_k|[/math] - количество элементов [math]g^s_k[/math] в множестве.

[math]M'_k[/math] - множество элементов, которые содержатся в [math]M_k[/math] и удовлетворяют критерию [math]h[/math].

h - критерий (описанный далее).

[math]\{M'_k\}[/math] - последовательность множеств [math]M'_k[/math], [math]k = 1,\ldots,n[/math].


1.2.2 Проверка по критерию

Критерием [math]h[/math] является проверка подматриц на равенство. Предположим, требуется определить, удовлетворяет ли элемент [math]g^s_k[/math] критерию h. Для этого необходимо, чтобы элементы [math]a_{ij}[/math], для всех [math]i,j \leq k[/math], были равны соответствующим элементам [math]a_{r_ir_j}[/math]. Подматрица [math]g^s_k[/math] выглядит так:

[math] \begin{matrix} & r_1 & r_2 & \dots & r_k \cr r_1 & a_{r_1r_1} & a_{r_1r_2} & \dots & a_{r_1r_k} \cr r_2 & a_{r_2r_1} & a'_{r_2r_2} & \dots & a_{r_2r_k} \cr \vdots & \vdots & \vdots & \ddots & \vdots \cr r_k & a_{r_kr_1} & a_{r_kr_2} & \dots & a_{r_kr_k} \cr \end{matrix} [/math]

Если хотя бы одно из равенств не выполнено, это означает, что по данной частичной подстановке хотя бы одна вершина отобразилась в другую так, что структура графа изменилась. А так как частичная перестановка [math]g^s_k[/math] фиксирует [math]r_1, \ldots r_k[/math], то структура останется измененой, что означает отображение не будет являться автоморфизмом.


1.2.3 Построение множеств частичных отображений

Описание построения [math]M'_n[/math].

На первом этапе рассматриваются все [math]g^s_1[/math], образующие множество [math]M_1[/math]. Каждый элемент [math]g^s_1[/math] проверяется по критерию h. Элементы, удовлетворяющие h, образуют [math]M'_1[/math]. В каждый элемент из [math]M'_1[/math] добавляется еще одно отображение (2 [math]\to[/math] [math]r_2[/math]), т.е. происходит переход от [math]g^s_1[/math] к [math]g^s_2[/math]. Из каждого [math]g^s_1[/math] получается разных [math](n-1)[/math] элементов [math]g^s_2[/math]. Всевозможные элементы [math]g^s_2[/math] образуют [math]M_2[/math]. Далее строится [math]M'_2[/math], добавляя в него только те элементы из [math]M_2[/math], которые удовлетворяют критерию. Аналогично получаются множества [math]M_3,\ M'_3,\ M_4,\ldots, M_n,\ M'_n[/math].


Таким образом, получается последовательнось множеств частичных отображенией:

[math]\{M'_k\}[/math]: [math]M'_1 \subseteq M'_2 \subseteq \ldots \subseteq M'_n[/math].

Множество [math]M'_n[/math] является множеством всех возможных автоморфизмов (или пустое, если их нет).

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

Вычислительным ядром алгоритма является последовательность множеств [math]M'_1 \ldots M'_n[/math]. Вычисляется на основе соответствующих [math]M_1 \ldots M_n[/math]. Построение [math]M_1 \ldots M_n[/math] занимает несущественную часть времени.

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

Каждое множество [math] M_i (i = 2 \ldots n) [/math] вычисляется из [math] M'_{i-1} [/math] путем добавления в каждый элемент (частичная перестановка, представленная вектором целых чисел) из [math] M'_{i-1} [/math] всех возможных оставшихся чисел, которых нет в соответствующем элементе.

Для этого удобно использовать 2 не фиксированных по количеству строк двумерных массива размера t на n (t может увеличиваться), хранящих частичные отображения, такого вида:

[math] \begin{pmatrix} a_{11} & a_{12} & \ldots &a_{1i} & ? & \ldots & ? \cr a_{21} & a_{22} & \ldots &a_{2i} & ? & \ldots & ? \cr \ldots \cr a_{k1} & a_{k2} & \ldots &a_{ki} & ? & \ldots & ? \cr ? & ? & \ldots & ? & ? & \ldots & ? \cr \ldots \cr ? & ? & \ldots & ? & ? & \ldots & ? \cr \end{pmatrix} [/math]

? - эти значения не известны и заполняются постепенно.

Один массив для [math] M'_{i-1} [/math], другой для вычисления из предыдущего [math] M_i [/math]. Из каждой строки множества [math] M'_{i-1} [/math] (первый массив), в соответствие с алгоритмом, получается [math] n [/math] новых строк длины i, которые записываются во второй массив (расширяется, если нужно).

После этого, второй массив копируется в первый и запускается цикл по всем векторам. Вектор исключается из массива, если [math] a_{ji} [/math] равен какому-либо числу в данном векторе или вектор с [math] a_{ji} [/math] является частичной перестановкой, не удовлетворяющей критерию;

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

Схема реализации представлена на языке C++ 

#define GRAPH_SIZE 300
#define ROW_ARR_SIZE 10000 
#define COL_ARR_SIZE GRAPH_SIZE

const int N = GRAPH_SIZE;

vector<array<unsigned short,COL_ARR_SIZE>> Mi(ROW_ARR_SIZE, COL_ARR_SIZE);
vector<array<unsigned short,COL_ARR_SIZE>> M'i(ROW_ARR_SIZE, COL_ARR_SIZE);
unsigned char **matrix;

struct_M'i make_M'i(Mi) {
    struct_M'i M'i;
    for (auto x: Mi) {
        for (int i = 0; i < n; ++i) {
            if (check_h(x) && !eq(x, i)) {
                M'i.push_back(x.add(i));
            }
        }
    }
    return M'i;
}

struct_Mi make_Mi(M'i) {
    struct_Mi Mi;
    for (auto x: M'i) {
        for (int i = 0; i < n; ++i) {
           Mi.push_back(x.add(i));
        }
    }
    return Mi;
}

int main() {

    //заполнение матрицы смежности
    init_automorphisms(matrix);

    //распараллеливание
    switch(process) {
    case 0:
        begin = 0;
        end = stop_0;
    case 1:
        begin = start_1;
        end = stop_1;
    ...
    case N:
        begin = start_n;
        end = M_0.size();

    //основной цикл
    for (i = begin; i < end; ++i) {
        Mi = make_Mi(M'i-1);
        M'i = make_M'i(Mi);
    }

    //сохранение результата (вывод автоморфизмов)
    final_automorphism(M'i);
}

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

Сложность всего алгоритма представляет собой сумму сложностей вычисления [math]M'_1 \ldots M'_n[/math].

Количество элементов в каждом множестве (с вероятностью близкой к единице):

[math] |M'_{k}| \thickapprox \frac{n!}{(n-k-2)!~2^{(k)^2}} \thickapprox \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} [/math]

Можно оценить: [math] |M'_k| = \frac{n(n-1)\ldots(n-k-1)}{2^{(k)^2}} \le \frac{n^{k}}{2^{(k)^2}} [/math]

Количество операций сравнения для подсчета всех множеств:

[math] \sum_{k = 1}^{n} \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1)[/math]

Оценка (были учтены точка стабилизации и точка максимума последовательности множеств):

[math] n \times \frac{n^{(5/7) \ln(n)}}{2^{((5/7)\ln(n))^2}}\times n(2(\frac{5}{7}\ln(n)) + 1)\times \log_2(n) = O(n^2(\frac{e}{2})^{\ln(n)^2} \ln(n))[/math]

Сложность экспоненциальная.

1.7 Информационный граф

Граф алгоритма[3][4][5] для [math]n = 4[/math] (при росте [math]n[/math] изменения графа будут аналогичны, а отклонения не существенны:


Рисунок 1. Граф алгоритма. CHECK - проверка по критерию.


При больших [math]n[/math] ширина ярусов будет расти до яруса под номером [math]\lceil\frac{5}{7}\log_2(n) - 1\rceil[/math], после начнет убывать.

1.8 Ресурс параллелизма алгоритма

Для поиска автоморфизмов матрицы порядка [math]n[/math] итерационным алгоритмом в параллельном варианте требуется выполнить:

  • [math]n[/math] ярусов сравнений (количество сравнений [math] k = 1 \ldots n: \frac{1}{e^{k}} \frac{n^{n+1/2}}{(n-k-2)^{(n-k-3/2)}~2^{(k)^2}} \times (n - k)(2k + 1) [/math])

При классификации по высоте ЯПФ, таким образом, алгоритм имеет сложность [math] O(n) [/math].

При классификации по ширине ЯПФ его сложность [math] O(n(\frac{e}{2})^{\ln(n)^2} \ln(n))) [/math].

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

Входные данные: матрица смежности [math]A[/math] (элементы [math]a_{ij}[/math]) графа . Дополнительные ограничения:

  • [math]a_{ij}[/math] – любые, но в данной статье рассматриваются из множества {0,1}.

Объём входных данных: [math]n^2[/math].

Выходные данные: множество [math]M'_n[/math], представленное матрицей (элементы [math]g^s_n[/math] - полученные автоморфизмы).

Объём выходных данных: [math]l \times n[/math], где [math]l[/math] количество всевозможных автоморфизмов для данного графа.

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

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

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость реализации алгоритма

Исследование проводилось на суперкомпьютере "Ломоносов"[6] Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

  • число процессоров [4 : 128] с шагом [math] 2^n[/math] (точки отображены с шагом 4, усреднив результаты);
  • размер матрицы [300 : 1000].

В результате проведённых экспериментов был получен следующий диапазон алгоритма:

  • минимальная эффективность реализации 17,44%;
  • максимальная эффективность реализации 88,73%.

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

Рисунок 2. Параллельная реализация алгоритма поиска автоморфизмов. Изменение производительности в зависимости от числа процессоров и размера матрицы.
Рисунок 3. Параллельная реализация алгоритма поиска автоморфизмов. Изменение эффективности в зависимости от числа процессоров и размера матрицы.

Оценки масштабируемости выбранной реализации:

  • По числу процессов: -0,00837.
  • По размеру задачи: 0,04612.
  • По двум направлениям: 0,00253.

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.7 Существующие реализации алгоритма

Информация о реализациях данного алгоритма не найдена. При анализе алгоритма было разработано 2 программы:

1) приложение с графическим интерфейсом, написанное на Qt
  • не поддерживает распараллеливание
  • справляется с графами размера до 500 вершин
  • удобный анализ графов
  • помимо нахождения автоморфизмов, решает задачи изоморфизма и гомоморфизма графов
2) программа на языки C++ с поддержкой OpenMPI
  • поддерживает распараллеливание средствами OpenMPI
  • помимо нахождения автоморфизмов, сохраняет много информации для анализа графов с большим количеством вершин

3 Литература

  1. ↑ Группы автоморфизмов и изоморфизм комбинаторных объектов и алгебраических структур. Егоров В.Н., Егоров А.В. (Ломоносовские чтения, Научная конференция, Москва, факультет ВМК МГУ имени М.В.Ломоносова).
  2. ↑ О группах автоморфизмов матриц. Егоров В.Н. (журнал "Прикладная дискретная математика").
  3. ↑ Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.
  4. ↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.
  5. ↑ Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.
  6. ↑ Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Full/Поиск_автоморфизмов_графов&oldid=25087