graphical.hs

import Data.List (sort)

-- Given a degree sequence, determines whether it is graphical. Returns a list
-- of steps from the base case to the original degree sequence.
graphical :: [Int] -> Maybe [[Int]]
graphical ds | even $ sum ds  = graphical' ds []
              -- By the handshaking lemma, cannot be a graph with odd sum:
             | otherwise      = Nothing

graphical' ds previous
     -- It's all zeros and ones! Then we're all good.
    | zerosAndOnes ds' = Just (ds':previous)
    | otherwise        = reduceSequence ds' previous
     -- Ensure the degree sequence is sorted.
    where ds' = sort ds

-- True if all are zeros and ones.
zerosAndOnes = all $ \i -> i `elem` [0, 1]

-- Reduce Sequence
reduceSequence ds previous =
    let
        (n:rds) = reverse ds
        changedVertices = [i - 1 | i <- take n rds]
        ds' = reverse $ changedVertices ++ (drop n rds)
    in if all whole changedVertices
        then graphical' ds' (ds:previous)
        else Nothing
        
-- Returns true if the int is a whole number... really useless.
whole = (>= 0)

q10a = [1,1,1,2,2,2,3,3,3,4,4,4] :: [Int]
q10b = [2,3,3,4,5,5]             :: [Int]

main = do
    putStrLn "Sequence for 10a: "
    putStrLn $ show $ graphical q10a
    putStrLn "Sequence for 10b: "
    putStrLn $ show $ graphical q10b