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)
emptyGraph :: Graph a
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
reachablesG :: Graph node -> [node] -> [node]
transposeG :: Graph node -> Graph node
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
- = Forward
- | Cross
- | Backward
- | SelfLoop
classifyEdges :: Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)]

Documentation

data Graph node Source #

Instances

Instances details

Outputable node => Outputable (Graph node) Source #
Instance details Defined in GHC.Data.Graph.Directed.Internal 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 #

emptyGraph :: Graph a 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 Rep (SCC vertex) Source #

Since: containers-0.5.9

Instance details

Defined in Data.Graph

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 node_payload :: payload User data node_key :: key User defined node id node_dependencies :: [key] Dependencies/successors of the node

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 #

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

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

transposeG :: Graph node -> Graph node Source #

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.