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.
