Data.Graph.DAG.Edge.Utils

Documentation

data RTree a

Trivial rose tree for creating spanning trees. We make control structure instances "parallel" (instead of cartesian) by default for simplicity.

Constructors

a :@-> [RTree a]

Instances

Monad RTree

Functor RTree

Applicative RTree

Foldable RTree

Eq a0 => Eq (RTree a)

Show a0 => Show (RTree a)

Monoid a => Monoid (RTree a)

SEq a0 (KProxy a0) => SEq (RTree a) (KProxy (RTree a))

PEq (RTree k) (KProxy (RTree k))

SDecide a0 (KProxy a0) => SDecide (RTree a) (KProxy (RTree a))

SingKind a0 (KProxy a0) => SingKind (RTree a) (KProxy (RTree a))

(SingI a0 n0, SingI [RTree a0] n1) => SingI (RTree a) ((:@->) a n n)

SuppressUnusedWarnings (k -> TyFun [RTree k] (RTree k) -> *) ((:@->$$) k)

SuppressUnusedWarnings (TyFun k (TyFun [RTree k] (RTree k) -> *) -> *) ((:@->$) k)

data Sing (RTree a0) where

• (:%@->) :: (~) (RTree a) z ((:@->) a n n) => Sing a n -> Sing [RTree a] n -> Sing (RTree a) z

type (:==) (RTree k0) a0 b0 = Equals_1627432871 k0 a0 b0

type DemoteRep (RTree a0) (KProxy (RTree a0)) = RTree (DemoteRep a0 (KProxy a0))

type Apply (RTree k) [RTree k] ((:@->$$) k l1) l0 = (:@->$$$) k l1 l0

type Apply (TyFun [RTree k] (RTree k) -> *) k ((:@->$) k) l0 = (:@->$$) k l0

type family Equals_1627432871 a b :: Bool

Equations

Equals_1627432871 ((:@->) a a) ((:@->) b b) = (:&&) ((:==) a b) ((:==) a b)

Equals_1627432871 (a :: RTree k) (b :: RTree k) = FalseSym0

type SRTree z = Sing z

type (:@->$$$) t t = (:@->) t t

data l :@->$$ l

Constructors

forall arg . (~) (KindOf (Apply ((:@->$$) l) arg)) (KindOf ((:@->$$$) l arg)) => (:@->$$###)

Instances

SuppressUnusedWarnings (k -> TyFun [RTree k] (RTree k) -> *) ((:@->$$) k)

type Apply (RTree k) [RTree k] ((:@->$$) k l1) l0 = (:@->$$$) k l1 l0

data (:@->$) l

Constructors

forall arg . (~) (KindOf (Apply (:@->$) arg)) (KindOf ((:@->$$) arg)) => (:@->$###)

Instances

SuppressUnusedWarnings (TyFun k (TyFun [RTree k] (RTree k) -> *) -> *) ((:@->$) k)

type Apply (TyFun [RTree k] (RTree k) -> *) k ((:@->$) k) l0 = (:@->$$) k l0

reflect :: forall a. (SingI a, SingKind (KProxy :: KProxy k)) => Proxy a -> Demote a

Gives us a generic way to get our spanning trees of the graph, as a value. Credit goes to András Kovács.

type family AppendIfNotElemTrees c trees :: [RTree k]

Adds an empty c tree to the list of trees uniquely

Equations

AppendIfNotElemTrees c ((c :@-> xs) : xss) = (c :@-> xs) : xss

AppendIfNotElemTrees c ((x :@-> xs) : xss) = (x :@-> xs) : AppendIfNotElemTrees c xss

AppendIfNotElemTrees c [] = (c :@-> []) : []

type family AddChildTo test child trees :: [RTree k]

Adds c as a child of any tree with a root t. Assumes unique roots.

Equations

AddChildTo t c ((t :@-> xs) : xss) = (t :@-> AppendIfNotElemTrees c xs) : AddChildTo t c xss

AddChildTo t c ((x :@-> xs) : xss) = (x :@-> AddChildTo t c xs) : AddChildTo t c xss

AddChildTo t c [] = []

type family AddEdge' edge trees hasFromRoot hasToRoot :: [RTree Symbol]

We need to track if from has is a root node or not. TODO: Some code repeat.

Equations

AddEdge' (EdgeType from to) [] False False = (from :@-> ((to :@-> []) : [])) : ((to :@-> []) : [])

AddEdge' (EdgeType from to) [] True False = (to :@-> []) : []

AddEdge' (EdgeType from to) [] False True = (from :@-> ((to :@-> []) : [])) : []

AddEdge' x [] True True = []

AddEdge' (EdgeType from to) ((from :@-> xs) : xss) hasFromRoot hasToRoot = (from :@-> AppendIfNotElemTrees to xs) : AddEdge' (EdgeType from to) xss True hasToRoot

AddEdge' (EdgeType from to) ((to :@-> xs) : xss) hasFromRoot hasToRoot = (to :@-> AddEdge' (EdgeType from to) xs True True) : AddEdge' (EdgeType from to) xss hasFromRoot True

AddEdge' (EdgeType from to) ((x :@-> xs) : xss) hasFromRoot hasToRoot = (x :@-> AddEdge' (EdgeType from to) xs True True) : AddEdge' (EdgeType from to) xss hasFromRoot hasToRoot

type family AddEdge edge trees :: [RTree Symbol]

Add to as a child to every from node in the accumulator.

Equations

AddEdge a trees = AddEdge' a trees False False

type family SpanningTrees' edges acc :: [RTree Symbol]

Auxilliary function normally defined in a where clause for manual folding.

Equations

SpanningTrees' [] trees = trees

SpanningTrees' (EdgeType from to : es) trees = SpanningTrees' es (AddEdge (EdgeType from to) trees)

type family SpanningTrees edges :: [RTree Symbol]

Expects edges to already be type-safe

Equations

SpanningTrees edges = SpanningTrees' edges []

getSpanningTrees :: EdgeSchema es x unique -> Proxy (SpanningTrees es)

espanningtrees :: SingI (SpanningTrees' es []) => EdgeSchema es x unique -> Demote (SpanningTrees' es [])

Get the spanning trees of an EdgeSchema. Operate on the assumtion that the data returned is actually [Tree String].

etree :: SingI (SpanningTrees' es []) => String -> EdgeSchema es x unique -> Maybe (RTree String)

Get a single tree.

ehead :: (EdgeType from to ~ b, EdgeValue from to ~ a) => EdgeSchema (b : old) c u -> a

Degenerate (but type-safe!) head.

eTreeToEdges :: RTree String -> [(String, String)]

For now, we only suport unique edges.

eForestToEdges :: [RTree String] -> [(String, String)]

Get a first-class list of edges from spanning trees. Only works on uniqely edged EdgeSchema's.

fcEdges :: SingI (SpanningTrees' es []) => EdgeSchema es x True -> [(String, String)]

Get the First-Class edges of a uniquely-edged EdgeSchema.