Revision history [back]

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:

• https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/
• https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/

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).

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.

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:

• https://ask.sagemath.org/question/24199/why-the-function-graphs-cant-generate-graphs/
• https://ask.sagemath.org/question/33384/using-a-lambda-expression-in-digraphs-fails-for-lengsinks/

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.