coloring: Compute a vertex coloring for a graph

In RBGL: An interface to the BOOST graph library

Description

Compute vertex coloring for a graph

Usage

sequential.vertex.coloring(g)

Arguments

g	an instance of the graph class

Details

A vertex coloring for a graph is to assign a color for each vertex so that no two adjacent vertices are of the same color. We designate the colors as sequential integers: 1, 2, ....

For ordered vertices, v1, v2, ..., vn, for k = 1, 2, ..., n, this algorithm assigns vk to the smallest possible color. It does NOT guarantee to use minimum number of colors.

See documentations on these algorithms in Boost Graph Library for more details.

Value

no. of colors needed	how many colors to use to color the graph
colors of nodes	color label for each vertex

Author(s)

Li Long <[e-mail]>

References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

Examples

con <- file(system.file("XML/dijkex.gxl",package="RBGL"), open="r")
coex <- fromGXL(con)
close(con)
sequential.vertex.coloring(coex)

RBGL documentation built on Nov. 8, 2020, 5 p.m.