ghc-9.13: The GHC API
Safe HaskellNone
LanguageGHC2021

GHC.Data.Graph.Directed

Synopsis

Documentation

data Graph node Source #

Instances

Instances details
Outputable node => Outputable (Graph node) Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

ppr :: Graph node -> SDoc Source #

graphFromEdgedVerticesOrd :: Ord key => [Node key payload] -> Graph (Node key payload) 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 #

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

Since: containers-0.7.0

Bundled Patterns

pattern CyclicSCC :: [vertex] -> SCC vertex

Partial pattern synonym for backward compatibility with containers < 0.7.

Instances

Instances details
Foldable1 SCC Source #

Since: containers-0.7.0

Instance details

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 #

head :: SCC a -> a Source #

last :: 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 Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

liftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool Source #

Read1 SCC Source #

Since: containers-0.5.9

Instance details

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 Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SCC a -> ShowS Source #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SCC a] -> ShowS Source #

Functor SCC Source #

Since: containers-0.5.4

Instance details

Defined in Data.Graph

Methods

fmap :: (a -> b) -> SCC a -> SCC b #

(<$) :: a -> SCC b -> SCC a #

Foldable SCC Source #

Since: containers-0.5.9

Instance details

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 #

toList :: SCC a -> [a] #

null :: SCC a -> Bool #

length :: SCC a -> Int #

elem :: Eq a => a -> SCC a -> Bool #

maximum :: Ord a => SCC a -> a #

minimum :: Ord a => SCC a -> a #

sum :: Num a => SCC a -> a #

product :: Num a => SCC a -> a #

Traversable SCC Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

traverse :: Applicative f => (a -> f b) -> SCC a -> f (SCC b) #

sequenceA :: Applicative f => SCC (f a) -> f (SCC a) #

mapM :: Monad m => (a -> m b) -> SCC a -> m (SCC b) #

sequence :: Monad m => SCC (m a) -> m (SCC a) #

Generic1 SCC Source # 
Instance details

Defined in Data.Graph

Associated Types

type Rep1 SCC

Since: containers-0.5.9

Instance details

Defined in Data.Graph

type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-inplace" '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)))

Methods

from1 :: SCC a -> Rep1 SCC a #

to1 :: Rep1 SCC a -> SCC a #

OutputableP env a => OutputableP env (SCC a) Source # 
Instance details

Defined in GHC.Utils.Outputable

Methods

pdoc :: env -> SCC a -> SDoc Source #

Lift vertex => Lift (SCC vertex :: Type)

Since: containers-0.6.6

Instance details

Defined in Data.Graph

Methods

lift :: Quote m => SCC vertex -> m Exp

liftTyped :: forall (m :: Type -> Type). Quote m => SCC vertex -> Code m (SCC vertex)

NFData a => NFData (SCC a) Source # 
Instance details

Defined in Data.Graph

Methods

rnf :: SCC a -> () Source #

Outputable a => Outputable (SCC a) Source # 
Instance details

Defined in GHC.Utils.Outputable

Methods

ppr :: SCC a -> SDoc Source #

Data vertex => Data (SCC vertex) Source #

Since: containers-0.5.9

Instance details

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) Source # 
Instance details

Defined in Data.Graph

Associated Types

type Rep (SCC vertex)

Since: containers-0.5.9

Instance details

Defined in Data.Graph

type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-inplace" '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))))

Methods

from :: SCC vertex -> Rep (SCC vertex) x #

to :: Rep (SCC vertex) x -> SCC vertex #

Read vertex => Read (SCC vertex) Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

readsPrec :: Int -> ReadS (SCC vertex) #

readList :: ReadS [SCC vertex] #

readPrec :: ReadPrec (SCC vertex) #

readListPrec :: ReadPrec [SCC vertex] #

Show vertex => Show (SCC vertex) Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

showsPrec :: Int -> SCC vertex -> ShowS #

show :: SCC vertex -> String #

showList :: [SCC vertex] -> ShowS #

Eq vertex => Eq (SCC vertex) Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

Methods

(==) :: SCC vertex -> SCC vertex -> Bool #

(/=) :: SCC vertex -> SCC vertex -> Bool #

type Rep1 SCC Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-inplace" '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) Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers-0.7-inplace" '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 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 

Fields

Instances

Instances details
Functor (Node key) Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

fmap :: (a -> b) -> Node key a -> Node key b #

(<$) :: a -> Node key b -> Node key a #

(Outputable a, Outputable b) => Outputable (Node a b) Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

ppr :: Node a b -> SDoc 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 #

verticesG :: Graph node -> [node] Source #

edgesG :: Graph node -> [Edge 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.

outgoingG :: Graph node -> node -> [node] Source #

emptyG :: Graph node -> Bool Source #

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.

stronglyConnCompFromEdgedVerticesOrd :: Ord key => [Node key payload] -> [SCC payload] Source #

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 #

data 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

Instances

Instances details
Outputable EdgeType Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

ppr :: EdgeType -> SDoc Source #

Eq EdgeType Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

(==) :: EdgeType -> EdgeType -> Bool #

(/=) :: EdgeType -> EdgeType -> Bool #

Ord EdgeType Source # 
Instance details

Defined in GHC.Data.Graph.Directed

Methods

compare :: EdgeType -> EdgeType -> Ordering #

(<) :: EdgeType -> EdgeType -> Bool #

(<=) :: EdgeType -> EdgeType -> Bool #

(>) :: EdgeType -> EdgeType -> Bool #

(>=) :: EdgeType -> EdgeType -> Bool #

max :: EdgeType -> EdgeType -> EdgeType #

min :: EdgeType -> EdgeType -> EdgeType #

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.