Statistics
| Branch: | Tag: | Revision:

root / htest / Test / Ganeti / HTools @ df8578fb

Name Size
  Backend
CLI.hs 4.4 kB
Cluster.hs 17.9 kB
Container.hs 3 kB
Graph.hs 7 kB
Instance.hs 7 kB
Loader.hs 3.4 kB
Node.hs 15.4 kB
PeerMap.hs 2.6 kB
Types.hs 5.1 kB

Latest revisions

# Date Author Comment
df8578fb 12/17/2012 01:37 pm Iustin Pop

Generalise the test helper 'genUniquesList'

Instead of always using "arbitrary", make it require a generator (that
can then use more complex rules for building the list elements), and
also convert it to use a temporary set instead of list membership.

Signed-off-by: Iustin Pop <>...

cce30754 12/14/2012 03:11 pm Guido Trotter

Improve a few Graph test properties

Return type is changed from Property to Bool, and the ==? True at the
end is dropped.

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

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...

9f80119c 12/03/2012 11:41 am Guido Trotter

Add generator for an instance on a node list

Given a node list in input, we get an instance that had nodes in it.

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

View revisions

Also available in: Atom