- data Graph n t = Graph (Map n (Maybe t, [Edge n]))
- type Edge n = (n, Bool)
- graphOfBinds :: (Ord s, Ord a) => Program s a -> Env a -> Graph (CName s a) (Type a)
- graphTopoOrder :: Ord n => Graph n t -> [n]
- mergeWeights :: Ord n => Graph n t -> Map n Int -> Graph n ()
- invertMap :: Ord v => Map k v -> Map v [k]
- numNodes :: Graph n t -> Int
- numEdges :: Graph n t -> Int
- 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
- listOfGraph :: Graph n t -> ([(n, Maybe t)], [((n, n), Bool)])
- graphOfList :: Ord n => ([(n, Maybe t)], [((n, n), Bool)]) -> Graph n t
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.
Find topological ordering of DAG Does not check for cycles - really must be a DAG!
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.
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.
Graph to a lists of nodes and a list of edges