Полиномиальный алгоритм изоморфизма графов

[rtfai]

У Вас нет доказательства конечности бэктрэгинов. "Их мало", это не ответ. Я могу только повторить формулировку которую уже озвучил: для любого графа число бектрекингов должно быть ограничено степенью числа вершин в некоторой фиксированной степени.

Более того, например, когда я предложил одному журналу ДРУГОЙ результат с доказательством, у меня потребовали доказательство более короткое и удовлетворяющее требованиям журнала.

[bin]

rtfai
о каких "бэктрэкингах" Вы говорите? В новом алгоритме, который я выложил несколько дней назад, их вообще нет.

[Zealint]

Здравствуйте, bin.

Вопрос по Вашей реализации. Насколько быстро можно проверить с её помощью изоморфизм графов из приблизительно 20 вершин (чуть меньше) с той оговоркой, что нужно выполнить несколько миллионов таких проверок за приемлемое время?

Мой коллега занимается задачей в которой нужно, помимо прочего, построить все неизоморфные графы, которые получаются из графа $C_n$ (цикл) путём последовательного склеивания всех возможных пар вершин в одну. Экспоненциальный алгоритм проверки изоморфизма с различными самопальными эвристиками в этом случае работает довольно быстро, но для $n=12$ уже не мгновенно. Нам же нужны все такие подграфы приблизительно до $n=20$. Или Ваш алгоритм, как и все похожие алгоритмы, хорош лишь в теории или на очень больших графах?

Я всерьез заинтересовался бы вашей разработкой, если она сможет ускорить наши программы и при этом даст правильные ответы. Тут только беда в том, что нам нужна не отдельная программа, как у Вас, а её нужно как бы встроить в код в виде процедуры типа isIsomorphic ( G1, G2 ), которая вернёт "точно да" или "точно нет".

А вдруг вы уже отвечали на этот вопрос? К сожалению, всю тему прочитать не могу, сами понимаете : )

[bin]

Здравствуйте, Zealint.

В секции Заключение статьи я подчеркиваю, что основной целью является теоретический результат. Поэтому я не оптимизировал реализацию, напротив, пытался упростить исходный код, возможно, в некоторых местах в ущерб скорости. Хотя я применяю простые приемы сжатия строк (замена двух символов "$x;$", где $x$ - шестнадцатиричная цифра, на один символ), но эти трюки явно не исчерпывают всех возможностей. Прежде всего строка типа string - видимо, не самый экономный тип данных. При таком подходе сравнивать среднее время работы реализации моего алгоритма с временем работы программ, написанных для практических целей, смысла не имеет. Поэтому таких сравнений я не делал, но, отлаживая программу, испытывал ее на разных графах. Могу сказать, что сравнение двух изоморфных графов в сорок вершин занимает около часа на Pentium 4 (3 ГГц). Что касается встраивания в код моей процедуры тестирования на изоморфизм - тут нет никаких проблем. Программа выполнена по модульному принципу, в ней оболочка GUI и модули тестирования на изоморфизм, подключаете эти модули к своей программе и вызываете процедуру тестирования. Графы на входе задаются матрицами смежности, реализованными динамическими массивами.

[Zealint]

bin
А вас не затруднит ещё раз дать ссылку на последнюю версию программы? Или назовите номер страницы в этой теме, где искать. Я попробую подключить к своему коду, когда найду время.

[bin]

Zealint
См. http://arxiv.org/abs/1004.1808 или

bin в сообщении #730933 писал(а):

Файл с переводом

секция Заключение. Модератор разрешил дать только эти ссылки. Кроме того, в этой секции статьи пароль для раззиповки.

[bin]

PS Хотя в файле ReadMe, приложенном к программе, даны недвусмысленные предупреждения, что данная программа является экспериментальной и сделана только с одной целью - продемонстрировать реализацию описанного в указанном препринте алгоритма, я все же решил предупредить лишний раз здесь, что хоть я и уверен в своей правоте, но, к сожалению, никто не может исключить вероятности, что в программе или в алгоритме не найдутся ошибки. Т.о. использование этой программы или ее составных частей - Ваш свободный выбор и личный риск. Пока общего признания моему подходу нет.

[Zealint]

