ghc-8.0.1: The GHC API

Safe HaskellNone
LanguageHaskell2010

Digraph

Synopsis

Documentation

data Graph node Source #

Instances

Outputable node => Outputable (Graph node) # 

Methods

ppr :: Graph node -> SDoc Source #

pprPrec :: Rational -> Graph node -> SDoc Source #

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

data SCC vertex :: * -> * Source #

Strongly connected component.

Constructors

AcyclicSCC vertex

A single vertex that is not in any cycle.

CyclicSCC [vertex]

A maximal set of mutually reachable vertices.

Instances

Functor SCC 

Methods

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

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

NFData a => NFData (SCC a) 

Methods

rnf :: SCC a -> ()

Outputable a => Outputable (SCC a) # 

Methods

ppr :: SCC a -> SDoc Source #

pprPrec :: Rational -> SCC a -> SDoc Source #

type Node key payload = (payload, key, [key]) 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 #

dfsTopSortG :: 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 #

transposeG :: Graph node -> Graph node Source #

outdegreeG :: Graph node -> node -> Maybe Int Source #

indegreeG :: Graph node -> node -> Maybe Int Source #

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

emptyG :: Graph node -> Bool Source #

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

findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload] Source #

Find a reasonably short cycle a->b->c->a, in a strongly connected component. The input nodes are presumed to be a SCC, so you can start anywhere.

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

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