Moduleghc-10.0.0.20260917GHC2024

GHC.Data.Graph.Directed

Synopsis

data Graph
value graphFromEdgedVerticesOrd
value graphFromEdgedVerticesUniq
value graphFromVerticesAndAdjacency
value emptyGraph
data SCC
pattern CyclicSCC
data Node
value flattenSCC
value flattenSCCs
value stronglyConnCompG
value topologicalSortG
value verticesG
value edgesG
value hasVertexG
value reachablesG
value transposeG
value outgoingG
value emptyG
value findCycle
value stronglyConnCompFromEdgedVerticesOrd
value stronglyConnCompFromEdgedVerticesOrdR
value stronglyConnCompFromEdgedVerticesUniq
value stronglyConnCompFromEdgedVerticesUniqR
data EdgeType
value classifyEdges

Packageghc-10.0.0.20260917
Exports26
LanguageGHC2024
LicenceBSD-3-Clause
SourceGraph.hs

datadata Graph node

Instances1Outputable

Outputable node => Outputable (Graph node)Defined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed.Internal

valuegraphFromEdgedVerticesOrd

:: Ord key
=> [Node key payload]
-> Graph (Node key payload)

valuegraphFromEdgedVerticesUniq

:: Uniquable key
=> [Node key payload]
-> Graph (Node key payload)

valuegraphFromVerticesAndAdjacency

:: Ord key
=> [Node key payload]
-> [(key, key)]
-> Graph (Node key payload)

valueemptyGraph :: Graph a

datadata SCC vertex

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.

Instances20Functor, Foldable, Traversable, Foldable1, Eq1, Read1, …

Functor SCCDefined in containers-0.8 · Data.Graph
Foldable SCCDefined in containers-0.8 · Data.Graph
Traversable SCCDefined in containers-0.8 · Data.Graph
Foldable1 SCCDefined in containers-0.8 · Data.Graph
Eq1 SCCDefined in containers-0.8 · Data.Graph
Read1 SCCDefined in containers-0.8 · Data.Graph
Show1 SCCDefined in containers-0.8 · Data.Graph
NFData1 SCCDefined in containers-0.8 · Data.Graph
Generic1 SCCDefined in containers-0.8 · Data.Graph
Lift vertex => Lift (SCC vertex)Defined in containers-0.8 · Data.Graph
OutputableP env a => OutputableP env (SCC a)Defined in ghc-10.0.0.20260917 · GHC.Utils.Outputable
Eq vertex => Eq (SCC vertex)Defined in containers-0.8 · Data.Graph
Data vertex => Data (SCC vertex)Defined in containers-0.8 · Data.Graph
Read vertex => Read (SCC vertex)Defined in containers-0.8 · Data.Graph
Show vertex => Show (SCC vertex)Defined in containers-0.8 · Data.Graph
Generic (SCC vertex)Defined in containers-0.8 · Data.Graph
NFData a => NFData (SCC a)Defined in containers-0.8 · Data.Graph
Outputable a => Outputable (SCC a)Defined in ghc-10.0.0.20260917 · GHC.Utils.Outputable
type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.8-65e2" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 vertex)) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec0 (NonEmpty vertex))))Defined in containers-0.8 · Data.Graph
type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.8-65e2" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec1 NonEmpty)))Defined in containers-0.8 · Data.Graph

patternpattern CyclicSCC :: [vertex] -> SCC vertex

Source#

Partial pattern synonym for backward compatibility with containers < 0.7.

datadata Node key payload

Source#

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

DigraphNode
- node_payload :: payload
  User data
- node_key :: key
  User defined node id
- node_dependencies :: [key]
  Dependencies/successors of the node

Instances2Functor, Outputable

Functor (Node key)Defined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed
(Outputable a, Outputable b) => Outputable (Node a b)Defined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed

valueflattenSCC :: SCC vertex -> [vertex]

Source#

The vertices of a strongly connected component.

flattenSCC = toList . flattenSCC1.

This function is retained for backward compatibility, flattenSCC1 has the more precise type.

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

Source#

The vertices of a list of strongly connected components.

valuestronglyConnCompG :: Graph node -> [SCC node]

valuetopologicalSortG :: Graph node -> [node]

valueverticesG :: Graph node -> [node]

valueedgesG :: Graph node -> [Edge node]

valuehasVertexG :: Graph node -> node -> Bool

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

Source#

Given a list of roots, return all reachable nodes in topological order. Implemented using a depth-first traversal.

valuetransposeG :: Graph node -> Graph node

valueoutgoingG :: Graph node -> node -> [node]

valueemptyG :: Graph node -> Bool

valuefindCycle :: 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.

valuestronglyConnCompFromEdgedVerticesOrd

:: Ord key
=> [Node key payload]
-> [SCC payload]

valuestronglyConnCompFromEdgedVerticesOrdR

:: Ord key
=> [Node key payload]
-> [SCC (Node key payload)]

valuestronglyConnCompFromEdgedVerticesUniq

:: Uniquable key
=> [Node key payload]
-> [SCC payload]

valuestronglyConnCompFromEdgedVerticesUniqR

:: Uniquable key
=> [Node key payload]
-> [SCC (Node key payload)]

datadata EdgeType

Source#

Edge direction based on DFS Classification

Constructors

Forward
Cross
Backward
Loop back towards the root node. Eg backjumps in loops
SelfLoop
v -> v

Instances3Eq, Ord, Outputable

Eq EdgeTypeDefined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed
Ord EdgeTypeDefined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed
Outputable EdgeTypeDefined in ghc-10.0.0.20260917 · GHC.Data.Graph.Directed

valueclassifyEdges

:: 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.