Алгоритм Ульмана: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показано 12 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| + | {{level-a}} | ||
| + | |||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 7: | Строка 9: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | Пусть задан ориентированный граф <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>. | ||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| + | Определим булеву матрицу <math>B= ( B_{i,j} )</math> размера следующим образом: | ||
| + | |||
| + | • <math>B_{i,j}</math> истинно, если не исключена возможность того, что <math>\varphi(v_i )=w_j</math>; | ||
| + | |||
| + | • <math>B_{i,j}</math> ложно в противном случае. | ||
| + | |||
| + | Алгоритм Ульмана состоит в последовательном уточнении матрицы до тех пор, пока такое уточнение возможно. После остановки алгоритма матрица либо целиком состоит из нулей, либо содержит информацию обо всех возможных изоморфных подграфах. | ||
| + | |||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| + | 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>. | ||
| + | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | |||
| + | |||
| + | • полиномиальная, для фиксированного графа <math>H</math> | ||
| + | |||
| + | • линейная, для фиксированного графа <math>H</math> и планарного графа <math>G</math>. | ||
| + | |||
=== Информационный граф === | === Информационный граф === | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| + | |||
| + | Перебор может быть эффективно параллелизован <ref>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 </ref>, в том числе с использованием графических ускорителей<ref>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</ref>. Известны реализации, работающие напрямую с графовыми базами данных<ref>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</ref> <ref> 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</ref>. | ||
| + | |||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
| Строка 18: | Строка 60: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| − | + | Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы | |
| − | + | ||
| − | + | === Результаты прогонов === | |
| − | === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
| Строка 38: | Строка 71: | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Ullman's algorithm]] | ||
Текущая версия на 12:14, 6 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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 Возможные способы и особенности параллельной реализации алгоритма
Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
- ↑ 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.
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
