Category Archives: Databases

Iso-class representatives for all weakly-connected digraphs with up to 10 arcs

Have you ever wanted to test some hypothesis or constructions involving (weakly) connected directed graphs? In that case, it can be quite resource consuming to generate canonically labelled representatives as you go, for instance, in sage. Furthermore, there is a good chance that you are going to need the representatives again and again. After having spent my fair share of computing power to generate these representatives, I went hunting for an online database where I could just download them โ€” but I did not find any. So I created such a database myself using sage, possibly saving you around 12 hours of computations (see: github.com/immanuel-albrecht/databases).

The SQL query

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  

yields:

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

Now, let’s compare this to the corresponding OEIS-entry:

1, 4, 12, 53, 237, 1306, 7537, 47913, 322253, 2297874, ...

So it appears that the canonical labeling implemented in sage is working as expected ๐Ÿ™‚