Habt ihr auch schon einmal eine Hypothese oder Konstruktion, die sich um (schwach) zusammenhängende gerichtete Graphen dreht, testen wollen? In disem Fall stellt sich schnell heraus, dass es sehr ressourcenintensiv sein kann, kanonisch-gelabelte Repräsentanten on-the-fly zu erzeugen, z.B. mit sage. Außerdem ist die Wahrscheinlichkeit groß, dass diese Repräsentanten später immer wieder benötigt werden. Nachdem ich einige Rechenzeit in die Erzeugung von Repräsentanten gesteckt hatte, habe ich versucht, aus dem Internet eine Datenbank mit kanonisch-gelabelten gerichteten Graphen herunterzuladen — habe aber keine gefunden! Also habe ich mit sage selbst so eine Datenbank erstellt, die jedem um die 12 Stunden Rechenzeit sparen hilft (link: github.com/immanuel-albrecht/databases).
Die SQL-Anfrage
SELECTarcs
, COUNT() ASnbr_of_digraphs
FROM (SELECTID
, COUNT() ASarcs
FROMweakly_connected
AS tmp1 GROUP BYID
) AS tmp2 GROUP BYarcs
ergibt:
arcs nbr_of_digraphs 1 1 2 4 3 12 4 53 5 237 6 1,306 7 7,537 8 47,913 9 322,253 10 2,297,874
Ein Vergleich mit dem entsprechenden OEIS-Eintrag…
1, 4, 12, 53, 237, 1306, 7537, 47913, 322253, 2297874, ...
… ergibt, dass das kanonische Labeling in sage wohl korrekt implementiert wurde 🙂