Kautz, Imase and Itoh, and Generalized de Bruijn digraph generators

[dcoudert]

This patch implements generators for Kautz digraphs, Imase and Itoh digraphs, and Generalized de Bruijn digraphs.

CC: @nathanncohen

Component: graph theory

Author: David Coudert

Reviewer: Nathann Cohen

Merged: sage-5.0.beta8

Issue created by migration from https://trac.sagemath.org/ticket/12626

[dcoudert]

Author: David Coudert

[dcoudert]

comment:1

The implementation of the Kautz generator can certainly be done in a more elegant way, but I don't know how.

[dcoudert]

comment:2

Update of the patch removing the documentation warnings caused by duplicated references and an inline literal that was starting at a line and ending at the next one.

It should now pass all tests without warnings...

[nathanncohen]

comment:3

Helloooooo David !!!

Looks like there is something wrong with your doctests ! You forgot to add many "::" and so the doctests you add do not appear in the documentation (and probably are not tested when you run "sage -t")

Some other things : we try to keep the "first line" of the documentation of each function "short and descriptive". Something like "its meaning in at most one line". Something like what you find in "RandomDirectedGNR" or in "DeBruijn". When it requires some details, they are given immediately after, though.

In the documentation you define the "degree d", but "degree" appears in the formulas, like in "v \equiv -u*degree-a-1 \mod{n}"

I noticed that you added a link toward a Wikipedia page... Did you see this ":wikipedia:" somewhere already ? During the last Sage Combinat days Florent Hivert actually added such a thing in Sage ! It is patch #12490. As written, this link does not display correctly in the doc, but since #12490 has been merged you can replace

See also :wikipedia: http://en.wikipedia.org/wiki/Kautz_graph 

by

See also the :wikipedia:`Wikipedia article on Kautz Graphs <Kautz_graph>`

Note that the argument is not a full link, but only the article's name :-)

Nathann

[dcoudert]

comment:4

I have addressed all points and I can see all doctests in the documentation.
The wikipedia link is also working.

Should be better now.

Thanks Nathann !

[nathanncohen]

comment:5

Helloooo David !!!

Well, I only have two unimportant things to bring up, and a question :

• Your "TESTS ::" should become "TESTS :" on two occurrences. There should only be a "::" before some Sage code, not before text !
• An integer equals to the diameter --> equal

I also spent some time playing with the code of the Kautz constructor. I have to admit I am not a big fan of doing all the computations through words, if you end up casting them to strings in the end. I don't think it would be a good idea to keep words in the graph either, as then the vertices would appear as "word: 1" instead of '1', hence it is not a good idea either. If you only need the is_suffix method you can just use string methods :

sage: a = "123456789"
sage: a[1:]
'23456789'

This would mean that all of your symbols have a 'width' of 1, though. Hence, "Bb" could not be a symbol as in your examples.

The other thing is that as such, it is not possible to "decompose" a vertex of your graph. Vertices are strings of symbols split by commas, but you have no idea what the "first symbol of the word" is. The answer to that would be to use tuples ("Bb", '1') to encode the vertices, but of course they would be longer.

All this to say that I do not know of any "good solution" to the problem. I'm just bringing this up for you to decide, after all you know better than I do what these graphs can be used for :-)

Oh, and.. I would have changed

produced, and also to the cardinality minus one of the alphabet to use.

by

produced, that is the cardinality [...]

to make clearer that it is an equivalent definition. That again is up to you !

Nathann

[dcoudert]

Attachment: trac_12626_kautz_digraph_generator.patch.gz

[dcoudert]

comment:6

Nathann,

I have done all corrections.

Concerning implementation choices for the Kautz digraph generator. I tried to be consistent with existing implementation of the DeBruijn digraph generator. I also used ideas from the ButterflyGraph generator.

So we have the same behavior:

