Safe Haskell	None
Language	Haskell2010

Data.Graph.DAG.Edge.Utils

Synopsis

Documentation

data RTree a Source

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 Source

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 Source

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

data l :@->$$ l Source

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 Source

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 Source

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] Source

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] Source

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] Source

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] Source

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] Source

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] Source

Expects edges to already be type-safe

Equations

SpanningTrees edges = SpanningTrees' edges []

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

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

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) Source

Get a single tree.

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

Degenerate (but type-safe!) head.

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

For now, we only suport unique edges.

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

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)] Source

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