| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Graph.Libgraph
Synopsis
- 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
Instances
| Generic (Graph vertex arc) # | |
| type Rep (Graph vertex arc) # | |
Defined in Data.Graph.Libgraph.Core type Rep (Graph vertex arc) = D1 (MetaData "Graph" "Data.Graph.Libgraph.Core" "libgraph-1.14-IjYxzy2QWeQJJ5hFS641UW" False) (C1 (MetaCons "Graph" PrefixI True) (S1 (MetaSel (Just "root") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 vertex) :*: (S1 (MetaSel (Just "vertices") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [vertex]) :*: S1 (MetaSel (Just "arcs") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [Arc vertex arc])))) | |
Instances
| (Eq vertex, Eq arc) => Eq (Arc vertex arc) # | |
| (Show vertex, Show arc) => Show (Arc vertex arc) # | |
| Generic (Arc vertex arc) # | |
| type Rep (Arc vertex arc) # | |
Defined in Data.Graph.Libgraph.Core type Rep (Arc vertex arc) = D1 (MetaData "Arc" "Data.Graph.Libgraph.Core" "libgraph-1.14-IjYxzy2QWeQJJ5hFS641UW" False) (C1 (MetaCons "Arc" PrefixI True) (S1 (MetaSel (Just "source") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 vertex) :*: (S1 (MetaSel (Just "target") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 vertex) :*: S1 (MetaSel (Just "arc") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 arc)))) | |
isSucc :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool #
Is first vertex a successor of second?
isPred :: Eq vertex => Graph vertex arc -> vertex -> vertex -> Bool #
Is first vertex a predecessor of second?
getDfs :: Eq vertex => Graph vertex arc -> Dfs vertex arc #
Walk graph in depth-first order and number the vertices.
getPreorder :: Dfs vertex arc -> [vertex] #
Get list of vertices in the order they were visited by the depth-first search.
getPostorder :: Dfs vertex arc -> [vertex] #
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 #
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 #
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] #
Vertices dominating the vertex given as argument.
getRedHeaders :: CycleNest vertex -> [vertex] #
Entry vertices of reducible cycles.
Constructors
| Right | |
| Wrong | |
| Unassessed | |
| Assisted [AssistedMessage] |
Instances
| Eq Judgement # | |
| Ord Judgement # | |
| Show Judgement # | |
| Generic Judgement # | |
| type Rep Judgement # | |
Defined in Data.Graph.Libgraph.AlgoDebug type Rep Judgement = D1 (MetaData "Judgement" "Data.Graph.Libgraph.AlgoDebug" "libgraph-1.14-IjYxzy2QWeQJJ5hFS641UW" False) ((C1 (MetaCons "Right" PrefixI False) (U1 :: * -> *) :+: C1 (MetaCons "Wrong" PrefixI False) (U1 :: * -> *)) :+: (C1 (MetaCons "Unassessed" PrefixI False) (U1 :: * -> *) :+: C1 (MetaCons "Assisted" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [AssistedMessage])))) | |
data AssistedMessage #
Constructors
| InconclusiveProperty String | |
| PassingProperty String |
Instances
showWith :: Eq vertex => Graph vertex arc -> (vertex -> (String, String)) -> (Arc vertex arc -> String) -> String #
Convert Graph to String with functions to show vertices and arcs.