| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
GHC.Data.Graph.Directed
Synopsis
- data Graph node
- graphFromEdgedVerticesOrd :: Ord key => [Node key payload] -> Graph (Node key payload)
- graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload)
- graphFromVerticesAndAdjacency :: Ord key => [Node key payload] -> [(key, key)] -> Graph (Node key payload)
- data SCC vertex where
- AcyclicSCC vertex
- NECyclicSCC !(NonEmpty vertex)
- pattern CyclicSCC :: [vertex] -> SCC vertex
- data Node key payload = DigraphNode {
- node_payload :: payload
- node_key :: key
- node_dependencies :: [key]
- flattenSCC :: SCC vertex -> [vertex]
- flattenSCCs :: [SCC a] -> [a]
- stronglyConnCompG :: Graph node -> [SCC node]
- topologicalSortG :: Graph node -> [node]
- verticesG :: Graph node -> [node]
- edgesG :: Graph node -> [Edge node]
- hasVertexG :: Graph node -> node -> Bool
- reachableG :: Graph node -> node -> [node]
- reachablesG :: Graph node -> [node] -> [node]
- transposeG :: Graph node -> Graph node
- allReachable :: Ord key => Graph node -> (node -> key) -> Map key (Set key)
- allReachableCyclic :: Ord key => Graph node -> (node -> key) -> Map key (Set key)
- outgoingG :: Graph node -> node -> [node]
- emptyG :: Graph node -> Bool
- findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload]
- stronglyConnCompFromEdgedVerticesOrd :: Ord key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesOrdR :: Ord key => [Node key payload] -> [SCC (Node key payload)]
- stronglyConnCompFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesUniqR :: Uniquable key => [Node key payload] -> [SCC (Node key payload)]
- data EdgeType
- classifyEdges :: Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)]
Documentation
Instances
| Outputable node => Outputable (Graph node) Source # | |
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload) Source #
graphFromVerticesAndAdjacency :: Ord key => [Node key payload] -> [(key, key)] -> Graph (Node key payload) Source #
Strongly connected component.
Constructors
| AcyclicSCC vertex | A single vertex that is not in any cycle. |
| NECyclicSCC !(NonEmpty vertex) | A maximal set of mutually reachable vertices. Since: containers-0.7.0 |
Bundled Patterns
| pattern CyclicSCC :: [vertex] -> SCC vertex | Partial pattern synonym for backward compatibility with |
Instances
| Foldable1 SCC | Since: containers-0.7.0 | ||||
Defined in Data.Graph Methods fold1 :: Semigroup m => SCC m -> m Source # foldMap1 :: Semigroup m => (a -> m) -> SCC a -> m Source # foldMap1' :: Semigroup m => (a -> m) -> SCC a -> m Source # toNonEmpty :: SCC a -> NonEmpty a Source # maximum :: Ord a => SCC a -> a Source # minimum :: Ord a => SCC a -> a Source # foldrMap1 :: (a -> b) -> (a -> b -> b) -> SCC a -> b Source # foldlMap1' :: (a -> b) -> (b -> a -> b) -> SCC a -> b Source # foldlMap1 :: (a -> b) -> (b -> a -> b) -> SCC a -> b Source # foldrMap1' :: (a -> b) -> (a -> b -> b) -> SCC a -> b Source # | |||||
| Eq1 SCC | Since: containers-0.5.9 | ||||
| Read1 SCC | Since: containers-0.5.9 | ||||
Defined in Data.Graph Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (SCC a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SCC a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SCC a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SCC a] Source # | |||||
| Show1 SCC | Since: containers-0.5.9 | ||||
| Functor SCC | Since: containers-0.5.4 | ||||
| Foldable SCC | Since: containers-0.5.9 | ||||
Defined in Data.Graph Methods fold :: Monoid m => SCC m -> m # foldMap :: Monoid m => (a -> m) -> SCC a -> m # foldMap' :: Monoid m => (a -> m) -> SCC a -> m # foldr :: (a -> b -> b) -> b -> SCC a -> b # foldr' :: (a -> b -> b) -> b -> SCC a -> b # foldl :: (b -> a -> b) -> b -> SCC a -> b # foldl' :: (b -> a -> b) -> b -> SCC a -> b # foldr1 :: (a -> a -> a) -> SCC a -> a # foldl1 :: (a -> a -> a) -> SCC a -> a # elem :: Eq a => a -> SCC a -> Bool # maximum :: Ord a => SCC a -> a # | |||||
| Traversable SCC | Since: containers-0.5.9 | ||||
| Generic1 SCC | |||||
Defined in Data.Graph Associated Types
| |||||
| OutputableP env a => OutputableP env (SCC a) Source # | |||||
| Lift vertex => Lift (SCC vertex :: Type) | Since: containers-0.6.6 | ||||
| NFData a => NFData (SCC a) | |||||
Defined in Data.Graph | |||||
| Outputable a => Outputable (SCC a) Source # | |||||
| Data vertex => Data (SCC vertex) | Since: containers-0.5.9 | ||||
Defined in Data.Graph Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex) # toConstr :: SCC vertex -> Constr # dataTypeOf :: SCC vertex -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex)) # gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r # gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) # | |||||
| Generic (SCC vertex) | |||||
Defined in Data.Graph Associated Types
| |||||
| Read vertex => Read (SCC vertex) | Since: containers-0.5.9 | ||||
| Show vertex => Show (SCC vertex) | Since: containers-0.5.9 | ||||
| Eq vertex => Eq (SCC vertex) | Since: containers-0.5.9 | ||||
| type Rep1 SCC | Since: containers-0.5.9 | ||||
Defined in Data.Graph type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-cfc3" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec1 NonEmpty))) | |||||
| type Rep (SCC vertex) | Since: containers-0.5.9 | ||||
Defined in Data.Graph type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-cfc3" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 vertex)) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec0 (NonEmpty vertex)))) | |||||
data Node key payload Source #
Representation for nodes of the Graph.
- The
payloadis user data, just carried around in this module - The
keyis the node identifier. Key has an Ord instance for performance reasons. - The
[key]are the dependencies of the node; it's ok to have extra keys in the dependencies that are not the key of any Node in the graph
Constructors
| DigraphNode | |
Fields
| |
Instances
| Functor (Node key) Source # | |
| (Outputable a, Outputable b) => Outputable (Node a b) Source # | |
flattenSCC :: SCC vertex -> [vertex] Source #
The vertices of a strongly connected component.
flattenSCCs :: [SCC a] -> [a] Source #
The vertices of a list of strongly connected components.
stronglyConnCompG :: Graph node -> [SCC node] Source #
topologicalSortG :: Graph node -> [node] Source #
hasVertexG :: Graph node -> node -> Bool Source #
reachableG :: Graph node -> node -> [node] Source #
reachablesG :: Graph node -> [node] -> [node] Source #
Given a list of roots return all reachable nodes.
transposeG :: Graph node -> Graph node Source #
allReachable :: Ord key => Graph node -> (node -> key) -> Map key (Set key) Source #
Efficiently construct a map which maps each key to it's set of transitive dependencies. Only works on acyclic input.
allReachableCyclic :: Ord key => Graph node -> (node -> key) -> Map key (Set key) Source #
Efficiently construct a map which maps each key to it's set of transitive
dependencies. Less efficient than allReachable, but works on cyclic input as well.
findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload] Source #
Find a reasonably short cycle a->b->c->a, in a graph The graph might not necessarily be strongly connected.
stronglyConnCompFromEdgedVerticesOrdR :: Ord key => [Node key payload] -> [SCC (Node key payload)] Source #
stronglyConnCompFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> [SCC payload] Source #
stronglyConnCompFromEdgedVerticesUniqR :: Uniquable key => [Node key payload] -> [SCC (Node key payload)] Source #
Edge direction based on DFS Classification
Constructors
| Forward | |
| Cross | |
| Backward | Loop back towards the root node. Eg backjumps in loops |
| SelfLoop | v -> v |
classifyEdges :: Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)] Source #
Given a start vertex, a way to get successors from a node and a list of (directed) edges classify the types of edges.