| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Graph.Libgraph
- data Graph vertex arc = Graph {}
- data Arc vertex arc = Arc {}
- (-->) :: vertex -> vertex -> SimpleArc vertex
- succs :: Eq vertex => Graph vertex arc -> vertex -> [vertex]
- preds :: Eq vertex => Graph vertex arc -> vertex -> [vertex]
- isSucc :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool
- isPred :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool
- mapGraph :: (a -> b) -> Graph a c -> Graph b c
- mapArcs :: (a -> b) -> Graph c a -> Graph c b
- data Dfs vertex arc
- data EdgeType
- getDfs :: Eq vertex => Graph vertex arc -> Dfs vertex arc
- getEdgetype :: (Eq vertex, Show vertex) => Dfs vertex arc -> Arc vertex arc -> EdgeType
- getPreorder :: Dfs vertex arc -> [vertex]
- getPostorder :: Dfs vertex arc -> [vertex]
- isAncestor :: (Eq vertex, Show vertex) => Dfs vertex arc -> vertex -> vertex -> Maybe Bool
- data Domsets vertex arc
- getDomsets :: Eq vertex => Graph vertex arc -> Domsets vertex arc
- getDominators :: Eq vertex => vertex -> Domsets vertex arc -> [vertex]
- data CycleTree vertex
- getCycles :: Ord vertex => CycleNest vertex -> CycleTree vertex
- getRedHeaders :: CycleNest vertex -> [vertex]
- dagify :: (Ord v, Eq a, Show v) => ([v] -> v) -> Graph v a -> Graph v a
- findFaulty :: (Ord v, Eq a, Show v) => (v -> Judgement) -> ([v] -> v) -> Graph v a -> [v]
- findFaulty_dag :: (Ord v, Eq a, Show v) => (v -> Judgement) -> Graph v a -> [v]
- next_step :: Eq v => Graph v a -> (v -> Judgement) -> v
- next_daq :: Ord v => Graph v a -> (v -> Judgement) -> v
- data Judgement
- = Right
- | Wrong
- | Unassessed
- | Assisted [AssistedMessage]
- data AssistedMessage
- showWith :: Eq vertex => Graph vertex arc -> (vertex -> (String, String)) -> (Arc vertex arc -> String) -> String
- escape :: String -> String
- display :: (Graph vertex arc -> String) -> Graph vertex arc -> IO ()
- collapse :: (Show v, Ord v, Eq a) => ([v] -> v) -> Graph v a -> Graph v a
- remove :: (Ord v, Show v) => Graph v a -> Graph v a
- treeDepth :: Ord v => Graph v a -> Int
- succCache :: Ord vertex => Graph vertex arc -> vertex -> [vertex]
- predCache :: Ord vertex => Graph vertex arc -> vertex -> [vertex]
Documentation
preds :: Eq vertex => Graph vertex arc -> vertex -> [vertex] Source #
Direct predecessors of a vertex.
isSucc :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool Source #
Is first vertex a successor of second?
isPred :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool Source #
Is first vertex a predecessor of second?
getDfs :: Eq vertex => Graph vertex arc -> Dfs vertex arc Source #
Walk graph in depth-first order and number the vertices.
getPreorder :: Dfs vertex arc -> [vertex] Source #
Get list of vertices in the order they were visited by the depth-first search.
getPostorder :: Dfs vertex arc -> [vertex] Source #
Get list of vertices in the order they were last visited by the depth-first search.
isAncestor :: (Eq vertex, Show vertex) => Dfs vertex arc -> vertex -> vertex -> Maybe Bool Source #
Is first vertex a (recursive) parent of second vertex? May fail when one of the vertices is unreachable from the root.
getDomsets :: Eq vertex => Graph vertex arc -> Domsets vertex arc Source #
Compute dominator sets. N.B. currently a naive algorithm is implemented with time-complexity O(vertex^2).
getDominators :: Eq vertex => vertex -> Domsets vertex arc -> [vertex] Source #
Vertices dominating the vertex given as argument.
getRedHeaders :: CycleNest vertex -> [vertex] Source #
Entry vertices of reducible cycles.
Constructors
| Right | |
| Wrong | |
| Unassessed | |
| Assisted [AssistedMessage] |
data AssistedMessage Source #
Constructors
| InconclusiveProperty String | |
| PassingProperty String |
Instances
showWith :: Eq vertex => Graph vertex arc -> (vertex -> (String, String)) -> (Arc vertex arc -> String) -> String Source #
Convert Graph to String with functions to show vertices and arcs.