алгоритм на связи вершин в графах

и где вопрос?

ну собственно нету вопроса, есть просьба предложить варианты алгоритмов

что-то я ничерта не понял.

Он у тебя неориентированный? Что еще за коннекторы? Хренпросышь пока поймешь. В чем вообще алгоритм заключается?

попутно своей разработки алгоритма решил задать вопрос ЛОРу

и где вопрос?

ну собственно нету вопроса

в скобочках ответ -> [ ]

есть просьба предложить варианты алгоритмов

к сожалению выполнить просьбу затруднительно, поскольку непонятно что именно должен делать алгоритм, что является его результатом работы, как проверяется соответствие между вершинами, что значит «наиболее подходящие связи» и т.д.

subgraph isomorphism problem, гуглить алгоритмы Ульмана:

http://dl.acm.org/citation.cfm?doid=321921.321925

Вот тебе даже прямая ссылка на статью:

http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf

Сам писал подобное для квантовой химии.

Вот тебе даже прямая ссылка на статью:

Но это конечно если я запрос распарсил правильно. С выражением мыслей-то у ТС явно проблемы.

наиболее подходящие связи

Переведи с русского на математический.

предложить варианты алгоритмов

Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах.

P.S. «Алгоритмы на графах» // врио К.О. :)

есть 2 графа, где связи двунаправленные, каждая вершина содержит несколько коннеторов, связи идут по коннекторам. Ну представьте себе эл. резистор и конденсатор, их можно соединить несколькими способами, через разные полюса. Вот примерно для этого я и ввёл коннекторы в граф.

Коннекторы 2х графов мы не сравниваем, но сравниваем связи, следовательно надо знать с какого коннектора в какие ветки идут связи. В примере видно, что во втором графе из «a» связи идут по коннектору "(2)" в вершины «b» и «c», а в первом из '«a» в «b» и «c» идут связи по 2м разным коннекторам => результат не содержит наименее подходящую связь.

http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf...

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

Не совсем понятно условие. Два уточняющих вопроса:

1. Верно ли, что второй граф содержит все связи, которые есть в первом?

2. Верно ли, что нужно найти такое соответствие между рёбрами, чтобы одинаковые коннекторы при одной вершине соответствовали одинаковым, а разные — разным?

Если да, то мне кажется, задачу можно переформулировать, сделав «коннекторы» полноценными вершинами и сгруппировав их по номерам. Тогда получится так:

a-(1)---(2)-b
 \
 (2)---(1)-c

a-(3)--(1)-b
 \   __/
  \ /
 (2)---(1)-c

1. нет 2. что значит одинаковым? я их сравниваю только по критерию - в какуие вершины мы из них идём.

сделав «коннекторы» полноценными вершинами и сгруппировав их по номерам

согласен. Но зачем группировать? их не сравниваем между собой. Т.е. коннектор «1» графа «A» вершины «a» вполне может соответствовать коннектору «B» -> «b» -> «2», если и них обоих идёт связь в вершину «s» и при этом нет связи, более «похожей»

И задача сводится к нахождению изоморфизма первого графа подграфу второго

можно подробнее, как всё же получить соответствие рёбер?

1. Верно ли, что второй граф содержит все связи, которые есть в первом?

нет

Можно пример такого случая? Желательно с пояснением того, по какому критерию «похожести» мы потом находим решение.

сделав «коннекторы» полноценными вершинами и сгруппировав их по номерам

согласен. Но зачем группировать? их не сравниваем между собой.

Я имел в виду не сравнивать, а ставить в соответствие. Но развивать тему нет смысла, пока условие не понятно.

У графов вроде рёбра, а не какие-то там коннекторы. Придерживайтесь общепринятой терминалогии и тогда вас начнут понимать.

Судя по дикой терминологии ты вообще не знаком с теорией и популярными алгоритмами. Это такой толстый намёк

Прочитал, потом ещё раз.

Пришло в голову вот это: http://demotivators.despair.com/incompetencedemotivator.jpg

Как выше уже сказали:

google: изоморфность графов алгоритм

Зачем изобретать велосипеды?

Затем, что задача автора может оказаться намного более частной, чем изоморфизм. Если бы только он объяснил по-человечески.

Годно

ребро - это сущность, связывающая 2 вершины графа(рассматриваем ненапрвленные рёбра).

вершина - это сущность, содержащая данные для её идентификации.

