4
$\begingroup$

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow self-edges.

I have done some research on this, and I found the tool "nauty" which can generate graphs up to isomorphism, but it can't generate directed multigraphs and it can't generate directed graphs with self-loops. Perhaps the nauty library could be used to solve this problem. It can efficiently calculate generators for the automorphism group of a graph. Is there a way that those could be used to generate directed multigraphs?

I can think of a way to generate undirected multigraphs, but it might not help with this problem.

This problem could be solved by solving graph isomorphism an exponential number of times, but that's not feasible. I am looking for an algorithm for which the main growth factor is due to the number of graphs generated. I have not found an algorithm that can count the number of these graphs.

Improve this question
$\endgroup$
1
  • $\begingroup$ Related: see the papers cited at cs.stackexchange.com/q/29552/755 for research on how to enumerate non-isomorphic graphs; perhaps they can be modified to address your problem (directed multigraphs, with self-edges allowed)? $\endgroup$
    – D.W. ♦
    Commented Mar 6, 2017 at 3:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.