DDC.Core.Flow.Transform.Rates.Graph

Documentation

data Graph n t

Constructors

Graph (Map n (Maybe t, [Edge n]))

type Edge n = (n, Bool)

Graph for function Each node is a binding, edges are dependencies, and the bool is whether the node's output can be fused or contracted. For example, filter and map dependencies can be contracted, but a fold cannot as it must consume the entire stream before producing output.

graphOfBinds :: (Ord s, Ord a) => Program s a -> Env a -> Graph (CName s a) (Type a)

graphTopoOrder :: Ord n => Graph n t -> [n]

Find topological ordering of DAG Does not check for cycles - really must be a DAG!

mergeWeights :: Ord n => Graph n t -> Map n Int -> Graph n ()

Merge nodes together with same value in weight map. Type information of each node is thrown away. It is, perhaps surprisingly, legal to merge nodes of different types (eg filtered data), so the only sensible thing is to choose () for all new types.

invertMap :: Ord v => Map k v -> Map v [k]

numNodes :: Graph n t -> Int

Number of nodes in graph

numEdges :: Graph n t -> Int

Total number of edges in graph

hasNode :: Ord n => Graph n t -> n -> Bool

hasEdge :: Ord n => Graph n t -> (n, n) -> Bool

nodeInputs :: Ord n => Graph n t -> n -> [n]

nodeInEdges :: Ord n => Graph n t -> n -> [(n, Bool)]

nodeType :: Ord n => Graph n t -> n -> Maybe t

Find type, or iteration size, of node, if it has one. An external can't be represented as a loop, so it will be Nothing. Similarly with input nodes.

listOfGraph :: Graph n t -> ([(n, Maybe t)], [((n, n), Bool)])

Convert Graph to a lists of nodes and a list of edges

graphOfList :: Ord n => ([(n, Maybe t)], [((n, n), Bool)]) -> Graph n t

Convert lists of nodes and list of edges to a Graph