Opened 9 years ago

Closed 9 years ago

#7246 closed enhancement (fixed)

digraph.DeBruijn in graph_generators

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.2
Component: graph theory Keywords:
Cc: Merged in: sage-4.2.alpha1
Authors: Nathann Cohen Reviewers: Sebastien Labbe
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (2)

trac_7246.patch (2.9 KB) - added by ncohen 9 years ago.
trac_7246_review.patch (1.9 KB) - added by slabbe 9 years ago.

Download all attachments as: .zip

Change History (6)

Changed 9 years ago by ncohen

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by slabbe

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?

Changed 9 years ago by slabbe

comment:3 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

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

comment:4 Changed 9 years ago by mhansen

  • Authors set to Nathann Cohen
  • Merged in set to sage-4.2.alpha1
  • Resolution set to fixed
  • Reviewers set to Sebastien Labbe
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.