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.

$\endgroup$
  • $\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. Mar 6 '17 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.