ganeti

Ganeti.HTools.Graph

Description

Algorithms on Graphs.

This module contains a few graph algorithms and the transoformations needed for them to be used on nodes.

LF-coloring is described in: Welsh, D. J. A.; Powell, M. B. (1967), An upper bound for the chromatic number of a graph and its application to timetabling problems, The Computer Journal 10 (1): 85-86, doi:10.1093comjnl10.1.85 http://comjnl.oxfordjournals.org/content/10/1/85

DSatur is described in: Brelaz, D. (1979), New methods to color the vertices of a graph, Communications of the ACM 22 (4): 251-256, doi:10.1145/359094.359101 http://dx.doi.org/10.1145%2F359094.359101

Also interesting: Klotz, W. (2002). Graph coloring algorithms. Mathematics Report, Technical University Clausthal, 1-9. <http:www.math.tu-clausthal.deArbeitsgruppenDiskrete-Optimierung publications2002/gca.pdf>

Synopsis

# Type declarations

type Color = IntSource

Node colors.

type Satur = IntSource

type VertColorMap = IntMap ColorSource

Vertex to Color association.

type ColorVertMap = IntMap [Int]Source

Color to Vertex association.

# Vertices characteristics

verticesDegree :: Graph -> [(Vertex, Int)]Source

verticesByDegreeDesc :: Graph -> [Vertex]Source

vertices of a graph, sorted by ascending degree.

verticesByDegreeAsc :: Graph -> [Vertex]Source

vertices of a graph, sorted by descending degree.

neighbors :: Graph -> Vertex -> [Vertex]Source

Get the neighbors of a vertex.

hasLoop :: Graph -> BoolSource

Check whether a graph has no loops. (vertices connected to themselves)

isUndirected :: Graph -> BoolSource

Check whether a graph is undirected

# Coloring

Empty color map.

isColorable :: Graph -> BoolSource

Check whether a graph is colorable.

verticesColorSet :: VertColorMap -> [Vertex] -> IntSetSource

neighColors :: Graph -> VertColorMap -> Vertex -> [Color]Source

colorNode :: Graph -> VertColorMap -> Vertex -> ColorSource

colorInOrder :: Graph -> [Vertex] -> VertColorMapSource

Color greedily all nodes in the given order.

colorLF :: Graph -> VertColorMapSource

Color greedily all nodes, larger first.

vertexSaturation :: Graph -> VertColorMap -> Vertex -> (Vertex, (Satur, Int))Source

vertexColorDegree :: Graph -> VertColorMap -> Vertex -> (Vertex, (Int, Int))Source

colorDynamicOrder :: Ord a => (Graph -> VertColorMap -> Vertex -> (Vertex, a)) -> Graph -> VertColorMap -> [Vertex] -> VertColorMapSource

colorDcolor :: Graph -> VertColorMapSource

Color greedily all nodes, highest number of colored neighbors, then highest degree. This is slower than colorLF as we must dynamically recalculate which node to color next among all remaining ones but produces better results.

colorDsatur :: Graph -> VertColorMapSource

Color greedily all nodes, highest saturation, then highest degree. This is slower than colorLF as we must dynamically recalculate which node to color next among all remaining ones but produces better results.

ColorVertMap from VertColorMap.