Сравнение графов(?)

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

Перебрать все возможные перестановки. Применить каждую к первому графу и сравнить любые их конструкторы.

Кривая реализация этого на bash:

http://kmeaw.com/permute.sh

Пример входного файла:

digraph DFA {
size="8,5";
node [rank = max]; a;
node [shape = doublecircle, rank = min]; b;
node [shape = circle];
a -> a [ label = "a" ];
a -> b [ label = "b" ];
b -> a [ label = "" ];
}

курить гугол на тему "изоморфизм графов"

А вообще-то данная задача гораздо проще, чем задача распознания изоморфизма графов. По крайней мере, если речь идет о кристаллах, то достаточно определить пространственную группу и сравнивать координаты симметрийно-неэквивалентных ядер.

diff-ом их

> diff-ом их Феерический бред. Из неравенства матриц смежности не следует, что графы не изоморфны.

Эээ... Товарищ! А зачем вам это?

Я эту задачку именно для этого применения когда-то и разбирал..

эффективный эвристический алгоритм изоморфизма графов.

шаг N1:
если G1.vericles().size()!=G2.verticles.size() то графы различны
шаг N2:
цикл i=0..(G1.verticles.size()-1)
/проверяем что вершины G1.0 и G2.i "похожи", то есть имеют одинаковое количество рёбер/
если G1.verticles[0].edges().size()!=G2.verticles[i].edges().size() то next;

далее впадаем в следование по рёбрам, рекурсию и тд

Неа, не всё так просто.. Он же про фазы говорит. А пр. группа у фаз обычно отличается. Так что сравнивать нужно именно графы.

если что - стучись в аську.

Да, именно так. Только вершины ещё могут различаться не только по степени но и по типу (атомов), а ребра скорее всего имеют вес (т.е. расстояния между атомами - длины (связей)), что также надо учитывать.

Хм, сразу-то и не понял, что вещества похоже подразумеваются разные. Тогда надо немного уточнить начальные условия..

> А вообще-то данная задача гораздо проще, чем задача распознания изоморфизма графов. По крайней мере, если речь идет о кристаллах, то достаточно определить пространственную группу и сравнивать координаты симметрийно-неэквивалентных ядер.

Если пространственная группа одинакова и ячейки близки. Тогда задача обычно легко решается и вручную. В моём случае нужно сравнить, например, группы P4 и C2/c и ячейки различаются в 12 раз.

> А зачем вам это?

Сравнивать сильно различающиеся полиморфные модификации. Для описания механизма превращения. А также сравнивать предположительно изоструктурные вещества.

> Я эту задачку именно для этого применения когда-то и разбирал..

Я надеялся, что кто-нибудь с этим сталкивался и нашёл готовую программу для подобного сравнения.

> Только вершины ещё могут различаться не только по степени но и по типу (атомов), а ребра скорее всего имеют вес (т.е. расстояния между атомами - длины (связей)), что также надо учитывать.

Да, конечно, про различающиеся атомы я забыл сказать. Насчёт связей -- это неорганика, связи могут и рваться и сохраняться.

> Перебрать все возможные перестановки.

> Кривая реализация этого на bash:

> Пример входного файла:

Спасибо, но как раз полного перебора хотелось бы избежать, как-то ограничив его по координатам. Сколько времени займёт такой перебор для 480 вершин?

> эффективный эвристический алгоритм изоморфизма графов.

Спасибо...

> матрицы смежности,

> курить гугол на тему "изоморфизм графов"

Курю...

Мамочка! Это что 480 независимых атомов в неорганике?!!

Или всё-таки 60 c учетом группы P4?

> Мамочка! Это что 480 независимых атомов в неорганике?!! Или всё-таки 60 c учетом группы P4?

Приходилось слышать про какой-то триклинный цеолит с ~980 независимых атомов :)

Но я немного напутал. 2 модификации (P41 и C2/c) PbTeO3 имеют соответственно 5 и 15 независимых атомов в ячейке и 20 и 120 всего. 3 модификации SrTeO3, по которым у меня данные под рукой (C2, C2/c и P-1) имеют 32, 32 и 30 независимых и 120, 240 и 60 всего. Пока это самые сложные структуры, которые я пытаюсь сравнивать. Я почему-то подумал, что у SrTeO3 C2/c 480 атомов в ячейке.

Так как ячейку можно выбрать неединственным способом, мне кажется, что следует сравнивать ячейку одной структуры с 8 ( 2 x 2 x 2 ) ячейками другой, если они одинакового размера. То есть ища соответствие одного графа обходить другой, вдвое больший во всех трёх измерениях, чтобы не упереться в границу.

Осталось решить как задавать связи. Для сильно деформированного окружения выбор какие атомы металла и кислорода считать связанными довольно произволен...

Нда. Тогда наверное единственный вариант - задавать _все_ связи (ну меньше суммы ВДВ радиусов IMHO), а при сравнении брать больший допуск расхождения. Сравнивать естественно в декартовых координатах, а не в долях ячейки. И, возможно, ограничить сначала сравнением маленького кубика (который бы полностью включал в себя самую большую из независимых частей ячейки во всех группах).

Таки-у вас в неорганике свои большие сложности )