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

SELECT arcs, COUNT() AS nbr_of_digraphs FROM (SELECT ID, COUNT() AS arcs FROM weakly_connected  AS tmp1  GROUP BY ID) AS tmp2 GROUP BY arcs  

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 🙂