Up

module Coloring

: sig

k-coloring of undirected graphs.

A k-coloring of a graph g is a mapping c from nodes to {1,...,k} such that c(u) <> c(v) for any edge u-v in g.

Graph coloring for graphs without marks

#
module type G = sig

Minimal graph signature for Make. Sub-signature of Sig.G.

#
val is_directed : bool
#
type t
#
val nb_vertex : t -> int
#
module V : Sig.COMPARABLE
#
val out_degree : t -> V.t -> int
#
val iter_vertex : (V.t -> unit) -> t -> unit
#
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
#
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
#
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
end
#
module Make : functor (G : G) -> sig

Provide a function for k-coloring a graph.

#
module H : Hashtbl.S with type key = G.V.t

Hash tables used to store the coloring

#
val coloring : G.t -> int -> int H.t

coloring g k colors the graph g with k colors and returns the coloring as a hash table mapping nodes to their colors.

end

Graph coloring for graph with integer marks

#
module type GM = sig

Minimal graph signature for Mark. Sub-signature of Sig.IM.

#
val is_directed : bool
#
type t
#
val nb_vertex : t -> int
#
module V : Sig.COMPARABLE
#
val out_degree : t -> V.t -> int
#
val iter_vertex : (V.t -> unit) -> t -> unit
#
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
#
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
#
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
#
module Mark : sig
#
val get : V.t -> int
#
val set : V.t -> int -> unit
end
end
#
module Mark : functor (G : GM) -> sig

Provide a function for k-coloring a graph with integer marks. The provided function is more efficient that the one provided by functor Make above.

#
exception NoColoring
#
val coloring : G.t -> int -> unit

coloring g k colors the nodes of graph g using k colors, assigning the marks integer values between 1 and k. raises NoColoring when there is no possible coloring.

The graph marks may be partially set before starting; the meaning of initial values is as follows:

  • 0: a node to be colored
  • any value between 1 and k: a color already assigned
  • any value greater than k: a node to be ignored
Raises NoColoring if g cannot be k-colored.
end
end