De Bruijn graphs

De Bruijn graphs are labeled graphs representing the overlap of strings.

Usage

make_de_bruijn_graph(m, n)

de_bruijn_graph(m, n)

Arguments

m

Integer scalar, the size of the alphabet. See details below.

n

Integer scalar, the length of the labels. See details below.

Value

A graph object.

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.

Related documentation in the C library

de_bruijn()

See also

make_kautz_graph(), make_line_graph()

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> De-Bruijn graph 2-2 ───────────────────────────────────── 2307eb6 ──
#> ℹ directed
#> ℹ 4 vertices · 8 edges
#> 
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph:  name <chr>, m <dbl>, n <dbl>
#> 
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 → 1  1 → 2  2 → 3  2 → 4  3 → 1  3 → 2  4 → 3  4 → 4 
make_line_graph(g)
#> ── <igraph> Line graph ────────────────────────────────────────────── 9ac065c ──
#> ℹ directed
#> ℹ 4 vertices · 8 edges
#> 
#> ── Attributes ──────────────────────────────────────────────────────────────────
#> → graph:  name <chr>
#> 
#> ── Edges ───────────────────────────────────────────────────────────────────────
#> [1] 1 → 1  3 → 1  1 → 2  3 → 2  2 → 3  4 → 3  2 → 4  4 → 4