Dobra biblioteka do testowania, czy nieletni istnieje na wykresie?

Chciałbym wiedzieć, czy są jakieś bezpłatne biblioteki wykresów do testowania, czy na danym wykresie istnieje określony zestaw nieletnich?

graph-algorithms implementation graph-minor Hooman
źródło

Chciałbym ! byłby to doskonały papier ALENEX / SEA lub zestaw papierów.

Suresh Venkat

Odpowiedzi:

NAUTY może być używany jako biblioteka, która pomoże ci zbudować tablicę haszującą dla całego zestawu mniejszych grafów dla małych . Kluczem byłaby kanoniczna forma podana przez NAUTY, a wartością byłaby konkatenacja w uporządkowanej kolejności kanonicznych form jej bezpośrednich nieletnich. $n$

Chad Brewbaker
źródło

Tak, ale nauty nie zapewnia (o ile mi wiadomo) żadnych metod znalezienia nieletnich . Ponadto, biorąc pod uwagę, że pytanie dotyczyło jedynie obecności / nieobecności określonego zestawu nieletnich, nie rozumiem, w jaki sposób zbudowanie tablicy hasht ze wszystkich przypadków pomaga rozwiązać ten początkowy problem ...

Joshua Grochow

Wendy Myrvold i Brendan McKay przeprowadzają wiele drobnych badań z NAUTY jako biblioteką pomocniczą. DFS podczas usuwania / łączenia, aż dojdzie do możliwej do wyliczenia liczby wierzchołków, a następnie przeprowadź zapytanie o wstępnie obliczony zestaw. To, jak zrobisz DFS, będzie zależeć od tego, jakiego rodzaju małoletniego szukasz.

Chad Brewbaker

Ciekawy! Powinieneś zrobić tę część odpowiedzi. Czy możesz również podać referencje? Nie mogłem tego znaleźć.

Joshua Grochow