| make_de_bruijn_graph {igraph} | R Documentation |
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 |
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 csardi.gabor@gmail.com
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)