Обычно граф определяется как
упорядоченная пара из двух множеств — множества вершин этого графа (они же узлы) и множества связей этого графа (они же рёбра, дуги = ориентированные рёбра).
Г := < В , Р >
Мне же нужен не простой граф, а граф с вершинами разных типов (видимо это называется "окрашенные вершины").
И не только граф, но и алгоритм поиска в направленном графе
подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
Вы скажете — сядь и подумай. Переборами, переборами.
Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Мне в таком решении не нравятся два момента:
1) при добавлении новой вершины (со связями) в граф надо будет всё пересматривать, а это излишне трудоёмко.
2) вообще полный перебор выглядит излишне трудоёмким. Есть же вдохновляющий алгоритм Кнута-Морриса-Пратта, в котором количество действий снижается (у них там, правда, не граф и цепочка, а просто две цепочки).
Вы скажете — надо тебе инкрементально, прикладывай цепочку разными узлами к нововставленной в граф вершине и проверяй наличие обоих хвостов цепочки в графе. Но и тут, мне кажется, можно сэкономить, если граф предварительно дополнительно разметить.
Как нужный мне алгоритм называется и как его искать?
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>И не только граф, но и алгоритм поиска в направленном графе AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки). AS>Как нужный мне алгоритм называется и как его искать?
Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь. В процессе складываешь в очередь только те вершины, которые помечены так же, как очередная вершина на пути-паттерне (то есть на том же расстоянии от начала).
AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").
Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода, чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).
AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскрашиваются, и повторный заход можно задетектить — встретим не белую вершину.
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>Мне же нужен не простой граф, а граф с вершинами разных типов (видимо это называется "окрашенные вершины"). AS>И не только граф, но и алгоритм поиска в направленном графе AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
В частном случае это всего-навсего проверка вхождения цепочки в язык, заданный автоматной (регулярной) грамматикой.
Добавь к своему графу две фиктивные вершины — старт и финиш — и соедини их со всеми вершинами (ибо, цепочка может начаться на любой из вершин твоего графа, и закончиться тоже на любой).
Теперь твой граф являет собой конечный автомат, который умеет парсить цепочки.
Если задача проверки — для одного и того же графа много разных цепочек — то следует предварительно минимизировать этот автомат.
Здравствуйте, Arsen.Shnurkov, Вы писали:
К>> твой граф являет собой конечный автомат AS>И как мне это поможет снизить количество операций?
Мы свели задачу к хорошо известной.
Единственно, что если нужно найти не просто факт "цепочка входит", а конкретное место, — то придётся немножко поколдовать.
Вместо автомата-акцептора возьмём недетерминированный автомат-транслятор Мура (каждой вершине соответствует выход "мы посетили эту вершину").
Результат работы — трансляция цепочки раскрасок в цепочку (в множество цепочек) номеров вершин.
К>> что за задача поиска подграфа?
AS>нискажу, но в качестве примера думаю, что подойдёт поиск куска молекулы в целой молекуле.
Если это обычные молекулы, то наверняка можно подойти укрупнённо — искать не по отдельным атомам, а по группам: аминокислоты, сульфидные мостики (если речь о белках), нуклеотиды и даже их триплеты (если речь идёт о ДНК-РНК), либо циклы, гетероциклы, углеводородные цепочки и т.п.
Перекуём баги на фичи!
