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 <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

diff --git a/htest/Test/Ganeti/HTools/Graph.hs b/htest/Test/Ganeti/HTools/Graph.hs
index b9c1111..e9f62cb 100644 (file)
--- a/htest/Test/Ganeti/HTools/Graph.hs
+++ b/htest/Test/Ganeti/HTools/Graph.hs
@@ -89,6 +89,14 @@ case_emptyVertColorMapEmpty :: Assertion
 case_emptyVertColorMapEmpty =
   assertEqual "" 0 $ IntMap.size emptyVertColorMap
 
+-- | Check that our generated graphs are colorable
+prop_isColorableTestableGraph :: TestableGraph -> Property
+prop_isColorableTestableGraph (TestableGraph g) = isColorable g ==? True
+
+-- | Check that our generated graphs are colorable
+prop_isColorableTestableClique :: TestableClique -> Property
+prop_isColorableTestableClique (TestableClique g) = isColorable g ==? True
+
 -- | Check that the given algorithm colors a clique with the same number of
 -- colors as the vertices number.
 prop_colorClique :: (Graph.Graph -> ColorVertMap) -> TestableClique -> Property
@@ -128,4 +136,6 @@ testSuite "HTools/Graph"
             , 'prop_colorDsaturClique
             , 'prop_colorLFAllNodes
             , 'prop_colorDsaturAllNodes
+            , 'prop_isColorableTestableGraph
+            , 'prop_isColorableTestableClique
             ]

diff --git a/htools/Ganeti/HTools/Graph.hs b/htools/Ganeti/HTools/Graph.hs
index 3555921..bdb8a33 100644 (file)
--- a/htools/Ganeti/HTools/Graph.hs
+++ b/htools/Ganeti/HTools/Graph.hs
@@ -58,11 +58,15 @@ module Ganeti.HTools.Graph
   , colorInOrder
   , colorLF
   , colorDsatur
+  , isColorable
     -- * Color map transformations
   , colorVertMap
-    -- * Vertex sorting
+    -- * Vertex characteristics
   , verticesByDegreeDesc
   , verticesByDegreeAsc
+  , neighbors
+  , hasLoop
+  , isUndirected
   ) where
 
 import Data.Maybe
@@ -106,12 +110,27 @@ verticesByDegreeAsc g = map fst . sortBy (comparing snd) $ verticesDegree g
 neighbors :: Graph.Graph -> Graph.Vertex -> [Graph.Vertex]
 neighbors g v = g Array.! v
 
+-- | Check whether a graph has no loops.
+-- (vertices connected to themselves)
+hasLoop :: Graph.Graph -> Bool
+hasLoop g = any vLoops $ Graph.vertices g
+    where vLoops v = v `elem` neighbors g v
+
+-- | Check whether a graph is undirected
+isUndirected :: Graph.Graph -> Bool
+isUndirected g =
+  (sort . Graph.edges) g == (sort . Graph.edges . Graph.transposeG) g
+
 -- * Coloring
 
 -- | Empty color map.
 emptyVertColorMap :: VertColorMap
 emptyVertColorMap = IntMap.empty
 
+-- | Check whether a graph is colorable.
+isColorable :: Graph.Graph -> Bool
+isColorable g = isUndirected g && not (hasLoop g)
+
 -- | Get the colors of a list of vertices.
 -- Any uncolored vertices are ignored.
 listColors :: VertColorMap -> [Graph.Vertex] -> [Color]