History | View | Annotate | Download (7 kB)
Improve a few Graph test properties
Return type is changed from Property to Bool, and the ==? True at theend is dropped.
Signed-off-by: Guido Trotter <ultrotter@google.com>Reviewed-by: Iustin Pop <iustin@google.com>
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 fewextra functions to calculate the degree order, and convert the node to...
Add Dsatur implementation
Implement the Dsatur algorithm for Graph coloring. This also abstractsthe neighColors function into two subfunctions that this algorithm canreuse.
Ganeti/HTools/Graph Add isColorable
Check whether coloring on a given graph makes sense. This is the caseonly if there are no loops and the graph is undirected.
Add tests for verticesByDegree{Asc,Desc}
This brings our coverage of Graph.hs to 100%
Fix Dsatur and add Dcolor
Our Dsatur implementation was incorrect: while the paper defined thedegree of saturation of a vertex as the number of different colors it isadjacent to, we were using the number of colors, without consideringuniqueness. This effectively implemented a different algorithm, which is...
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 witha color-to-vertex one. Since all our coloring algorithms created avertex-to-color map behind the scenes and then converted it, we flip...