Statistics
| Branch: | Tag: | Revision:

root / htest @ d5b031dc

Name Size
  Test
  data
  shelltests
cli-tests-defs.sh 1.2 kB
hpc-htools.hs 19 Bytes
live-test.sh 5 kB
offline-test.sh 3.2 kB
test.hs 3.4 kB

Latest revisions

# 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 <>
dae1f9cb 12/04/2012 06:46 pm Guido Trotter

HTools/Node: add mkNodeGraph function

This function helps treating node node problems as graph problems.
It can transform a list of nodes plus a list of instances into a graph
which uses the nodes as vertices, and instances as edges connecting them
(as long as they have both a primary and a secondary node)...
8b50de5c 12/04/2012 06:46 pm Guido Trotter

Fix Dsatur and add Dcolor

Our Dsatur implementation was incorrect: while the paper defined the
degree of saturation of a vertex as the number of different colors it is
adjacent to, we were using the number of colors, without considering
uniqueness. This effectively implemented a different algorithm, which is...
c94f9990 12/04/2012 06:46 pm Guido Trotter

Add "proper coloring" unittest check

We have to check that for each edge its vertices have different colors.

This is very easy to do with a vertex-to-color map, but not so easy with
a color-to-vertex one. Since all our coloring algorithms created a
vertex-to-color map behind the scenes and then converted it, we flip...
c67b908a 12/04/2012 01:44 pm Iustin Pop

Add a negative type

This mirrors the positive one, and will be needed for relative job
IDs.

Signed-off-by: Iustin Pop <>
Reviewed-by: Guido Trotter <>
b46ba79c 12/04/2012 01:44 pm Iustin Pop

Add types and parameters for common opcode implementation

This will go into a separate type; this patch adds the needed
underlying types and parameters.

Signed-off-by: Iustin Pop <>
Reviewed-by: Guido Trotter <>
4a826364 12/04/2012 01:44 pm Iustin Pop

Add CommonOpParams and MetaOpCode types

This patch adds the "meta" opcode type and the common op
params. Compatibility tests with Python are changed to pass Meta
opcodes.

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

View revisions

Also available in: Atom