1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/make.R
\name{make_de_bruijn_graph}
\alias{de_bruijn_graph}
\alias{graph.de.bruijn}
\alias{make_de_bruijn_graph}
\title{De Bruijn graphs}
\usage{
make_de_bruijn_graph(m, n)
de_bruijn_graph(...)
}
\arguments{
\item{m}{Integer scalar, the size of the alphabet. See details below.}
\item{n}{Integer scalar, the length of the labels. See details below.}
\item{...}{Passed to \code{make_de_bruijn_graph}.}
}
\value{
A graph object.
}
\description{
De Bruijn graphs are labeled graphs representing the overlap of strings.
}
\details{
A de Bruijn graph represents relationships between strings. An alphabet of
\code{m} letters are used and strings of length \code{n} are considered. A
vertex corresponds to every possible string and there is a directed edge
from vertex \code{v} to vertex \code{w} if the string of \code{v} can be
transformed into the string of \code{w} by removing its first letter and
appending a letter to it.
Please note that the graph will have \code{m} to the power \code{n} vertices
and even more edges, so probably you don't want to supply too big numbers
for \code{m} and \code{n}.
De Bruijn graphs have some interesting properties, please see another
source, eg. Wikipedia for details.
}
\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)
}
\author{
Gabor Csardi <csardi.gabor@gmail.com>
}
\seealso{
\code{\link{make_kautz_graph}}, \code{\link{make_line_graph}}
}
\keyword{graphs}
|
