HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduleghc-9.10.3GHC2021

GHC.Data.Graph.Directed

  • 4 types
  • 23 values
  • Packageghc-9.10.3
  • Exports28
  • LanguageGHC2021
  • LicenceBSD-3-Clause
  • SourceGraph.hs
datadata SCC vertex
#

Strongly connected component.

Constructors

Instances19Functor, Foldable, Traversable, Foldable1, Eq1, Read1, …
patternpattern CyclicSCC :: [vertex] -> SCC vertex
#

Partial pattern synonym for backward compatibility with containers < 0.7.

datadata Node key payload
#

Representation for nodes of the Graph.

  • The payload is user data, just carried around in this module

  • The key is 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

Instances2Functor, Outputable
valueflattenSCC :: SCC vertex -> [vertex]
#

The vertices of a strongly connected component.

valueflattenSCCs :: [SCC a] -> [a]
#

The vertices of a list of strongly connected components.

valuereachablesG :: Graph node -> [node] -> [node]
#

Given a list of roots return all reachable nodes.

valueallReachable :: Ord key => Graph node -> (node -> key) -> Map key (Set key)
#

Efficiently construct a map which maps each key to it's set of transitive dependencies. Only works on acyclic input.

valueallReachableCyclic
  1. :: Ord key
  2. => Graph node
  3. -> node -> key
  4. -> Map key (Set key)
#

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.

valuefindCycle :: Ord key => [Node key payload] -> Maybe [payload]
#

Find a reasonably short cycle a->b->c->a, in a graph The graph might not necessarily be strongly connected.

datadata EdgeType
#

Edge direction based on DFS Classification

Constructors

Instances3Eq, Ord, Outputable
valueclassifyEdges
  1. :: Uniquable key
  2. => key
  3. -> key -> [key]
  4. -> [(key, key)]
  5. -> [((key, key), EdgeType)]
#

Given a start vertex, a way to get successors from a node and a list of (directed) edges classify the types of edges.