Safe Haskell | Safe-Inferred |
---|

- newtype UG a = UG (Dom a, Rel a)
- newtype DG a = DG (Dom a, Rel a)
- orientUG :: (Show a, Ord a) => UG a -> DG a
- partitionDG :: Eq a => DG a -> [Tree a]
- newtype Tree a = Tree (Dom a, Rel a)
- sources :: Eq a => a -> Tree a -> [a]
- anchor :: Eq a => a -> Tree a -> Tree a
- type Dom a = [a]
- type Rel a = a -> a -> Bool
- fromList :: Eq a => [(a, a)] -> Rel a
- toList :: Dom a -> Rel a -> [(a, a)]
- transClosure :: Eq a => Dom a -> Rel a -> Rel a
- transOrient :: (Show a, Ord a) => UG a -> DG a
- aliasMeasure :: Eq a => Rel a -> Partitioning a -> Int
- isTree :: Dom a -> Rel a -> Bool

# Graphs and Trees for TBAA metadata

partitionDG :: Eq a => DG a -> [Tree a]Source

Partition a DG into the minimum set of (directed) trees

An inverted tree (with edges going from child to parent)

# Quickcheck Testing ONLY

transClosure :: Eq a => Dom a -> Rel a -> Rel aSource

Find the transitive closure of a binary relation using Floyd-Warshall algorithm

transOrient :: (Show a, Ord a) => UG a -> DG aSource

Transitively orient an undireted graph

Using the algorithm from Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, R. McConnell et al 2000

In the case where the transitive orientation does not exist, it simply gives some orientation

note: gave up on modular decomposition, this approach has very slightly worse time complexity but much simpler

aliasMeasure :: Eq a => Rel a -> Partitioning a -> IntSource

Calculate the aliasing induced by a set of trees this includes aliasing within each of the trees and aliasing among trees.