De Bruijn graphs are labeled graphs representing the overlap of strings.
Arguments
- m
Integer scalar, the size of the alphabet. See details below.
- n
Integer scalar, the length of the labels. See details below.
- ...
Passed to
make_de_bruijn_graph()
.
Details
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, e.g. Wikipedia for details.
Author
Gabor Csardi csardi.gabor@gmail.com
Examples
# de Bruijn graphs can be created recursively by line graphs as well
g <- make_de_bruijn_graph(2, 1)
make_de_bruijn_graph(2, 2)
#> IGRAPH 3aa8c6c D--- 4 8 -- De-Bruijn graph 2-2
#> + attr: name (g/c), m (g/n), n (g/n)
#> + edges from 3aa8c6c:
#> [1] 1->1 1->2 2->3 2->4 3->1 3->2 4->3 4->4
make_line_graph(g)
#> IGRAPH e72aedf D--- 4 8 -- Line graph
#> + attr: name (g/c)
#> + edges from e72aedf:
#> [1] 1->1 3->1 1->2 3->2 2->3 4->3 2->4 4->4