Data.Graph.DAG.Edge.Utils

Documentation

data Tree a

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

Constructors

Node a [Tree a]

Instances

Monad Tree

Functor Tree

Applicative Tree

Eq a0 => Eq (Tree a)

Show a0 => Show (Tree a)

Monoid a => Monoid (Tree a)

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

PEq (Tree k) (KProxy (Tree k))

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

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

(SingI a0 n0, SingI [Tree a0] n1) => SingI (Tree a) (Node a n n)

SuppressUnusedWarnings (k -> TyFun [Tree k] (Tree k) -> *) (NodeSym1 k)

SuppressUnusedWarnings (TyFun k (TyFun [Tree k] (Tree k) -> *) -> *) (NodeSym0 k)

data Sing (Tree a0) where

• SNode :: (~) (Tree a) z (Node a n n) => Sing a n -> Sing [Tree a] n -> Sing (Tree a) z

type (:==) (Tree k0) a0 b0 = Equals_1627428536 k0 a0 b0

type DemoteRep (Tree a0) (KProxy (Tree a0)) = Tree (DemoteRep a0 (KProxy a0))

type Apply (Tree k) [Tree k] (NodeSym1 k l1) l0 = NodeSym2 k l1 l0

type Apply (TyFun [Tree k] (Tree k) -> *) k (NodeSym0 k) l0 = NodeSym1 k l0

type family Equals_1627428536 a b :: Bool

Equations

Equals_1627428536 (Node a a) (Node b b) = (:&&) ((:==) a b) ((:==) a b)

Equals_1627428536 (a :: Tree k) (b :: Tree k) = FalseSym0

type STree z = Sing z

type NodeSym2 t t = Node t t

data NodeSym1 l l

Constructors

forall arg . (~) (KindOf (Apply (NodeSym1 l) arg)) (KindOf (NodeSym2 l arg)) => NodeSym1KindInference

Instances

SuppressUnusedWarnings (k -> TyFun [Tree k] (Tree k) -> *) (NodeSym1 k)

type Apply (Tree k) [Tree k] (NodeSym1 k l1) l0 = NodeSym2 k l1 l0

data NodeSym0 l

Constructors

forall arg . (~) (KindOf (Apply NodeSym0 arg)) (KindOf (NodeSym1 arg)) => NodeSym0KindInference

Instances

SuppressUnusedWarnings (TyFun k (TyFun [Tree k] (Tree k) -> *) -> *) (NodeSym0 k)

type Apply (TyFun [Tree k] (Tree k) -> *) k (NodeSym0 k) l0 = NodeSym1 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 :: [Tree k]

Adds an empty c tree to the list of trees uniquely

Equations

AppendIfNotElemTrees c (Node c xs : xss) = Node c xs : xss

AppendIfNotElemTrees c (Node x xs : xss) = Node x xs : AppendIfNotElemTrees c xss

AppendIfNotElemTrees c [] = Node c [] : []

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

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

Equations

AddChildTo t c (Node t xs : xss) = Node t (AppendIfNotElemTrees c xs) : AddChildTo t c xss

AddChildTo t c (Node x xs : xss) = Node x (AddChildTo t c xs) : AddChildTo t c xss

AddChildTo t c [] = []

type family AddEdge' edge trees hasFromRoot hasToRoot :: [Tree 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 = Node from (Node to [] : []) : (Node to [] : [])

AddEdge' (EdgeType from to) [] True False = Node to [] : []

AddEdge' (EdgeType from to) [] False True = Node from (Node to [] : []) : []

AddEdge' x [] True True = []

AddEdge' (EdgeType from to) (Node from xs : xss) hasFromRoot hasToRoot = Node from (AppendIfNotElemTrees to xs) : AddEdge' (EdgeType from to) xss True hasToRoot

AddEdge' (EdgeType from to) (Node to xs : xss) hasFromRoot hasToRoot = Node to (AddEdge' (EdgeType from to) xs True True) : AddEdge' (EdgeType from to) xss hasFromRoot True

AddEdge' (EdgeType from to) (Node x xs : xss) hasFromRoot hasToRoot = Node x (AddEdge' (EdgeType from to) xs True True) : AddEdge' (EdgeType from to) xss hasFromRoot hasToRoot

type family AddEdge edge trees :: [Tree 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 :: [Tree 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 :: [Tree Symbol]

Expects edges to already be type-safe

Equations

SpanningTrees edges = SpanningTrees' edges []

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