Safe Haskell	None
Language	Haskell2010

Digraph

Synopsis

data Graph node
graphFromEdgedVerticesOrd :: Ord key => [Node key payload] -> Graph (Node key payload)
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload)
data SCC vertex :: * -> *
- = AcyclicSCC vertex
- | CyclicSCC [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]
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]
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)]

Documentation

data Graph node Source #

Instances

Outputable node => Outputable (Graph node) #
Instance details Methods ppr :: 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 :: * -> * 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
Instance details Methods fmap :: (a -> b) -> SCC a -> SCC b Source # (<$) :: a -> SCC b -> SCC a Source #
Foldable SCC
Instance details Methods fold :: Monoid m => SCC m -> m Source # foldMap :: Monoid m => (a -> m) -> SCC a -> m Source # foldr :: (a -> b -> b) -> b -> SCC a -> b Source # foldr' :: (a -> b -> b) -> b -> SCC a -> b Source # foldl :: (b -> a -> b) -> b -> SCC a -> b Source # foldl' :: (b -> a -> b) -> b -> SCC a -> b Source # foldr1 :: (a -> a -> a) -> SCC a -> a Source # foldl1 :: (a -> a -> a) -> SCC a -> a Source # toList :: SCC a -> [a] Source # null :: SCC a -> Bool Source # length :: SCC a -> Int Source # elem :: Eq a => a -> SCC a -> Bool Source # maximum :: Ord a => SCC a -> a Source # minimum :: Ord a => SCC a -> a Source # sum :: Num a => SCC a -> a Source # product :: Num a => SCC a -> a Source #
Traversable SCC
Instance details Methods traverse :: Applicative f => (a -> f b) -> SCC a -> f (SCC b) Source # sequenceA :: Applicative f => SCC (f a) -> f (SCC a) Source # mapM :: Monad m => (a -> m b) -> SCC a -> m (SCC b) Source # sequence :: Monad m => SCC (m a) -> m (SCC a) Source #
Eq1 SCC
Instance details Methods liftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool Source #
Read1 SCC
Instance details 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
Instance details Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> SCC a -> ShowS Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [SCC a] -> ShowS Source #
Eq vertex => Eq (SCC vertex)
Instance details Methods (==) :: SCC vertex -> SCC vertex -> Bool # (/=) :: SCC vertex -> SCC vertex -> Bool #
Data vertex => Data (SCC vertex)
Instance details Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SCC vertex -> c (SCC vertex) Source # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SCC vertex) Source # toConstr :: SCC vertex -> Constr Source # dataTypeOf :: SCC vertex -> DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SCC vertex)) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SCC vertex)) Source # gmapT :: (forall b. Data b => b -> b) -> SCC vertex -> SCC vertex Source # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r Source # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SCC vertex -> r Source # gmapQ :: (forall d. Data d => d -> u) -> SCC vertex -> [u] Source # gmapQi :: Int -> (forall d. Data d => d -> u) -> SCC vertex -> u Source # gmapM :: Monad m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> SCC vertex -> m (SCC vertex) Source #
Read vertex => Read (SCC vertex)
Instance details Methods readsPrec :: Int -> ReadS (SCC vertex) Source # readList :: ReadS [SCC vertex] Source # readPrec :: ReadPrec (SCC vertex) Source # readListPrec :: ReadPrec [SCC vertex] Source #
Show vertex => Show (SCC vertex)
Instance details Methods showsPrec :: Int -> SCC vertex -> ShowS Source # show :: SCC vertex -> String Source # showList :: [SCC vertex] -> ShowS Source #
Generic (SCC vertex)
Instance details Associated Types type Rep (SCC vertex) :: * -> * Source # Methods from :: SCC vertex -> Rep (SCC vertex) x Source # to :: Rep (SCC vertex) x -> SCC vertex Source #
NFData a => NFData (SCC a)
Instance details Methods rnf :: SCC a -> () Source #
Outputable a => Outputable (SCC a) #
Instance details Methods ppr :: SCC a -> SDoc Source # pprPrec :: Rational -> SCC a -> SDoc Source #
Generic1 SCC
Instance details Associated Types type Rep1 SCC :: k -> * Source # Methods from1 :: SCC a -> Rep1 SCC a Source # to1 :: Rep1 SCC a -> SCC a Source #
type Rep (SCC vertex)
Instance details type Rep (SCC vertex) = D1 (MetaData "SCC" "Data.Graph" "containers-0.5.10.2" False) (C1 (MetaCons "AcyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 vertex)) :+: C1 (MetaCons "CyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [vertex])))
type Rep1 SCC
Instance details type Rep1 SCC = D1 (MetaData "SCC" "Data.Graph" "containers-0.5.10.2" False) (C1 (MetaCons "AcyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) :+: C1 (MetaCons "CyclicSCC" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 [])))

data Node key payload Source #

Constructors

DigraphNode
Fields node_payload :: payload node_key :: key node_dependencies :: [key]

Instances

(Outputable a, Outputable b) => Outputable (Node a b) #
Instance details Methods ppr :: Node a b -> SDoc Source # pprPrec :: Rational -> 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 #

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 #