make_de_bruijn_graph: De Bruijn graphs

In igraph: Network Analysis and Visualization

De Bruijn graphs

Description

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

Usage

make_de_bruijn_graph(m, n)

de_bruijn_graph(...)

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.

Value

A graph object.

Author(s)

Gabor Csardi [e-mail]

See Also

make_kautz_graph(), make_line_graph()

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)
make_line_graph(g)

igraph documentation built on Oct. 20, 2024, 1:06 a.m.