sage: K = digraphs.Kautz(['aA','bB',1],2)
sage: K.edges()
[('1,aA', 'aA,1', '1'), ('1,aA', 'aA,bB', 'bB'), ('1,bB', 'bB,1', '1'), ('1,bB', 'bB,aA', 'aA'), ('aA,1', '1,aA', 'aA'), ('aA,1', '1,bB', 'bB'), ('aA,bB', 'bB,1', '1'), ('aA,bB', 'bB,aA', 'aA'), ('bB,1', '1,aA', 'aA'), ('bB,1', '1,bB', 'bB'), ('bB,aA', 'aA,1', '1'), ('bB,aA', 'aA,bB', 'bB')]
sage: B = digraphs.DeBruijn(['aA','bB',1],2)
sage: B.edges()
[('1,aA', 'aA,1', '1'), ('1,aA', 'aA,aA', 'aA'), ('1,aA', 'aA,bB', 'bB'), ('1,bB', 'bB,1', '1'), ('1,bB', 'bB,aA', 'aA'), ('1,bB', 'bB,bB', 'bB'), ('11', '1,aA', 'aA'), ('11', '1,bB', 'bB'), ('11', '11', '1'), ('aA,1', '1,aA', 'aA'), ('aA,1', '1,bB', 'bB'), ('aA,1', '11', '1'), ('aA,aA', 'aA,1', '1'), ('aA,aA', 'aA,aA', 'aA'), ('aA,aA', 'aA,bB', 'bB'), ('aA,bB', 'bB,1', '1'), ('aA,bB', 'bB,aA', 'aA'), ('aA,bB', 'bB,bB', 'bB'), ('bB,1', '1,aA', 'aA'), ('bB,1', '1,bB', 'bB'), ('bB,1', '11', '1'), ('bB,aA', 'aA,1', '1'), ('bB,aA', 'aA,aA', 'aA'), ('bB,aA', 'aA,bB', 'bB'), ('bB,bB', 'bB,1', '1'), ('bB,bB', 'bB,aA', 'aA'), ('bB,bB', 'bB,bB', 'bB')]
sage: K = digraphs.Kautz(['a','b',1],2)
sage: K.edges()
[('1a', 'a1', '1'), ('1a', 'ab', 'b'), ('1b', 'b1', '1'), ('1b', 'ba', 'a'), ('a1', '1a', 'a'), ('a1', '1b', 'b'), ('ab', 'b1', '1'), ('ab', 'ba', 'a'), ('b1', '1a', 'a'), ('b1', '1b', 'b'), ('ba', 'a1', '1'), ('ba', 'ab', 'b')]
sage: B = digraphs.DeBruijn(['a','b',1],2)
sage: B.edges()
[('11', '11', '1'), ('11', '1a', 'a'), ('11', '1b', 'b'), ('1a', 'a1', '1'), ('1a', 'aa', 'a'), ('1a', 'ab', 'b'), ('1b', 'b1', '1'), ('1b', 'ba', 'a'), ('1b', 'bb', 'b'), ('a1', '11', '1'), ('a1', '1a', 'a'), ('a1', '1b', 'b'), ('aa', 'a1', '1'), ('aa', 'aa', 'a'), ('aa', 'ab', 'b'), ('ab', 'b1', '1'), ('ab', 'ba', 'a'), ('ab', 'bb', 'b'), ('b1', '11', '1'), ('b1', '1a', 'a'), ('b1', '1b', 'b'), ('ba', 'a1', '1'), ('ba', 'aa', 'a'), ('ba', 'ab', 'b'), ('bb', 'b1', '1'), ('bb', 'ba', 'a'), ('bb', 'bb', 'b')]

To be even more consistent, I have now modified the DeBruijn Generator to add the option of using integer vertex labels. I have also corrected the wikipedia link of the documentation of the DeBruijn generator.

sage: B = digraphs.DeBruijn(['a','b',1],2,vertices = 'rr')
sage: B.edges(labels=None)
[(0, 0), (0, 1), (0, 2), (1, 3), (1, 4), (1, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (4, 3), (4, 4), (4, 5), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (7, 3), (7, 4), (7, 5), (8, 6), (8, 7), (8, 8)]
sage: B = digraphs.DeBruijn(3,2,vertices = 'blop')
sage: B.edges(labels=None)
[(0, 0), (0, 1), (0, 2), (1, 3), (1, 4), (1, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (4, 3), (4, 4), (4, 5), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (7, 3), (7, 4), (7, 5), (8, 6), (8, 7), (8, 8)]

I agree that this implementation is not perfect, but it has the merit of being consistent with previous implementation choices for the de Bruijn generator. Since I don't how this generator is used, I prefer to let it as it is. Of course, most of the users will use either a normal alphabet with simple symbols, or the integer version.

In fact, to be more general, we should be able to provide permutation functions (on the alphabet, and on the shifting) to the deBruijn generator, but this is another story (see http://dx.doi.org/10.1002/net.10043 or my PhD thesis for more details) and it is not working for the Kautz graph...

Thank you again,

David.

[nathanncohen]

comment:7

Got it ! Anyway one can still use "split" to find the decomposition back, or remove all commas to deal with words...

Nathann

[nathanncohen]

Reviewer: Nathann Cohen

[nathanncohen]

comment:8

And a good news : patch #12224 should be available at some point, which according to Vincent will change the default display of Words from "Word: aaabbb" to "aaabbb". So from this point we will be able to use graphs defined on Words, and so to update those methods and the deBuijn graph too :-)

Nathann

[dcoudert]

comment:9

That would be nice and ease the implementation of various algorithms on the deBruijn/Kautz digraphs: paths computation, ...

D.

[jdemeyer]

Merged: sage-5.0.beta8