DegreeSequence.hs

module Data.Graph.UGraph.DegreeSequence
    (
    DegreeSequence

    -- * Construction
    , degreeSequence
    , getDegreeSequence

    -- * Queries
    , isGraphicalSequence
    -- , isDirectedGraphic
    , holdsHandshakingLemma

    -- * Graph generation
    -- , fromGraphicalSequence
    ) where

import Data.List (reverse, sort)

import Data.Hashable

import Data.Graph.Types
import Data.Graph.UGraph

-- | The Degree Sequence of a simple 'UGraph' is a list of degrees of the
-- vertices in the graph
--
-- Use 'degreeSequence' to construct a valid Degree Sequence
newtype DegreeSequence = DegreeSequence { unDegreeSequence :: [Int]}
    deriving (Eq, Ord, Show)

-- | Construct a 'DegreeSequence' from a list of degrees. Negative degree values
-- get discarded
degreeSequence :: [Int] -> DegreeSequence
degreeSequence = DegreeSequence . reverse . sort . filter (>0)

-- | Get the 'DegreeSequence' of a simple 'UGraph'. If the graph is not @simple@
-- (see 'isSimple') the result is Nothing
getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence
getDegreeSequence g
    | (not . isSimple) g = Nothing
    | otherwise = Just $ degreeSequence $ degrees g

-- | Tell if a 'DegreeSequence' is a Graphical Sequence
--
-- A Degree Sequence is a @Graphical Sequence@ if a corresponding 'UGraph' for
-- it exists. Uses the Havel-Hakimi algorithm
isGraphicalSequence :: DegreeSequence -> Bool
isGraphicalSequence (DegreeSequence []) = True
isGraphicalSequence (DegreeSequence (x:xs))
    | x > length xs = False
    | otherwise = isGraphicalSequence $ degreeSequence seq'
        where seq' = subtract 1 <$> take x xs ++ drop x xs

-- | Tell if a 'DegreeSequence' is a Directed Graphic
--
-- A @Directed Graphic@ is a Degree Sequence for which a 'DGraph' exists
-- TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms
isDirectedGraphic :: DegreeSequence -> Bool
isDirectedGraphic = undefined

-- | Tell if a 'DegreeSequence' holds the Handshaking lemma, that is, if the
-- number of vertices with odd degree is even
holdsHandshakingLemma :: DegreeSequence -> Bool
holdsHandshakingLemma = even . length . filter odd . unDegreeSequence

-- | Get the corresponding 'UGraph' of a 'DegreeSequence'. If the
-- 'DegreeSequence' is not graphical (see 'isGraphicalSequence') the result is
-- Nothing
fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())
fromGraphicalSequence = undefined