I'm trying to count all of the directed graphs on n vertices which have fixed in/out degree, up to isomorphism. I would like to allow loops, though not multiple edges. I can't figure out how to tell the digraphs iterrator to include the ones with loops, though i see this is an option in the graphs iterator. I would appreciate suggestions to get around this/explanations why it is not an option.
Let me first answer your last question: this is not an option because nobody implemented it. Sage is a free-software and it seems that the developers who worked on graphs prefered to work on graphs than digraphs. There is no mathematical reason. If you have time to work on digraphs, please to not hesitate to contribute your code to Sage.
Regarding your first question, let me first notice that being of fixed degree is not an hereditary property (not stable if you remove an edge or a vertex), while the digraphs generator . See the following two posts for more explanations and hints:
So, if d is the degree you want to select, let me suggest to generate all digraph (up to isomorphism) with in/out degree at most d and then filter the ones that have uniform in/out degree d.
Now, regarding loops, it is clear that if you attach loops to non-isomorphic digraphs, the resulting looped digraphs will remain non-isomorphic. Hence, for each digraph (up to isomorphism) worked separately, you have to see how to attach loops by being careful that some different choices of vertices to attach loop on may lead to isomorphic looped digraph. Such cases appear when the digraph has non-trivial automorphisms, and knowing the automorphism group of the graph (and its action on the graph) is enough to determine the classes of loop-attachment. For this, when G is a digraph, you can do:
sage: G.automorphism_group()
However, since your use case has to deal with the degree constraint and you already had to filter digraphs with degree at most d (not exactly d as explained above), you can rely on this generator, and filter both conditions simultaneously. The trick is to filter, among the digraphs of degree at most d, the digraphs whose in/out degrees are either (d,d) or (d-1,d-1), and then to attach a loop to each vertex with degrees (d-1,d-1). The disymmetry d vs d-1 is such that there is no need to deal with the automorphism groups of the digraphs.
I hope there is enough information to find your way, do not hesitate to ask questions and to post your code once it is written.
Asked: 2016-11-25 10:30:55 +0100
Seen: 623 times
Last updated: Nov 25 '16
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.