Ну вот, сел разбираться с Вашей программой, а она оказалась на Delphi : ( Я ожидал, что вырежу кусок и вставлю в свою программу на Си. Но переписывать ваш код сейчас не хотелось бы. Наверное, я не один такой, кто хотел проверить, но не получилось. Может вам имело бы смысл когда-нибудь сделать, например, dll с функцией тестирования на изоморфизм?

[bin]

Zealint в сообщении #736457 писал(а):

Может вам имело бы смысл когда-нибудь сделать, например, dll с функцией тестирования на изоморфизм?

Хорошая идея. Сделаю.

[bin]

Сделал DLL: лежит на той же странице, где и основная программа, пароль такой же (см. статью). Испытуемые DLL графы должны иметь одинаковое количество вершин и одинаковое количество ребер (надо будет добавить в ReadMe файл).

[Zealint]

Не хочу показаться чайником, но придётся, видимо. У Вас в DLL функция хочет два параметра типа array of array типа boolean и два параметра типа integer. Теперь представьте, что у меня программа на Си, и она должна на вход вашей функции послать какие-то данные. Чтобы структура этих данных совпала, я должен знать, как в Delphi устроен этот самый array of array и каким образом хранится boolean. Иначе как я передам параметры-то? Я должен на Си как-то написать

bool (*MT2giLibGI)(???, ???, int, int);

А как устроена ваша структура матрицы, я не знаю. Она же динамическая, как я понимаю? Там где-то как-то хранится служебная информация, какова она, неясно. И тип boolean тоже может быть реализован по-разному: через биты или через байты.

Или я не умею пользоваться функциями dll?

[bin]

Zealint
И я не хочу показаться чайником, но придется признать, что мои знания C/C++ очень однобоки: я хорошо знаком с литературой по сравнению языков программирования (в том числе и этих), но использую C и C++ только в одну сторону: перевожу с них на Паскаль или (когда нужно) на ассемблер, но ничего не пишу на Си. Поэтому сходу сообразить, как должен выглядеть вызов данной функции на Си, я затрудняюсь. Но вокруг много специалистов, кто переводил с Паскаля на Си, и они быстро сумеют ответить на Ваш вопрос. Например, его стоит задать в ветке Программирование этого форума. Могу еще помочь цитатой из Object Pascal Language Guide, Borland:

Цитата:

A Boolean type is stored as a Byte[…] A Boolean can assume the values 0 (False) and 1 (True).[…]

A dynamic-array variable occupies four bytes of memory which contain a pointer to
the dynamically allocated array. When the variable is empty (uninitialized) or holds
a zero-length array, the pointer is nil and no dynamic memory is associated with the
variable. For a nonempty array, the variable points to a dynamically allocated block
of memory that contains the array in addition to a 32-bit length indicator and a 32-bit
reference count. The table below shows the layout of a dynamic-array memory block.

Offset Contents
–8 32-bit reference-count
–4 32-bit length indicator (number of elements)
0..Length * (size of element) – 1 array elements

И еще у меня к Вам просьба: когда и если разберетесь, как сделать вызов, опубликуйте, пожалуйста, здесь или пришлите мне на ЛС, я добавлю его в файл ReadMe.

[Yuri Gendelman]

Возможно эти статьи вам (обоим) помогут или хотя бы подскажут где и что искать.:
Calling delphi DLL from MS Visual C++
Calling Delphi DLL from C++ using GetProcAddress: callback function fails with invalid parameter

[bin]

Выложил исправленную версию препринта (несколько локальных исправлений) и новый перевод. Ссылки не изменились.

Yuri Gendelman
Спасибо за статьи по DLL.

[whitefox]

Опять возражу против Вашего определения подобия:

Цитата:

В соответствии с определением Харари: "Две вершины $u$ и $v$ графа $G$
называются подобными, если для некоторого автоморфизма $\alpha$ этого графа
$\alpha(u)=v$" [9]. Расширим это определение:

Определение 1. Вершина $v$ графа $G$ и вершина $v'$ графа $G'$ подобны, если
существует изоморфизм $\pi$ графа $G$ на граф $G'$ такой, что $\pi(v)=v'$.

Допустим, что вершины $u$ и $v$ графа $G$ подобны в соответствии с классическим определением (по Харари).
Но по Вашему определению они уже не будут подобными, так как не существует изоморфизма $\pi$ графа $G$ на граф $G'$ такого, что $\pi(u)=v$.

Проблему можно решить если заменить Ваше Определение 1 следующим:

Определение 1. Будем говорить, что вершина $v$ графа $G$ и вершина $v'$ графа $G'$ подобны, если
они подобны как вершины графа $G\cup G'$.