Алгоритм Ульмана

Материал из Алговики
Перейти к навигации Перейти к поиску

Содержание

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

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

Алгоритм Ульмана[1][2] решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом

  • для фиксированного графа [math]H[/math] время полиномиальное;
  • для планарного графа [math]G[/math] время работы линейное (при фиксированном графе [math]H[/math]).

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

Пусть задан ориентированный граф [math]G=(V,E)[/math] с вершинами [math]V= ( v_1,v_2,...,v_n)[/math] и рёбрами [math]E=(e_1,e_2,...,e_m)[/math] , и ориентированный граф [math]H=(W,F)[/math] с вершинами [math]W=(w_1,w_2,...,w_n)[/math] и рёбрами [math]F=(f_1,f_2,...,f_m)[/math]. Булевы функции [math]p(v_i,w_j )[/math] и [math]q(e_i,f_j )[/math] задают совместимость вершин и рёбер двух графов (например, что вершины помечены одним и тем же химическим элементом).

Подграф [math]G'=(V',E' )[/math] графа [math]G[/math] изоморфен графу [math]H[/math], если существует взаимно-однозначное отображение [math]\varphi:V' \rightarrow W[/math], удовлетворяющее условиям:

1. [math]p(v, \varphi(v))[/math] истинно для всех вершин [math]v \in V'[/math].

2. Если вершины [math]v_1,v_2 \in V'[/math] и [math]e=(v_1,v_2 ) \in E[/math], то [math]e \in E' [/math] и существует соответствующее ребро [math]f=( \varphi (v_1 ), \varphi (v_2 )) \in F[/math].

3. [math]q(e,f)[/math] истинно.

Задача поиска изоморфных подграфов состоит в отыскании подграфов графа [math]G[/math], изоморфных графу-шаблону [math]H[/math].

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

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

Определим булеву матрицу [math]B= ( B_{i,j} )[/math] размера следующим образом:

[math]B_{i,j}[/math] истинно, если не исключена возможность того, что [math]\varphi(v_i )=w_j[/math];

[math]B_{i,j}[/math] ложно в противном случае.

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

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

1. Этап инициализации.

a. [math]B_(i,j):=p(v_i,w_j )[/math].

b. [math]B_(i,j):=0[/math], если степень вершины [math]v_i[/math] меньше степени вершины [math]w_j[/math] (таким образом, вершина [math]v_i[/math] заведомо не может соответствовать вершине [math]w_j[/math]).

c. [math]B_(i,j):=0[/math], если есть другие основания полагать, что вершина [math]v_i[/math] не может соответствовать вершине [math]w_j[/math] (например, с учётом функции [math]q[/math]).

2. Основной шаг. Пусть [math]B_(i,j):=1[/math]. Выполним поиск от вершины [math]v_i[/math], принимая во внимание текущее состояние матрицы [math]B[/math] и функцию [math]q[/math]. В результате либо будет найден изоморфный подграф, либо будет доказано, что вершина [math]v_i[/math] не может соответствовать вершине [math]w_j[/math]. В последнем случае производится присваивание [math]B_(i,j):=0[/math].

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

• полиномиальная, для фиксированного графа [math]H[/math]

• линейная, для фиксированного графа [math]H[/math] и планарного графа [math]G[/math].

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

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

Перебор может быть эффективно параллелизован [3], в том числе с использованием графических ускорителей[4]. Известны реализации, работающие напрямую с графовыми базами данных[5] [6].

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

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

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

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

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

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

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

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

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

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

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

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

3 Литература

  1. Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
  2. Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.
  3. Abu-Khzam, F. N., Daudjee, K., Mouawad, A. E., & Nishimura, N. (2015). On scalable parallel recursive backtracking. Journal of Parallel and Distributed Computing. http://doi.org/10.1016/j.jpdc.2015.07.006
  4. Wang, R., Guo, L., Ai, C., Li, J., Ren, M., & Li, K. (2015). An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU. EUC IEEE International Conference on High Performance Computing and Communications (HPCC) & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 7(5), 1089–1096. http://doi.org/10.1109/HPCC.and.EUC.2013.154
  5. Teixeira, C. H. C., Fonseca, A. J., Serafini, M., Siganos, G., Zaki, M. J., & Aboulnaga, A. (2015). Arabesque: a system for distributed graph mining (pp. 425–440). Presented at the SOSP Symposium, New York, New York, USA: ACM Press. http://doi.org/10.1145/2815400.2815410
  6. Raman, R., van Rest, O., Hong, S., Wu, Z., Chafi, H., & Banerjee, J. (2014). PGX.ISO: Parallel and Efficient In-Memory Engine for Subgraph Isomorphism (pp. 1–6). Presented at the GRADES Workshop, New York, New York, USA: ACM Press. http://doi.org/10.1145/2621934.2621939