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
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/coloring.R
\name{greedy_vertex_coloring}
\alias{greedy_vertex_coloring}
\title{Greedy vertex coloring}
\usage{
greedy_vertex_coloring(graph, heuristic = c("colored_neighbors", "dsatur"))
}
\arguments{
\item{graph}{The graph object to color.}
\item{heuristic}{The selection heuristic for the next vertex to consider.
Possible values are: \dQuote{colored_neighbors} selects the vertex with the
largest number of already colored neighbors. \dQuote{dsatur} selects the
vertex with the largest number of unique colors in its neighborhood, i.e.
its "saturation degree"; when there are several maximum saturation degree
vertices, the one with the most uncolored neighbors will be selected.}
}
\value{
A numeric vector where item \code{i} contains the color index
associated to vertex \code{i}.
}
\description{
\code{greedy_vertex_coloring()} finds a coloring for the vertices of a graph
based on a simple greedy algorithm.
}
\details{
The goal of vertex coloring is to assign a "color" (represented as a positive
integer) to each vertex of the graph such that neighboring vertices never
have the same color. This function solves the problem by considering the
vertices one by one according to a heuristic, always choosing the smallest
color that differs from that of already colored neighbors. The coloring
obtained this way is not necessarily minimum but it can be calculated in
linear time.
}
\examples{
g <- make_graph("petersen")
col <- greedy_vertex_coloring(g)
plot(g, vertex.color = col)
}
\concept{coloring}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Coloring.html#igraph_vertex_coloring_greedy}{\code{igraph_vertex_coloring_greedy()}}.}
|
