Eine gute Bibliothek zum Testen, ob Minderjährige in einer Grafik vorhanden sind?

18

Ich würde gerne wissen, ob es freie Grafikbibliotheken gibt, um zu testen, ob in einer bestimmten Grafik eine bestimmte Menge von Minderjährigen vorhanden ist.

graph-algorithms implementation graph-minor Hooman
quelle
4
Ich wünsche ! das wäre ein ausgezeichnetes ALENEX / SEA-Papier oder ein Satz von Papieren.
Suresh Venkat

Antworten:

5

NAUTY kann als Bibliothek verwendet werden, um Ihnen zu helfen, eine Hash-Tabelle für den gesamten Satz von Graph Minors für small erstellen . Der Schlüssel wäre die von NAUTY gegebene kanonische Form, und der Wert wäre eine Verkettung der kanonischen Formen seiner direkten Minderjährigen in sortierter Reihenfolge.n

Chad Brewbaker
quelle
Ja, aber nauty bietet (soweit ich weiß) überhaupt keine Methoden, um Minderjährige zu finden . Angesichts der Tatsache, dass es sich lediglich um die Anwesenheit / Abwesenheit einer bestimmten Gruppe von Minderjährigen handelte, kann ich nicht erkennen, wie das Erstellen einer Hashtabelle aus allen Instanzen zur Lösung dieses anfänglichen Problems beiträgt ...
Joshua Grochow
Wendy Myrvold und Brendan McKay recherchieren viel mit NAUTY als Support-Bibliothek. DFS bei Lösch- / Verknüpfungsvorgängen, bis Sie eine nachvollziehbare Anzahl von Scheitelpunkten erreicht haben, und fragen Sie dann das vorberechnete Poset ab. Wie Sie die DFS durchführen, hängt davon ab, nach welcher Art von Minderjährigem Sie suchen.
Chad Brewbaker
Interessant! Sie sollten diesen Teil der Antwort machen. Können Sie auch eine Referenz geben? Ich konnte es nicht finden.
Joshua Grochow