| graph.de.bruijn {igraph} | R Documentation |
De Bruijn graphs are labeled graphs representing the overlap of strings.
graph.de.bruijn(m,n)
m |
Integer scalar, the size of the alphabet. See details below. |
n |
Integer scalar, the length of the labels. See details below. |
A de Bruijn graph represents relationships between strings. An alphabet
of m letters are used and strings of length n are considered.
A vertex corresponds to every possible string and there is a directed edge
from vertex v to vertex w if the string of v can
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 n
vertices and even more edges, so probably you don't want to supply too
big numbers for m and n.
De Bruijn graphs have some interesting properties, please see another source, eg. Wikipedia for details.
A graph object.
Gabor Csardi <csardi@rmki.kfki.hu>
# 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)