I would like to be able to quickly generate (all) non-isomorphic isographs (that is, digraphs where each node has the same indegree and outdegree - also called "balanced networks" in the distributed sensors literature) and/or Eulerian digraphs (the same, but imposing connectivity - weak or strong does not change) with given number n of vertices.
Notice that this is similar to but distinct:
- from finding all non-isomorph circuits in a complete graph (since I want each edge to be traversed at most once in each direction), and
- from finding all non-isomorph Eulerian circuits in a given graph, and applying the procedure to all non-isomorph graphs (since I want to allow the same edge to be traversed once in each direction).
I am currently using nauty: I run geng and feed its output to directg, then filter the output keeping only balanced digraphs.
This works, but I think it is really overkill: already for small values of n, the number of existing digraphs is much larger than the number of existing isographs and the ratio between the two sequences grows for larger n; that is, most of the CPU cycles used by geng and directg are wasted for me.
I did search a bit the available literature, but I only found papers on enumerating, rather than generating, such graphs (i.e. "Isographs and Oriented Isographs", a 1972 paper by Sridharan and Parthasarathy). I also took a look at the software suggested by this answer, but found nothing applying to my case. Notice I'm really not expert, so I may have missed a lot. But I do feel that algorithms for generating (and possibly identifying?) non-isomorphic isographs should be completely different from algorithms for generic (di)graphs: namely, exploiting the possibility of decomposing the digraph in circuits.
So my question is:
- can I find anywhere an efficient algorithm for generating isographs and/or Eulerian digraphs?
- can I find anywhere an efficient algorithm for detecting if two isographs/Eulerian digraphs are isomorph?
- can I find anywhere the above (in particular point 1) already implemented in available software?
If the answer is "no", I think I will try to write one - to my naive eyes, point 1. does not look that hard (while point 2. does). But it is really probable that my naive eyes missed some already existing solution...
First of all, for what order (number of vertices) would you like to generate this graphs? Also, why do you need to generate all of them? Are you testing a specific conjecture? If so which?
The problem is that given that the number of such graphs grows exponentially it may well be that your attempt at coding an efficient generating algorithm would still not yield anything more than the things you are now able to obtain using the current(non-optimal) method and would only give you what you already have in a faster way.
What I would suggest you try is check the DEGPRUNE directive in nauts's source code for directg. This may help you prune the search tree substantially.
As for question 1. I may be wrong but I believe there is currently no such software available.