Представьте в моей задаче, что «коннекторы» - это полноценные вершины и принадлежность коннектора к вершине, как ребро между ними. И будет вам общая теория и изоморфизм графов. Неужели так сложно представить себе простую абстракцию? Предложите алгоритм, а главное приведите пример его работы на подходящих графах, где действительно есть проблема в сравнении рёбер. И это будет одним из решений поставленной задачи. Я что против вашей терминологии?

Можно пример такого случая? Желательно с пояснением того, по какому критерию «похожести» мы потом находим решение.

ну я использую 2 критерия - есть связь, нет связи.

a(1)---(2)b
 \
 (5)---(1)c

a(2)---(1)c(2)---(b)

ты хотел сказать, что можно сопоставить «a(5)---(1)c» и «a(2)---(1)c»? А «a(1)---(2)b» и «c(2)---(b)» оставить несопоставленными?

«a(1)---(2)b» и «c(2)---(b)»

их нельзя сопоставить хотябы потому, что нельзя сопоставить «a» и «c».

Посмотри первый пример в топике, там сопоставление «a(1)---(2)b» с «a(2)---(1)b» отвергается, потому, что есть более удачное сопоставление a(3)---(1)b

их нельзя сопоставить хотябы потому, что нельзя сопоставить «a» и «c».

Я понял, просто уточнял. Тогда получается, что нужно найти в двух графах сопоставление с максимальным количеством рёбер, верно? В литературе это называется максимальный общий подграф, MCS.

с максимальным количеством рёбер

с максимальным количеством _подходящих_ рёбер

есть 2 графа, где связи двунаправленные, каждая вершина содержит несколько коннеторов, связи идут по коннекторам. Ну представьте себе эл. резистор и конденсатор, их можно соединить несколькими способами, через разные полюса. Вот примерно для этого я и ввёл коннекторы в граф.

капец. Че за коннекторы? Че за связи? Вообще офигеть бред.

омг, вы ветку то читали?

А вообще бесит, что людям не представить что-то немного отличающееся, от стандартной теории. Стоило упомянуть графы и «капец» - используй только то, что есть в каждой книжке по графам для пятиклассников. Ну хрен с ними с графами! Что, не представить электрическую схему в удобной вам форме? абстрагируйтесь от «стадартных» графов, хотябы в этой задаче

Че за коннекторы?

Че, неужели не представить? Это и в самом деле так сложно? Не, ну правда

Это и в самом деле так сложно? Не, ну правда

Неужели так сложно описать задачу просто и понятно, а не вводить ненужные сущности и не придумывать велосипеды?

проще некуда. А те, непонятные вам сущности, ввел не я. Мне предоставляют такое представление, а как уже с ним работать, как его представлять решать мне и вам. Я просто предложил вам то, что дали мне в этой задаче. Я не против альтернативного представления графа. Но что сложного в таком представлении, я не знаю.

Если вам до сих пор что-то не понятно - скажите, я попытаюсь объяснить, иначе или предложите свое решение на любом удобном вам представлении графа или хватит уже жаловаться на мою постановку задачи. Я честно не думал что меня сложно будет понять

с максимальным количеством _подходящих_ рёбер

Осталось выяснить, что такое подходящие рёбра, и дело в шляпе!

ну я использую 2 критерия - есть связь, нет связи.

Это непонятно.

Возьму на себя смелость и ещё раз попробую угадать, в чём задача.

Соответствие между вершинами фиксировано, окей. Нужно найти такое соответствие между коннекторами, чтобы множество ПАР рёбер (одно из первого графа, другое из второго), не нарушающее выбранное соответствие между коннекторами, было максимальным.

Пара рёбер «a(i)---(j)b» и a(k)---(l)b не нарушает соответствие между коннекторами, если коннектор (i) из первого графа поставлен в соответствие коннектору (k) из второго, а коннектор (j) из первого графа поставлен в соответствие коннектору (l) из второго. При этом каждый коннектор может быть поставлен в соответствие не более чем одному коннектору из другого графа.

Верно?

Ты по-умолчанию полагашь, что остальные люди знают то же самое, что уже знаешь ты. В том числе и по задаче (описание данных, семантика, ограничения, инварианты/етц).

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

Дополню, помимо представления задачу то же нужно формулировать.

Я честно не думал что меня сложно будет понять

Да у тебя походу это вообще первый контакт с землянами.

омг, вы ветку то читали?

А вообще бесит, что людям не представить что-то немного отличающееся, от стандартной теории. Стоило упомянуть графы и «капец» - используй только то, что есть в каждой книжке по графам для пятиклассников. Ну хрен с ними с графами! Что, не представить электрическую схему в удобной вам форме? абстрагируйтесь от «стадартных» графов, хотябы в этой задаче

