ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
УДК 004.421.2:519.178
ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
С.В. Москаленко, Ю.А. Гатчин
Предложен ряд оптимизирующих моментов для современных алгоритмов идентификации графового изоморфизма, призванных увеличить скорость работы данных алгоритмов с сохранением точности вычисления результатов. Ключевые слова: теория графов, распознавание графических образов, определение межграфового изоморфизма.
Введение В последнее время растет объем обрабатываемой инженерной документации, в частности, приборостроительных и машиностроительных чертежей. Эта тенденция возникла в связи с активизацией использования электронной версии инженерной документации в САПР [1]. Довольно частой практикой для инженеров и проектировщиков является обращение к уже существующей документации, однако данный процесс всегда оказывается трудоемким, так как требует просмотра всей базы чертежей. Для упрощения поиска часто используется текстовая составляющая документа, когда происходит просмотр по ключевым словам. Такой подход весьма эффективен, но существуют трудности, связанные с получением этой текстовой информации (необходимо вмешательство человека), кроме того, набор ключевых слов не всегда точно может описать содержание чертежа. Поиск требуемого изображения в БД есть не что иное, как проблема сопоставления графических объектов, которая может быть решена путем вычисления степени соответствия входного объекта объекту в базе данных (БД) и сведена к процессу сопоставления графов. Для этого инженерная документация сначала приводится к представлению атрибутивных графов, где вершины графов отображают примитивы, полученные из исходных документов (линии, кривые) [2], а топологические связи 98 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 2(66)
С.В. Москаленко, Ю.А. Гатчин
между этими примитивами описаны ребрами графов. Далее вершины графов задаются метками, которые вычисляются по некоторой функции. Метки, как правило, являются целыми числами и используются для сравнения входных графов с заданными в БД графами. Таким образом, сравнивая ребра и метки графов, можно обнаружить чертежи, находящиеся в БД, целиком или частично схожие с текущим чертежом.
В статье рассматривается подкласс процесса сопоставления графов – проверка графов на изоморфизм (далее графовый изоморфизм или ГИ). ГИ можно определить следующим образом: два графа G=(V1, E1) и H=(V2, E2) изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Понятие ГИ находит применение в различных направлениях – при определении поврежденных клеток на медицинских снимках, поиске изоморфных химических соединений [3], сравнении пар кинематических цепей [4], и т.д. Для решения проблемы поиска ГИ, однако, не существует достаточно эффективных алгоритмов, обладающих полиномиальным временем исполнения, даже если алгоритм ограничен по области применения (например, операции проходят над строго однородными графами). В работе [5] представлен эффективный алгоритм, обладающий сложностью вычисления O (n1/3 log n), но оперирующий лишь со строго однородными графами. В работе [6] приведен еще один алгоритм, являющийся линейным для большинства случайных графов. Однако последний имеет ряд недостатков, которые связаны с невозможностью разрешения неопределенных ситуаций, возникающих при обнаружении множества идентичных друг другу вершин. В рамках данной статьи предложены 3 оптимизационных момента, призванные ускорить поиск ГИ в современных алгоритмах сопоставления графов.
Реализация алгоритма
Сформулируем обобщенный алгоритм работы многих современных систем идентификации ГИ [6, 7]. На старте алгоритм имеет некоторый входной помеченный граф (вершинам которого приписаны метки), а также база данных (БД) эталонных помеченных графов. Требуется найти граф в БД, изоморфный входному графу (см. определение 1, с. 101). Вначале алгоритм строит связи между всеми вершинами входного графа со всеми вершинами эталонного графа в БД, которые имеют одинаковые метки. Ситуацию, когда одна вершина в одном графе идентична с несколькими вершинами в другом, называют неопределенной. На следующих шагах после обнаружения удовлетворяющего эталона алгоритм пытается сократить число ложных связей. Для снижения числа случаев ошибочного определения изоморфизма отдельные алгоритмы, например [6], реализуют вовлечение информации о соседних вершинах в функцию вычисления меток.
Итак, обобщенный алгоритм идентификации ГИ выглядит следующим образом.
− Шаг 1 (предобработка). Для входного графа и для всех графов в БД высчитываются степени у вершин и собирается другая информация, необходимая для последующих шагов, например, тип линии для примитивов инженерных чертежей. Далее полученные данные используются в качестве аргументов функции вычисления меток. На данном шаге также может собираться информация о соседних вершинах (количество степеней и пр.) для включения в функцию вычисления меток.
− Шаг 2 (построение связей). Связи строятся между двумя сравниваемыми графами для всех пар вершин, которые имеют одинаковые метки. Пример таких связей приведен на рис. 1, где различные метки показаны черным, белым или серым цветом, вершина u графа G связана с вершиной v графа Н. Две вершины соединены потому, что метка от u совпадает с меткой от v, т.е. метка и степень вершины u равны соот-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)
99
ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
ветствующим значениям вершины v, а каждый потомок (смежная вершина) от узла u, а именно i, j, k, имеет соответствующего потомка от узла v с такой же меткой и степенью. На рис. 1 потомки i, j, k графа G совпадают с x, y, z на графе H. Однако ясно видно, что графы G и H не изоморфны.
связь между двумя графами
Рис. 1. Построение связи между двумя графами
− Шаг 3 (редукция энтропии). Данный шаг является самой затратной частью алгоритма по количеству вычислений. Происходит попытка разрешить неопределенные ситуации, если таковые возникли на предыдущем шаге, и сделать вывод о наличии изоморфизма между входным графом и эталонным графом.
Рис. 2. Иллюстрация работы алгоритма поиска ГИ: а – шаг предобработки, даны два графа G и Н; б – шаг построения связей; в – шаг редукции энтропии
На рис. 2 изображены все шаги представленного алгоритма. На этапе предобработки (рис. 2, а) для обоих графов вычисляются метки для каждой вершины. Здесь каждая вершина содержит метку с информацией о текущем узле, а также о его соседях. Вдобавок следует отметить, что все метки графов G и Н одинаковы как внутри графов, так и между G и Н. Это равенство обусловлено тем, что метки самих вершин изначально равны (все кружочки отмечены белым цветом), оба графа являются однородными (одинаковое число ребер, смежных с каждым узлом). Данное равенство дает высокую степень неопределенности, когда каждая вершина графа G может быть соединена с каждой вершиной Н (рис. 2, б). Неопределенность разрешается на шаге редукции энтропии (рис. 2, в), когда стартует детальный анализ графов.
100
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)
С.В. Москаленко, Ю.А. Гатчин
Пути оптимизации алгоритма
В предыдущем разделе был показан пример (рис. 2), когда при сопоставлении двух графов возникали избыточные неопределенные ситуации. Разрешение таких ситуаций – весьма трудоемкий процесс, требующий привлечения процедуры детального анализа графов, во время работы которой происходит последовательное продвижение по уровням графа (каждый уровень характеризуется набором всех вершин, смежных с любой текущей вершиной). Существует еще ряд проблем, связанных с трудозатратами, которые линейно возрастают по мере добавления в БД эталонных графов. В данном разделе приведены два критерия и один момент, которые могут быть вовлечены в любой алгоритм поиска ГИ в качестве оптимизирующих мер.
Ниже даны несколько ключевых определений. Определение 1. Графовый изоморфизм. Даны 2 графа G=(V1, E1) и H=(V2, E2), где │V1│=│V2│. Граф G изоморфен Н (G=Н), при V1 →V2 │ ∃ (u, v) E1 && ∃ (f(u), f(v)) ∈ E2 && l(u) ∈ l(f(u))│ ∀ u ∈ V1, где l – функция вычисления метки для вершины. Определение 2. Соответствие (идентичность) вершин. Пусть u ∈ V1 – вершина графа G, а v ∈ V2 – вершина графа Н. Считается, что узел u идентичен узлу v, если метка от u равна метке от v. Определение 3. Степенью неопределенности узла u, принадлежащего графу G, называется число узлов графа Н, с которыми u идентичен. Обозначение: deg(u)=m, где m – число вершин ∈ Н, которым соответствует узел u. Критерий 1. При поиске в БД эталонного графа, изоморфного входному, для каждого графа в БД запускается алгоритм идентификации ГИ, описанный выше. Ясно, что это весьма трудоемкий подход, требующий большого количества вычислений. Для оптимизации поиска ГИ можно ввести условие: во время первого пробега (последовательного сопоставления входного графа с каждым эталонным) алгоритм идентификации ГИ должен запускаться лишь для эталонных графов с числом вершин, равным или меньшим числа вершин входного графа. Данное условие применимо лишь для графов, которые отражают графическую информацию, заложенную в изображениях (инженерная документация, чертежи). Для таких изображений характерно наличие шумов, сказывающихся появлением на графах дополнительных вершин и ребер. Действительно, при разрыве линии на чертеже или при появлении случайного штриха, вызванного недостатками процесса сканирования, появляются шумы, которые, однако, не повлияют на вывод о наличии ГИ. На вход процедуры сравнения графов подаются G – входной граф, {Н} – множество эталонных графов в БД, G=(V1, E1) и H=(V2, E2). 1.Для каждого Н 2. если (│V1│≥│V2│) 3. выполняется алгоритм поиска ГИ 4. если (ГИ обнаружен) 5. тогда выход их программы с результатом «ГИ найден» 6.Для каждого Н 7. если (│V1│
УДК 004.421.2:519.178
ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
С.В. Москаленко, Ю.А. Гатчин
Предложен ряд оптимизирующих моментов для современных алгоритмов идентификации графового изоморфизма, призванных увеличить скорость работы данных алгоритмов с сохранением точности вычисления результатов. Ключевые слова: теория графов, распознавание графических образов, определение межграфового изоморфизма.
Введение В последнее время растет объем обрабатываемой инженерной документации, в частности, приборостроительных и машиностроительных чертежей. Эта тенденция возникла в связи с активизацией использования электронной версии инженерной документации в САПР [1]. Довольно частой практикой для инженеров и проектировщиков является обращение к уже существующей документации, однако данный процесс всегда оказывается трудоемким, так как требует просмотра всей базы чертежей. Для упрощения поиска часто используется текстовая составляющая документа, когда происходит просмотр по ключевым словам. Такой подход весьма эффективен, но существуют трудности, связанные с получением этой текстовой информации (необходимо вмешательство человека), кроме того, набор ключевых слов не всегда точно может описать содержание чертежа. Поиск требуемого изображения в БД есть не что иное, как проблема сопоставления графических объектов, которая может быть решена путем вычисления степени соответствия входного объекта объекту в базе данных (БД) и сведена к процессу сопоставления графов. Для этого инженерная документация сначала приводится к представлению атрибутивных графов, где вершины графов отображают примитивы, полученные из исходных документов (линии, кривые) [2], а топологические связи 98 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 2(66)
С.В. Москаленко, Ю.А. Гатчин
между этими примитивами описаны ребрами графов. Далее вершины графов задаются метками, которые вычисляются по некоторой функции. Метки, как правило, являются целыми числами и используются для сравнения входных графов с заданными в БД графами. Таким образом, сравнивая ребра и метки графов, можно обнаружить чертежи, находящиеся в БД, целиком или частично схожие с текущим чертежом.
В статье рассматривается подкласс процесса сопоставления графов – проверка графов на изоморфизм (далее графовый изоморфизм или ГИ). ГИ можно определить следующим образом: два графа G=(V1, E1) и H=(V2, E2) изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.
Понятие ГИ находит применение в различных направлениях – при определении поврежденных клеток на медицинских снимках, поиске изоморфных химических соединений [3], сравнении пар кинематических цепей [4], и т.д. Для решения проблемы поиска ГИ, однако, не существует достаточно эффективных алгоритмов, обладающих полиномиальным временем исполнения, даже если алгоритм ограничен по области применения (например, операции проходят над строго однородными графами). В работе [5] представлен эффективный алгоритм, обладающий сложностью вычисления O (n1/3 log n), но оперирующий лишь со строго однородными графами. В работе [6] приведен еще один алгоритм, являющийся линейным для большинства случайных графов. Однако последний имеет ряд недостатков, которые связаны с невозможностью разрешения неопределенных ситуаций, возникающих при обнаружении множества идентичных друг другу вершин. В рамках данной статьи предложены 3 оптимизационных момента, призванные ускорить поиск ГИ в современных алгоритмах сопоставления графов.
Реализация алгоритма
Сформулируем обобщенный алгоритм работы многих современных систем идентификации ГИ [6, 7]. На старте алгоритм имеет некоторый входной помеченный граф (вершинам которого приписаны метки), а также база данных (БД) эталонных помеченных графов. Требуется найти граф в БД, изоморфный входному графу (см. определение 1, с. 101). Вначале алгоритм строит связи между всеми вершинами входного графа со всеми вершинами эталонного графа в БД, которые имеют одинаковые метки. Ситуацию, когда одна вершина в одном графе идентична с несколькими вершинами в другом, называют неопределенной. На следующих шагах после обнаружения удовлетворяющего эталона алгоритм пытается сократить число ложных связей. Для снижения числа случаев ошибочного определения изоморфизма отдельные алгоритмы, например [6], реализуют вовлечение информации о соседних вершинах в функцию вычисления меток.
Итак, обобщенный алгоритм идентификации ГИ выглядит следующим образом.
− Шаг 1 (предобработка). Для входного графа и для всех графов в БД высчитываются степени у вершин и собирается другая информация, необходимая для последующих шагов, например, тип линии для примитивов инженерных чертежей. Далее полученные данные используются в качестве аргументов функции вычисления меток. На данном шаге также может собираться информация о соседних вершинах (количество степеней и пр.) для включения в функцию вычисления меток.
− Шаг 2 (построение связей). Связи строятся между двумя сравниваемыми графами для всех пар вершин, которые имеют одинаковые метки. Пример таких связей приведен на рис. 1, где различные метки показаны черным, белым или серым цветом, вершина u графа G связана с вершиной v графа Н. Две вершины соединены потому, что метка от u совпадает с меткой от v, т.е. метка и степень вершины u равны соот-
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)
99
ОПТИМИЗАЦИЯ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ГРАФОВОГО ИЗОМОРФИЗМА
ветствующим значениям вершины v, а каждый потомок (смежная вершина) от узла u, а именно i, j, k, имеет соответствующего потомка от узла v с такой же меткой и степенью. На рис. 1 потомки i, j, k графа G совпадают с x, y, z на графе H. Однако ясно видно, что графы G и H не изоморфны.
связь между двумя графами
Рис. 1. Построение связи между двумя графами
− Шаг 3 (редукция энтропии). Данный шаг является самой затратной частью алгоритма по количеству вычислений. Происходит попытка разрешить неопределенные ситуации, если таковые возникли на предыдущем шаге, и сделать вывод о наличии изоморфизма между входным графом и эталонным графом.
Рис. 2. Иллюстрация работы алгоритма поиска ГИ: а – шаг предобработки, даны два графа G и Н; б – шаг построения связей; в – шаг редукции энтропии
На рис. 2 изображены все шаги представленного алгоритма. На этапе предобработки (рис. 2, а) для обоих графов вычисляются метки для каждой вершины. Здесь каждая вершина содержит метку с информацией о текущем узле, а также о его соседях. Вдобавок следует отметить, что все метки графов G и Н одинаковы как внутри графов, так и между G и Н. Это равенство обусловлено тем, что метки самих вершин изначально равны (все кружочки отмечены белым цветом), оба графа являются однородными (одинаковое число ребер, смежных с каждым узлом). Данное равенство дает высокую степень неопределенности, когда каждая вершина графа G может быть соединена с каждой вершиной Н (рис. 2, б). Неопределенность разрешается на шаге редукции энтропии (рис. 2, в), когда стартует детальный анализ графов.
100
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)
С.В. Москаленко, Ю.А. Гатчин
Пути оптимизации алгоритма
В предыдущем разделе был показан пример (рис. 2), когда при сопоставлении двух графов возникали избыточные неопределенные ситуации. Разрешение таких ситуаций – весьма трудоемкий процесс, требующий привлечения процедуры детального анализа графов, во время работы которой происходит последовательное продвижение по уровням графа (каждый уровень характеризуется набором всех вершин, смежных с любой текущей вершиной). Существует еще ряд проблем, связанных с трудозатратами, которые линейно возрастают по мере добавления в БД эталонных графов. В данном разделе приведены два критерия и один момент, которые могут быть вовлечены в любой алгоритм поиска ГИ в качестве оптимизирующих мер.
Ниже даны несколько ключевых определений. Определение 1. Графовый изоморфизм. Даны 2 графа G=(V1, E1) и H=(V2, E2), где │V1│=│V2│. Граф G изоморфен Н (G=Н), при V1 →V2 │ ∃ (u, v) E1 && ∃ (f(u), f(v)) ∈ E2 && l(u) ∈ l(f(u))│ ∀ u ∈ V1, где l – функция вычисления метки для вершины. Определение 2. Соответствие (идентичность) вершин. Пусть u ∈ V1 – вершина графа G, а v ∈ V2 – вершина графа Н. Считается, что узел u идентичен узлу v, если метка от u равна метке от v. Определение 3. Степенью неопределенности узла u, принадлежащего графу G, называется число узлов графа Н, с которыми u идентичен. Обозначение: deg(u)=m, где m – число вершин ∈ Н, которым соответствует узел u. Критерий 1. При поиске в БД эталонного графа, изоморфного входному, для каждого графа в БД запускается алгоритм идентификации ГИ, описанный выше. Ясно, что это весьма трудоемкий подход, требующий большого количества вычислений. Для оптимизации поиска ГИ можно ввести условие: во время первого пробега (последовательного сопоставления входного графа с каждым эталонным) алгоритм идентификации ГИ должен запускаться лишь для эталонных графов с числом вершин, равным или меньшим числа вершин входного графа. Данное условие применимо лишь для графов, которые отражают графическую информацию, заложенную в изображениях (инженерная документация, чертежи). Для таких изображений характерно наличие шумов, сказывающихся появлением на графах дополнительных вершин и ребер. Действительно, при разрыве линии на чертеже или при появлении случайного штриха, вызванного недостатками процесса сканирования, появляются шумы, которые, однако, не повлияют на вывод о наличии ГИ. На вход процедуры сравнения графов подаются G – входной граф, {Н} – множество эталонных графов в БД, G=(V1, E1) и H=(V2, E2). 1.Для каждого Н 2. если (│V1│≥│V2│) 3. выполняется алгоритм поиска ГИ 4. если (ГИ обнаружен) 5. тогда выход их программы с результатом «ГИ найден» 6.Для каждого Н 7. если (│V1│