ghc-8.0.2: The GHC API

Safe HaskellNone
LanguageHaskell2010

Digraph

Synopsis

Documentation

data Graph node #

Instances

Outputable node => Outputable (Graph node) # 

Methods

ppr :: Graph node -> SDoc #

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

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

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

Outputable a => Outputable (SCC a) # 

Methods

ppr :: SCC a -> SDoc #

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

type Node key payload = (payload, key, [key]) #

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

topologicalSortG :: Graph node -> [node] #

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

verticesG :: Graph node -> [node] #

edgesG :: Graph node -> [Edge node] #

hasVertexG :: Graph node -> node -> Bool #

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

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

transposeG :: Graph node -> Graph node #

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

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

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

emptyG :: Graph node -> Bool #

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

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

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

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