Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
← Предыдущая правка
Нет описания правки
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
{{level-a}}
== Свойства и структура алгоритма ==
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
=== Общее описание алгоритма ===
Строка 16: Строка 18:
== Программная реализация алгоритма ==
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Результаты прогонов ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
* C++: [http://mivia.unisa.it/datasets/graph-database/vflib/ VF Library].
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/vf2_sub_graph_iso.html vf2_subgraph_iso]</code>).
* Python: [https://networkx.github.io NetworkX] (см. [https://networkx.github.io/documentation/latest/reference/algorithms.isomorphism.vf2.html VF2 Algorithm]).
== Литература ==
== Литература ==


Строка 37: Строка 26:


[[Категория:Начатые статьи]]
[[Категория:Начатые статьи]]
[[en:VF2 algorithm]]

Текущая версия от 11:11, 6 июля 2022


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

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

Алгоритм VF2[1] предназначен для поиска изоморфных подграфов больших графов.

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

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

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

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

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

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

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

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

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

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

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

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

Результаты прогонов

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

Литература

  1. ↑ Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Алгоритм_VF2&oldid=28974