Алгоритм Ульмана: различия между версиями

[непроверенная версия]

[досмотренная версия]

Текущая версия на 12:14, 6 июля 2022

Содержание

1 Свойства и структура алгоритма
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

[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

[1]

[2]

[3]

[4]

[5]

[6]

@@ Строка 1: / Строка 1: @@
-== Свойства и структура алгоритмов ==
+{{level-a}}
+== Свойства и структура алгоритма ==
 === Общее описание алгоритма ===
@@ Строка 6: / Строка 8: @@
 * для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).
-=== Математическое описание ===
+=== Математическое описание алгоритма ===
+Пусть задан ориентированный граф <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>, удовлетворяющее условиям:
+.	<math>p(v, \varphi(v))</math> истинно для всех вершин <math>v \in V'</math>.
+.	Если вершины <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>.
+.	 <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> ложно в противном случае.
+Алгоритм Ульмана состоит в последовательном уточнении матрицы  до тех пор, пока такое уточнение возможно. После остановки алгоритма матрица  либо целиком состоит из нулей, либо содержит информацию обо всех возможных изоморфных подграфах.
+=== Схема реализации последовательного алгоритма ===
+.	Этап инициализации.
+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>).
+.	Основной шаг. Пусть <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>.
-== Программная реализация алгоритмов ==
+=== Входные и выходные данные алгоритма ===
+=== Свойства алгоритма ===
+== Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
+=== Возможные способы и особенности параллельной реализации алгоритма ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
+Программа, реализующая поиск транзитного замыкания, состоит CPU части, отвечающей за общую координацию вычислений, использующей вспомогательные классы
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
-* C++: [http://cdelib.sourceforge.net Chemical Descriptors Library] (функция <code>[http://cdelib.sourceforge.net/doc/ullmann.html ullman]</code>).
-* C++: [http://mivia.unisa.it/datasets/graph-database/vflib/ VF Library].
 == Литература ==
 <references />
+[[Категория:Начатые статьи]]
+[[en:Ullman's algorithm]]