ghc-8.2.1: The GHC API

Safe Haskell None Haskell2010

Digraph

Synopsis

# Documentation

data Graph node Source #

Instances

 Outputable node => Outputable (Graph node) Source # Methodsppr :: Graph node -> SDoc Source #pprPrec :: Rational -> 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 #

data SCC vertex :: * -> * #

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

 Methodsfmap :: (a -> b) -> SCC a -> SCC b #(<\$) :: a -> SCC b -> SCC a # Methodsfold :: Monoid m => SCC m -> 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 # Methodstraverse :: 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) # MethodsliftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool # MethodsliftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (SCC a) #liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [SCC a] #liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (SCC a) #liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [SCC a] # MethodsliftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SCC a -> ShowS #liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SCC a] -> ShowS # Eq vertex => Eq (SCC vertex) Methods(==) :: SCC vertex -> SCC vertex -> Bool #(/=) :: SCC vertex -> SCC vertex -> Bool # Data vertex => Data (SCC vertex) Methodsgfoldl :: (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 :: (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) # Read vertex => Read (SCC vertex) MethodsreadsPrec :: Int -> ReadS (SCC vertex) #readList :: ReadS [SCC vertex] #readPrec :: ReadPrec (SCC vertex) #readListPrec :: ReadPrec [SCC vertex] # Show vertex => Show (SCC vertex) MethodsshowsPrec :: Int -> SCC vertex -> ShowS #show :: SCC vertex -> String #showList :: [SCC vertex] -> ShowS # Generic (SCC vertex) Associated Typestype Rep (SCC vertex) :: * -> * # Methodsfrom :: SCC vertex -> Rep (SCC vertex) x #to :: Rep (SCC vertex) x -> SCC vertex # NFData a => NFData (SCC a) Methodsrnf :: SCC a -> () # Outputable a => Outputable (SCC a) Source # Methodsppr :: SCC a -> SDoc Source #pprPrec :: Rational -> SCC a -> SDoc Source # Associated Typestype Rep1 SCC (f :: SCC -> *) :: k -> * # Methodsfrom1 :: f a -> Rep1 SCC f a #to1 :: Rep1 SCC f a -> f a # type Rep (SCC vertex) type Rep (SCC vertex) = D1 * (MetaData "SCC" "Data.Graph" "containers-0.5.10.2" False) ((:+:) * (C1 * (MetaCons "AcyclicSCC" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * vertex))) (C1 * (MetaCons "CyclicSCC" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * [vertex])))) type Rep1 * SCC type Rep1 * SCC = D1 * (MetaData "SCC" "Data.Graph" "containers-0.5.10.2" False) ((:+:) * (C1 * (MetaCons "AcyclicSCC" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1)) (C1 * (MetaCons "CyclicSCC" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 * []))))

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

flattenSCC :: SCC vertex -> [vertex] #

The vertices of a strongly connected component.

flattenSCCs :: [SCC a] -> [a] #

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.

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 #