#12626: Kautz, Imase and Itoh, and Generalized de Bruijn digraph generators
----------------------------+-----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: David Coudert
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Comment(by dcoudert):
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12626#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
