Safe Haskell | None |
---|---|

Language | Haskell98 |

- data AlgebraDag a
- class (Ord a, Show a) => Operator a where
- opChildren :: a -> [AlgNode]
- replaceOpChild :: a -> AlgNode -> AlgNode -> a

- nodeMap :: AlgebraDag a -> NodeMap a
- rootNodes :: AlgebraDag a -> [AlgNode]
- refCountMap :: AlgebraDag a -> NodeMap Int
- mkDag :: Operator a => NodeMap a -> [AlgNode] -> AlgebraDag a
- emptyDag :: AlgebraDag a
- addRootNodes :: Operator a => AlgebraDag a -> [AlgNode] -> AlgebraDag a
- parents :: AlgNode -> AlgebraDag a -> [AlgNode]
- topsort :: Operator a => AlgebraDag a -> [AlgNode]
- hasPath :: AlgNode -> AlgNode -> AlgebraDag a -> Bool
- reachableNodesFrom :: AlgNode -> AlgebraDag a -> Set AlgNode
- operator :: Operator a => AlgNode -> AlgebraDag a -> a
- insert :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a)
- insertNoShare :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a)
- replaceChild :: Operator a => AlgNode -> AlgNode -> AlgNode -> AlgebraDag a -> AlgebraDag a
- replaceRoot :: Operator a => AlgebraDag a -> AlgNode -> AlgNode -> AlgebraDag a
- collect :: Operator o => Set AlgNode -> AlgebraDag o -> AlgebraDag o

# The DAG data structure

data AlgebraDag a Source

class (Ord a, Show a) => Operator a where Source

opChildren :: a -> [AlgNode] Source

replaceOpChild :: a -> AlgNode -> AlgNode -> a Source

nodeMap :: AlgebraDag a -> NodeMap a Source

Return the nodemap of a DAG

rootNodes :: AlgebraDag a -> [AlgNode] Source

Return the (possibly modified) list of root nodes from a DAG

refCountMap :: AlgebraDag a -> NodeMap Int Source

A map storing the number of parents for each node.

mkDag :: Operator a => NodeMap a -> [AlgNode] -> AlgebraDag a Source

Create a DAG from a node map of algebra operators and a list of root nodes. Nodes which are not reachable from the root nodes provided will be pruned!

emptyDag :: AlgebraDag a Source

Construct an empty DAG with no root nodes. Beware: before any collections are performed, root nodes must be added. Otherwise, all nodes will be considered unreachable.

addRootNodes :: Operator a => AlgebraDag a -> [AlgNode] -> AlgebraDag a Source

Add a list of root nodes to a DAG, all of which must be present in the DAG. The node map is normalized by removing all nodes which are not reachable from the root nodes. FIXME re-use graph, opmap etc, only remove pruned nodes.

# Query functions for topological and operator information

parents :: AlgNode -> AlgebraDag a -> [AlgNode] Source

Return the list of parents of a node.

topsort :: Operator a => AlgebraDag a -> [AlgNode] Source

Return a topological ordering of all nodes which are reachable from the root nodes.

hasPath :: AlgNode -> AlgNode -> AlgebraDag a -> Bool Source

Tests wether there is a path from the first to the second node.

reachableNodesFrom :: AlgNode -> AlgebraDag a -> Set AlgNode Source

Return all nodes that are reachable from one node.

operator :: Operator a => AlgNode -> AlgebraDag a -> a Source

Returns the operator for a node.

# DAG modification functions

insert :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a) Source

Insert a new node into the DAG.

insertNoShare :: Operator a => a -> AlgebraDag a -> (AlgNode, AlgebraDag a) Source

Insert an operator without checking if an equivalent operator is already present.

replaceChild :: Operator a => AlgNode -> AlgNode -> AlgNode -> AlgebraDag a -> AlgebraDag a Source

'replaceChild n old new' replaces all links from node n to node old with links to node new.

replaceRoot :: Operator a => AlgebraDag a -> AlgNode -> AlgNode -> AlgebraDag a Source

Replace an entry in the list of root nodes with a new node. The root node must be present in the DAG.

collect :: Operator o => Set AlgNode -> AlgebraDag o -> AlgebraDag o Source