2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 26  След.
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение07.06.2013, 18:14 


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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение07.06.2013, 21:00 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение11.06.2013, 11:36 


26/01/10
959
Здравствуйте, bin.

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

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

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение12.06.2013, 15:26 
Аватара пользователя


22/09/09

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение12.06.2013, 16:56 


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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение12.06.2013, 17:27 
Аватара пользователя


22/09/09

1907
Zealint
См. http://arxiv.org/abs/1004.1808 или
bin в сообщении #730933 писал(а):
секция Заключение. Модератор разрешил дать только эти ссылки. Кроме того, в этой секции статьи пароль для раззиповки.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение12.06.2013, 23:13 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.06.2013, 06:37 


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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение14.06.2013, 13:27 
Аватара пользователя


22/09/09

1907
Zealint в сообщении #736457 писал(а):
Может вам имело бы смысл когда-нибудь сделать, например, dll с функцией тестирования на изоморфизм?
Хорошая идея. Сделаю.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение15.06.2013, 16:46 
Аватара пользователя


22/09/09

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение16.06.2013, 16:42 


26/01/10
959
Не хочу показаться чайником, но придётся, видимо. У Вас в DLL функция хочет два параметра типа array of array типа boolean и два параметра типа integer. Теперь представьте, что у меня программа на Си, и она должна на вход вашей функции послать какие-то данные. Чтобы структура этих данных совпала, я должен знать, как в Delphi устроен этот самый array of array и каким образом хранится boolean. Иначе как я передам параметры-то? Я должен на Си как-то написать
Код:
bool (*MT2giLibGI)(???, ???, int, int);

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.06.2013, 14:49 
Аватара пользователя


22/09/09

1907
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.

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение17.06.2013, 22:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение19.06.2013, 14:46 
Аватара пользователя


22/09/09

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

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

 Профиль  
                  
 
 Re: Полиномиальный алгоритм изоморфизма графов
Сообщение21.06.2013, 12:45 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Опять возражу против Вашего определения подобия:
Цитата:
В соответствии с определением Харари: "Две вершины $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'$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 380 ]  На страницу Пред.  1 ... 18, 19, 20, 21, 22, 23, 24 ... 26  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group