Opened 8 years ago

Closed 8 years ago

#12626 closed enhancement (fixed)

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

Reported by: dcoudert Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-5.0
Component: graph theory Keywords:
Cc: ncohen Merged in: sage-5.0.beta8
Authors: David Coudert Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by dcoudert)

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

Attachments (1)

trac_12626_kautz_digraph_generator.patch (14.2 KB) - added by dcoudert 8 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 8 years ago by dcoudert

  • Authors set to David Coudert
  • Cc ncohen added
  • Description modified (diff)
  • Status changed from new to needs_review

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

comment:2 Changed 8 years ago by dcoudert

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

comment:3 Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

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: 


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


comment:4 Changed 8 years ago by dcoudert

  • Status changed from needs_work to needs_review

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 !

comment:5 Changed 8 years ago by ncohen

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:]

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.


produced, that is the cardinality [...]

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


Changed 8 years ago by dcoudert

comment:6 Changed 8 years ago by dcoudert


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 or my PhD thesis for more details) and it is not working for the Kautz graph...

Thank you again,


comment:7 Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

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


comment:8 Changed 8 years ago by ncohen

  • Reviewers set to Nathann Cohen

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


comment:9 Changed 8 years ago by dcoudert

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


comment:10 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.