Участник:Full/Поиск автоморфизмов графов

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

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

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

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

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

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

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

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

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

$\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}$

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

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

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

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

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

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

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

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

$\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}$

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

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

Описание построения $M'_n$.

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

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

$\{M'_k\}$: $M'_1 \subseteq M'_2 \subseteq \ldots \subseteq M'_n$.

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

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

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

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

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

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

$\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}$

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

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

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

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 Последовательная сложность алгоритма

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

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

$|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}}$

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

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

$\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)$

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

$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))$

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

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

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

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

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

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

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

• $n$ ярусов сравнений (количество сравнений $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)$)

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

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

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

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

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

Объём входных данных: $n^2$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) приложение с графическим интерфейсом, написанное на Qt

• не поддерживает распараллеливание
• справляется с графами размера до 500 вершин
• удобный анализ графов
• помимо нахождения автоморфизмов, решает задачи изоморфизма и гомоморфизма графов

2) программа на языки C++ с поддержкой OpenMPI

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