Hakimi-Havel graphical sequence algorithm

deg-seq.hs

module DegreeSequence where

import           Data.List

-- | degree sequence is given by a list of non-increasing numbers
degSeq :: [Int] -> [Int]
degSeq = sortBy (flip compare)

-- | a graphical sequence is a degree sequence that has a graphical representation
isGraphicSeq :: [Int] -> Bool
isGraphicSeq [] = True
isGraphicSeq [1, 1] = True
isGraphicSeq xs =
  validSumOfDegrees xs
  && validDegrees xs
  && isGraphicSeq (reduce xs)


----------

-- | helper function to verify the sum of degrees of each vertex is even
validSumOfDegrees :: [Int] -> Bool
validSumOfDegrees ys = mod (toInteger (sum ys)) 2 == 0

-- | helper function to verify all the vertices have degree less than
-- the total number of vertices
validDegrees :: [Int] -> Bool
validDegrees ys = all (< length ys) ys

-- | reduce takes in a sorted list in descending order
--   pics up head
--   reduces 1 from first head number of elements
reduce :: [Int] -> [Int]
reduce xs = degSeq $ filter ( > 0) (map pred prefix) ++ suffix
  where
    h = head xs
    t = tail xs
    prefix = take h t
    suffix = drop h t