<p>I am interested in an algorithm that allows me to construct all inequivalent (non-isomorpic) digraphs of size n with self-loops allowed. For example, the output should look like this:
<img src="https://i.sstatic.net/qKA9K.png" alt="enter image description here"></p>

<p>Even though it is trivial to simply construct all such digraphs, I believe that the requirement that non-isomorphic graphs should appear only once makes the problem very difficult. Of course, we can always construct all of them and drop the duplicates but this approach is too slow. Ideally I would like an algorithm that just creates the inequivalent ones by construction.</p>

<p>Does such a thing exist? Any ideas or references would be most welcome.
Descriptions of the algorithm either in a diagrammatic form or in terms of adjacency matrices are equally acceptable. Thanks in advance!</p>

CC BY-SA 3.0
2014-01-16T10:42:57.120Z
Regarding your simple solution: keep in mind that checking for isomorphism between two graphs is not known to be solvable in polynomial time.
Kaveh
CC BY-SA 3.0
2014-01-16T14:18:55.000Z
http://cs.anu.edu.au/~bdm/nauty/
Nathann Cohen
CC BY-SA 3.0
2014-01-16T14:59:17.857Z
Traces is the next generation of McKay's software http://pallini.di.uniroma1.it/
Chad Brewbaker
<graph-theory><graph-algorithms>
Constructing all digraphs without repetitions
Heterotic
# Constructing all digraphs without repetitions

(Asked by: username_0 on 2014-01-16)

I am interested in an algorithm that allows me to construct all inequivalent (non-isomorpic) digraphs of size n with self-loops allowed. For example, the output should look like this:
![enter image description here](https://i.sstatic.net/qKA9K.png)

Even though it is trivial to simply construct all such digraphs, I believe that the requirement that non-isomorphic graphs should appear only once makes the problem very difficult. Of course, we can always construct all of them and drop the duplicates but this approach is too slow. Ideally I would like an algorithm that just creates the inequivalent ones by construction.

Does such a thing exist? Any ideas or references would be most welcome.
Descriptions of the algorithm either in a diagrammatic form or in terms of adjacency matrices are equally acceptable. Thanks in advance!

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Regarding your simple solution: keep in mind that checking for isomorphism between two graphs is not known to be solvable in polynomial time.  
> **username_2**: http://cs.anu.edu.au/~bdm/nauty/  
> **username_3**: Traces is the next generation of McKay's software http://pallini.di.uniroma1.it/  

---

## 0 answers

