Здравствуйте, Arsen.Shnurkov, Вы писали:

AS>Мне же нужен не простой граф, а граф с вершинами разных типов (видимо это называется "окрашенные вершины").
AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).

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

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

Если задача проверки — для одного и того же графа много разных цепочек — то следует предварительно минимизировать этот автомат.


А что за задача поиска подграфа?