I’m trying to generate all directed multigraphs with exactly n edges and no self-loops.
Currently, my approach is to use the nauty package:
geng -> multig -> direg
However, the issue is that direg only supports simple graphs, not multigraphs.
I wonder if there’s a way to achieve this using IGraph in Mathematica instead.
Can you give a small example? For example n=3 vertices and m=2 edges would give:
Is this correct?
If so, I think multig would not help, as it cannot reduce the edge count of the underlying simple graph.
To answer your question, unfortunately I do not think IGraph/M currently has the functionality to help here. It can test for isomorphism between multigraphs, but this is based on VF2 and therefore it is slow and only supports pairwise tests. It does not support canonicalization. Thus only tiny graphs could be handled.
What is the vertex and edge count of the graphs you are looking to enumerate?
Hi, thanks for the help.
That’s correct, except I forgot to mention that the multigraphs should have no isolated vertices.
The number of vertices can vary and is not fixed, as long as the total number of edges is exactly m.
My goal is to generate all directed multigraphs with no self-loops and no isolated vertices, and exactly m edges, where m can range from 1 to 30, for example.
I want to generate all such graphs (it’s okay if isomorphic ones are included).
Do you happen to know of any workaround or other tools that might help with this?
