Skip to content

Instantly share code, notes, and snippets.

@eddieantonio
Created September 22, 2013 22:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save eddieantonio/6664658 to your computer and use it in GitHub Desktop.
Save eddieantonio/6664658 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment