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
55
56
57
58
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/paths.R
\name{max_cardinality}
\alias{max_cardinality}
\alias{maximum.cardinality.search}
\title{Maximum cardinality search}
\usage{
max_cardinality(graph)
}
\arguments{
\item{graph}{The input graph. It may be directed, but edge directions are
ignored, as the algorithm is defined for undirected graphs.}
}
\value{
A list with two components: \item{alpha}{Numeric vector. The
vertices ordered according to the maximum cardinality search.}
\item{alpham1}{Numeric vector. The inverse of \code{alpha}.}
}
\description{
Maximum cardinality search is a simple ordering a vertices that is useful in
determining the chordality of a graph.
}
\details{
Maximum cardinality search visits the vertices in such an order that every
time the vertex with the most already visited neighbors is visited. Ties are
broken randomly.
The algorithm provides a simple basis for deciding whether a graph is
chordal, see References below, and also \code{\link{is_chordal}}.
}
\examples{
## The examples from the Tarjan-Yannakakis paper
g1 <- graph_from_literal(A-B:C:I, B-A:C:D, C-A:B:E:H, D-B:E:F,
E-C:D:F:H, F-D:E:G, G-F:H, H-C:E:G:I,
I-A:H)
max_cardinality(g1)
is_chordal(g1, fillin=TRUE)
g2 <- graph_from_literal(A-B:E, B-A:E:F:D, C-E:D:G, D-B:F:E:C:G,
E-A:B:C:D:F, F-B:D:E, G-C:D:H:I, H-G:I:J,
I-G:H:J, J-H:I)
max_cardinality(g2)
is_chordal(g2, fillin=TRUE)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\references{
Robert E Tarjan and Mihalis Yannakakis. (1984). Simple
linear-time algorithms to test chordality of graphs, test acyclicity of
hypergraphs, and selectively reduce acyclic hypergraphs. \emph{SIAM Journal
of Computation} 13, 566--579.
}
\seealso{
\code{\link{is_chordal}}
}
\keyword{graphs}
|
