Opened 10 years ago
Closed 10 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)
Change History (6)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
Changed 10 years ago by
comment:3 Changed 10 years ago by
- 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 10 years ago by
- 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.
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?