Suppose we have a simple digraph $G$ with $g$ vertices and $a$ arcs. How should one count all graphs in that isomorphism class (i.e., all graphs isomorphic to graph $G$).
Any pointers would be really appreciated.
Suppose we have a simple digraph $G$ with $g$ vertices and $a$ arcs. How should one count all graphs in that isomorphism class (i.e., all graphs isomorphic to graph $G$).
Any pointers would be really appreciated.
Are you looking for the number of labeled digraphs isomorphic to a given unlabeled one?
So really you are looking for the set of permutations of the labels which result in distinct labellings. E.g. for the directed claw $a\rightarrow b$, $a\rightarrow c$, $a\rightarrow d$, any permutation of the labels $b,c,d$ give the same labeled digraph, and any digraph with a different root of the claw with be nonisomorphic. In this example it seems that there are only 4 distinct labeled digraphs.
If this is the case, then this is equivalent to finding the order of the isomorphism group of graph. There is lots of research on both algorithms for this and its computational complexity (it's a subclass of graph isomorphism).
Practically, the go-to implementation (that is the implementation that you really should 'go to' for practical purposes) is nauty.