Я хочу навести маленький граф на большой граф.Оба эти графика показаны ниже.Вершины с одинаковым цветом эквивалентны.
маленький граф (подлежит индукции) 
большой граф (меньший граф индуцируется)
Проблема в том, что ни одна из красных вершин на большом графе не имеет 4 соседей в качестве малого графа.Так что boost::vf2_subgraph_iso не сможет вызвать small на large.Но если индуцирующий алгоритм более терпим (максимальное сопоставление вместо сопоставления всех вершин), он может дать наиболее близкое совпадение.
С другой стороны, boost::mcgregor_common_subgraphs занимает действительно экспоненциально много времени для завершения.Другое последствие - применение алгоритма поиска максимального общего подграфа, два совершенно несовместимых графика - это потеря большого количества процессорного времени.Алгоритм Макгрегора основан на поиске клик.Таким образом, он начинается с 1 вершины подграфа a и прогрессирует в сторону больших подграфов.Для подграфа, содержащего более 10 вершин, недопустимо много времени, чтобы найти очевидное решение.
Итак, каково решение в этом сценарии?Есть ли более толерантный алгоритм для создания подграфа?