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.de/Arbeitsgruppen/Diskrete-Optimierung publications2002/gca.pdf>

Synopsis

# Type declarations

type Color = Int Source #

Node colors.

type Satur = Int Source #

Saturation: number of colored neighbors.

type VertColorMap = IntMap Color Source #

Vertex to Color association.

type ColorVertMap = IntMap [Int] Source #

Color to Vertex association.

# Vertices characteristics

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

(vertex, degree) tuples on a graph.

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 -> Bool Source #

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

isUndirected :: Graph -> Bool Source #

Check whether a graph is undirected

# Coloring

Empty color map.

isColorable :: Graph -> Bool Source #

Check whether a graph is colorable.

verticesColors :: VertColorMap -> [Vertex] -> [Color] Source #

Get the colors of a list of vertices. Any uncolored vertices are ignored.

verticesColorSet :: VertColorMap -> [Vertex] -> IntSet Source #

Get the set of colors of a list of vertices. Any uncolored vertices are ignored.

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

Get the colors of the neighbors of a vertex.

colorNode :: Graph -> VertColorMap -> Vertex -> Color Source #

Color one node.

colorNodeInMap :: Graph -> Vertex -> VertColorMap -> VertColorMap Source #

Color a node returning the updated color map.

colorInOrder :: Graph -> [Vertex] -> VertColorMap Source #

Color greedily all nodes in the given order.

colorLF :: Graph -> VertColorMap Source #

Color greedily all nodes, larger first.

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

(vertex, (saturation, degree)) for a vertex.

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

(vertex, (colordegree, degree)) for a vertex.

Arguments

 :: Ord a => (Graph -> VertColorMap -> Vertex -> (Vertex, a)) Helper to induce the choice -> Graph Target graph -> VertColorMap Accumulating vertex color map -> [Vertex] List of remaining vertices -> VertColorMap Output vertex color map

Color all nodes in a dynamic order. We have a list of vertices still uncolored, and at each round we choose&delete one vertex among the remaining ones. A helper function is used to induce an order so that the next vertex can be chosen.

colorDcolor :: Graph -> VertColorMap Source #

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 -> VertColorMap Source #

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.