| Safe Haskell | Safe |
|---|---|
| Language | Haskell98 |
DDC.Core.Llvm.Metadata.Graph
- 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 :: 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
An undirected graph.
A directed graph.
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 a Source #
Find the transitive closure of a binary relation using Floyd-Warshall algorithm
transOrient :: (Show a, Ord a) => UG a -> DG a Source #
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