De Bruijn graphs.
De Bruijn graphs are labeled graphs representing the overlap of strings.
- Integer scalar, the size of the alphabet. See details below.
- Integer scalar, the length of the labels. See details below.
A de Bruijn graph represents relationships between strings. An alphabet
m letters are used and strings of length
n are considered.
A vertex corresponds to every possible string and there is a directed edge
v to vertex
w if the string of
be transformed into the string of
w by removing its first letter
and appending a letter to it.
Please note that the graph will have
m to the power
vertices and even more edges, so probably you don't want to supply too
big numbers for
De Bruijn graphs have some interesting properties, please see another source,
eg. Wikipedia for details.
- A graph object.
De Bruijn graph
# de Bruijn graphs can be created recursively by line graphs as well g <- graph.de.bruijn(2,1) graph.de.bruijn(2,2) line.graph(g)