digraph.DeBruijn in graph_generators

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

This patch adds the DeBruijn digraph to the ( still very short ) list of digraphs generators.

More information here : http://en.wikipedia.org/wiki/De_Bruijn_graph

I found no way to define automatically a layout for this graph. If you have an idea, do not hesitate to tell me :-)

Nathann

Component: graph theory

Author: Nathann Cohen

Reviewer: Sebastien Labbe

Merged: sage-4.2.alpha1

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Attachment: trac_7246.patch.gz

[seblabbe]

comment:2

Dear Nathann, I just reviewed your code and made some modifications (see patch). I mostly used some possibilities offered by the word code in sage (e.g. * instead of concatenation and Words(n,1) for words of length one). Tell me if you agree with those modifications.

The output when k=0 was broken (vertices of length one were appearing). Although it could not be supported (return an error), I think it may be defined using multiedges and hence the "Each vertex has exactly n incoming and n outgoing edges" statement stays true. The wiki page doesn't talk about k=0......

I am giving a positive review to your patch pending a solution for the case k=0. Can you review my patch?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:3

Attachment: trac_7246_review.patch.gz

I think your patch is perfect, including the case k=0... I did not think about empty words, though it can not hurt :-)

Positive review !

Nathann

[mwhansen]

Author: Nathann Cohen

[mwhansen]

Merged: sage-4.2.alpha1

[mwhansen]

Reviewer: Sebastien Labbe