Statistics
| Branch: | Tag: | Revision:

root / htest / Test / Ganeti / HTools / Graph.hs @ dae1f9cb

History | View | Annotate | Download (5.7 kB)

# Date Author Comment
8e6623c8 12/04/2012 06:46 pm Guido Trotter

Add Ganeti.HTools.Graph

This module implements some algorithms on Data.Graph data structures.
At the moment its main functionality is an LF-color implementation
(greedy coloring in descending order of degree). There are also a few
extra functions to calculate the degree order, and convert the node to...
742bd043 12/04/2012 06:46 pm Guido Trotter

Add Dsatur implementation

Implement the Dsatur algorithm for Graph coloring. This also abstracts
the neighColors function into two subfunctions that this algorithm can
reuse.

Signed-off-by: Guido Trotter <>
Reviewed-by: Iustin Pop <>
faef859e 12/04/2012 06:46 pm Guido Trotter

Ganeti/HTools/Graph Add isColorable

Check whether coloring on a given graph makes sense. This is the case
only if there are no loops and the graph is undirected.

Signed-off-by: Guido Trotter <>
Reviewed-by: Iustin Pop <>
34a21cc4 12/04/2012 06:46 pm Guido Trotter

Add tests for verticesByDegree{Asc,Desc}

This brings our coverage of Graph.hs to 100%

Signed-off-by: Guido Trotter <>
Reviewed-by: Iustin Pop <>