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>
case_emptyVertColorMapEmpty =
assertEqual "" 0 $ IntMap.size emptyVertColorMap
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
-- | 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
, 'prop_colorDsaturClique
, 'prop_colorLFAllNodes
, 'prop_colorDsaturAllNodes
, 'prop_colorDsaturClique
, 'prop_colorLFAllNodes
, 'prop_colorDsaturAllNodes
+ , 'prop_isColorableTestableGraph
+ , 'prop_isColorableTestableClique
, colorInOrder
, colorLF
, colorDsatur
, colorInOrder
, colorLF
, colorDsatur
-- * Color map transformations
, colorVertMap
-- * Color map transformations
, colorVertMap
+ -- * Vertex characteristics
, verticesByDegreeDesc
, verticesByDegreeAsc
, verticesByDegreeDesc
, verticesByDegreeAsc
+ , neighbors
+ , hasLoop
+ , isUndirected
) where
import Data.Maybe
) where
import Data.Maybe
neighbors :: Graph.Graph -> Graph.Vertex -> [Graph.Vertex]
neighbors g v = g Array.! v
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
-- * 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]
-- | Get the colors of a list of vertices.
-- Any uncolored vertices are ignored.
listColors :: VertColorMap -> [Graph.Vertex] -> [Color]