module Data.Apart.Structures.Graph (Graph, Edges (..), isolated, star, remove) where
import "free" Control.Comonad.Cofree (Cofree (..), unwrap)
import "comonad" Control.Comonad (Comonad (..))
import Data.Apart.Transformations (Segmented (..))
type Graph = Cofree Edges
data Edges a = Empty | Connect a | Overlay a deriving Show
instance Functor Edges where
fmap f Empty = Empty
fmap f (Connect x) = Connect $ f x
fmap f (Overlay x) = Overlay $ f x
instance Foldable Edges where
foldr f acc Empty = acc
foldr f acc (Connect x) = f x acc
foldr f acc (Overlay x) = f x acc
instance Traversable Edges where
traverse f Empty = pure Empty
traverse f (Connect x) = Connect <$> f x
traverse f (Overlay x) = Overlay <$> f x
connect, overlay, empty :: Segmented Graph a -> Segmented Graph a
connect = foldr (\x _ -> Connect x) Empty
overlay = foldr (\x _ -> Overlay x) Empty
empty = const Empty
isolated :: Foldable t => t a -> Segmented Graph a
isolated = foldr (\el -> Overlay . (:<) el) Empty
star :: Foldable t => a -> t a -> Graph a
star x structure = x :< connect (isolated structure)
remove :: Eq a => a -> Graph a -> Segmented Graph a
remove x graph@((==) x . extract -> True) = overlay $ unwrap graph
remove x graph@(y :< segment) = ((:<) y . overlay . remove x) <$> segment
degree :: Graph a -> Int
degree (x :< Empty) = 0
degree (x :< Overlay xs) = 0
degree (x :< Connect xs) = length xs