Хорошая библиотека для проверки, существует ли несовершеннолетний в графе?

18

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

graph-algorithms implementation graph-minor Hooman
источник
4
Хотел бы я ! это будет отличная статья или набор документов ALENEX / SEA.
Суреш Венкат

Ответы:

5

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

Чад Brewbaker
источник
Да, но nauty (насколько я знаю) не предоставляет каких-либо методов для поиска несовершеннолетних . Кроме того, учитывая, что вопрос был просто о наличии / отсутствии определенного набора несовершеннолетних, я не вижу, как построение хэш-таблицы из всех экземпляров помогает решить эту начальную проблему ...
Джошуа Грохоу
Венди Мирволд и Брендан Маккей проводят множество небольших исследований с NAUTY в качестве вспомогательной библиотеки. DFS при удалении / объединении до тех пор, пока вы не дойдете до нужного количества вершин, а затем запросите предварительно вычисленное множество. То, как вы будете работать с DFS, будет зависеть от того, какой тип несовершеннолетнего вы ищете.
Чад Brewbaker
Интересный! Вы должны сделать эту часть ответа. Кроме того, вы можете дать ссылку? Я не мог найти это.
Джошуа Грохоу