module Data.Graph where 

import qualified Data.Set as S

-- Simplistic view (from a performance perspective) of a graph
data Graph c a = Graph (S.Set c) (S.Set (c, a, c))
    deriving (Show, Eq)

emptyGraph :: Graph c a
emptyGraph = Graph S.empty S.empty

verts :: Graph c a -> [c]
verts (Graph cs _) = S.toList cs

gUnion :: (Ord c, Ord a) => Graph c a -> Graph c a -> Graph c a
gUnion (Graph c1 e1) (Graph c2 e2) = Graph (S.union c1 c2) (S.union e1 e2)

extractNodes :: Ord c => S.Set (c, a, c) -> S.Set c
extractNodes = S.foldr (\(c1, _, c2) s -> S.union s $ S.fromList [c1, c2]) S.empty

gFocus :: (Ord c) => c -> Graph c a -> Graph c a
gFocus c (Graph _ e) = 
    let e' = S.filter (\(c1, _, c2) -> c1 == c || c2 == c) e
    in Graph (extractNodes e') e'


isSingleton :: Graph c a -> Bool
isSingleton (Graph v _) = length v == 1

getSingleton :: Graph c a -> Maybe c
getSingleton g@(Graph v _) 
    | isSingleton g = Just . head $ S.toList v
    | otherwise = Nothing


gleaves :: (Ord c) => Graph c a -> [c]
gleaves (Graph v e) = S.toList $ v S.\\ S.map (\(c, _, _) -> c) e

gcmap :: (Ord k, Ord a) => (c -> k) -> Graph c a -> Graph k a
gcmap f (Graph v e) = Graph (S.map f v) (S.map (\(c1, a, c2) -> (f c1, a, f c2)) e)

-- Could be written without the Eq instances
isEmpty :: (Eq c, Eq a) => Graph c a -> Bool
isEmpty g = g == emptyGraph