Я пытался, честно. Но ладно. Попробую еще разок.

Я пытался, честно. Но ладно. Попробую еще разок.

Я сфэйлился. Непонятно, что значит «сопоставить»? В каком плане идет сопоставление?

Не знаю как ТС, но за себя скажу: сопоставление = отображение (mapping). Подразумевается, что оно может быть неполным.

ну так если вершины промаркированы, то просто берем полностью изолированный подграф (без ребер, который) и добавляем по ребру, если такие присутствуют и в графе G1, и в графе G2.

Но мое чутье подсказывает, что ТС не этого хочет.

ну я использую 2 критерия - есть связь, нет связи.

Это непонятно.

смотрите,

'a'1---2'b'
  \
   2---20'c'

'a'11---12'b'
  \
   11---32'c'

• если на графе 'A' есть связь 'a'1 --- 2'b', а на 'B' - 'a'11 --- 12'b', то соблюдается первый критерий.
• если на 'A' также есть связь 'a'2 --- 20'c', а на 'B' - 'a'11 --- 32'c', то выполняется второй критерий(нет такой связи) и можно сказать, что эта связь неправильная, хотя, если более подходящей нет,а её протсо нет, нужно сопостовлять её

а здесь есть:

'a'1---2'b'
  \
   2---20'c'

'a'11---12'b'
 |\
 | 11---32'c'
  \       /
   123---15

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

вот это вроде совсем не так.

Но в общем мой алгоритм работает именно со множеством соответствий коннекторов и проверяет каждую пару на 2 выше приведённых критерия.

Пример

'a'1---2'b'
  \
   2---20'c'

'a'11---12'b'
 |\
 | 11---32'c'
  \       /
   123---15

я приведу свой алгоритм, может в нём более четко сформулированны идея, чем я это сделал

'a'1---2'b'
  \
   2---20'c'

'a'11---12'b'
 |\
 | 11---32'c'
  \       /
   123---15

• Берём соответствие 'a'~'a' (*1*)
• Составляем таблицу связей T1 для первого графа:

1---[b]
2---[c]

• для второго T2

11---[b]
11---[c]
123---[c]

• Составляем таблицу осутствия связей T1' и T2' для первого и второго графов соответственно

1-x-[c]
2-x-[b]

11-x-[]
123-x-[b]

Проверяем по критериям все возможные сочетания коннекторов

+-----------+----------+----------+
| conformity| T1       | T2       |
+-----------+----------+----------+
|(1~11)     |+         |          |
+-----------+----------+----------+
|(1~123)    |          |          |
+-----------+----------+----------+
|(2~11)     |+         |          |
+-----------+----------+----------+
|(2~123)    |+         |+         |
+-----------+----------+----------+

Следовательно,

• связь 'a'1---2'b' лучше всего покрывает 'a'11---'12'b, т.к. +
• связь 'a'2---20'c' лучше всего покрывает 'a'123---'15'b, т.к. ++

• Берём соответствия b~b и c~c и делаем тоже самое, т.е. в пункт 1.

если такие

отлично, только что вы подразумеваете под «такие»

забыл сказать, на каждом шаге увеличивается вес более «подходящих»(по 2м криетриям) связей, таким образом в конце концов мы получи связи с большими весами. Причём связь 'a'i---j'b' эквивалента, т.е. мы инкрементируем именно её вес, связи b'j'---i'a'

Но в общем мой алгоритм работает именно со множеством соответствий коннекторов и проверяет каждую пару на 2 выше приведённых критерия.

Во-вторых, задам вопрос прямо: может ли алгоритм рассмотривать комбинацию пар (1,11) и (2,11) (в рамках одного множества соответствий коннекторов) или это запрещено?

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

если такие

отлично, только что вы подразумеваете под «такие»

если в графах G1 и G2 существует ребро (a,b), то добавляем его в граф G', состоящий изначально из изолированных вершин.

На вопрос «или-или» ответ «да» трактуется неоднозначно :) Разрешено комбинировать (1-11) и (2-11) или запрещено?

в очередной раз включил телепатию:

тебе MST надо что ли? (Minimal Spanning Tree)

ок, мы получим граф, содержащий общие рёбра, к примеру из

'a'1---2'b'
  \
   2---20'c'

'a'11---12'b'
 |\
 | 11---32'c'
  \       /
   123---15

'a'1*11---2*12'b'
 |\
 | 1*11---32*20'c'
  \       /
 2*123---20*15

нет

ты имеешь в виду в обшем ответе? Да, если они имеют одинаковый вес, можно