0
$\begingroup$

I'm actually writing a piece of code to try and test various conjectures on directed graphs, and when possible, find a minimal counter example to the conjecture being tested.

For that, I need to enumerate all possible simple directed graphs D=(V,A) (simple in the sense that multiple arcs, 2-cycles, or (u, u) arcs are not allowed).

I have for the moment a naive method, which consists in building all the possible functions

F: S --> {-1, 0, 1} where S = {(u, v) in VxV such that u > v} and V is the vertex set.

Then, F(u, v) = 1 <==> (u, v) in A, F(u, v) = -1 <==> (v, u) in A, and F(u, v) = 0 <==> (u, v) not in A and (v, u) not in A.

There are 3^(n(n-1)/2) (n the number of vertices) such functions, and I'm pretty sure that this is a much bigger number than the actual number of unlabeled simple directed graphs.

This does enumerate all labeled directed graphs, but it's an overkill because I do not care about labels, so ultimately I generate way too many graphs, and test conjectures several times on graphs that are similar (their only difference is the vertex labels).

My question is: is there a simple algorithm to enumerate unlabeled simple directed graphs ?

And since I'm confident such an algorithm exists, a quick description would be very welcome.

$\endgroup$
  • $\begingroup$ Most graphs have no automorphisms. So the total number of digraphs, even up to automorphism, is still roughly $3^{\binom{n}{2}}$. $\endgroup$ – Yuval Filmus Oct 30 '19 at 15:17
  • $\begingroup$ Thanks, I had seen the link about undirected graphs, I just wasn't sure the same thing would be valid for simple directed ones too. I'll stick to my actual implementation, which is more than fine for what I need. $\endgroup$ – m.raynal Oct 31 '19 at 12:30