Class GraphColoringExtensions

Namespace: Graph1x.Algorithms

Assembly: Graph1x.dll

Heuristic vertex coloring using DSatur (Brélaz): color the vertex with the highest saturation (most distinct neighbor colors) first, breaking ties by degree. Exact on bipartite graphs; an upper bound in general — computing the chromatic number exactly is NP-hard and out of scope.

public static class GraphColoringExtensions

Inheritance: object

GraphColoringExtensions

Inherited Members: object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

ColorVertices<TVertex, TEdge>(IReadOnlyGraph<TVertex, TEdge>)

Computes a proper vertex coloring with the DSatur heuristic. Edge direction is ignored (coloring concerns the underlying undirected graph); parallel edges are harmless.

public static GraphColoring<TVertex> ColorVertices<TVertex, TEdge>(this IReadOnlyGraph<TVertex, TEdge> graph) where TVertex : notnull where TEdge : IEdge<TVertex>

Parameters

graph IReadOnlyGraph<TVertex, TEdge>: The graph to color.

Returns

GraphColoring<TVertex>: The color assignment.

Type Parameters

TVertex: The vertex type.
TEdge: The edge type.

Exceptions

ArgumentException: The graph contains a self-loop, which no proper coloring can satisfy.