Утилита для Graph Isomorphism Testing

[upsetter]

Моя последняя версия для сабжа:
http://sourceforge.net/projects/griso/files/
Я опять в поисках контрпримера. Может кто поможет?

PS
Ес-но, у утилиты polynomial time algorithm, иначе я ее не городил бы.

[bin]

Позвольте дать совет (из собственного опыта): опишите подробно Ваш алгоритм (в виде статьи), приведите доказательство и ... на Вас хлынет поток опровержений с контрпримерами (как и на меня) (К сожалению, только с исходными кодами мало кто любит работать.)
В любом случае желаю успеха! Приветсвую каждую попытку решить проблему GI!

[upsetter]

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

И у Вас и у меня поли-тайм алгоритм. Значит, тандем обоих алгоритмов и есть то, что люди так долго искали. Или я неправ?

[upsetter]

Так, что-то я зарапортавался.
А если у bin-а ответ будет "неизоморфны", а у меня "изоморфны"?
И непонятно кто из нас двоих прав.

[bin]

upsetter в сообщении #606622 писал(а):

А если у bin-а ответ будет "неизоморфны", а у меня "изоморфны"?И непонятно кто из нас двоих прав.

Если Ваша программа (как и моя) не просто отвечает на вопрос "да/нет", но выдает какую ни будь подстановку, то проверить будет ли такая подстановка изоморфизмом нетрудно.

-- Пн авг 20, 2012 16:11:55 --

upsetter в сообщении #606468 писал(а):

И у Вас и у меня поли-тайм алгоритм. Значит, тандем обоих алгоритмов и есть то, что люди так долго искали. Или я неправ?

Чтобы ответить на этот вопрос нужно разобраться в Вашем алгоритме, но только по коду сделать это непросто (о чем свидетельствует отсутсвие откликов здесь, и о чем я писал выше). Сделайте здесь короткое, но подробное описание использованных принципов, тогда будет проще их оценить.