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]
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
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 :: forall key. Uniquable key => key -> (key -> [key]) -> [(key, key)] -> [((key, key), EdgeType)]

Documentation

data Graph node Source #

Instances

Instances details

Outputable node => Outputable (Graph node) #
Instance details Defined in Digraph 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

Instances details

Functor SCC	Since: containers-0.5.4
Instance details Defined in Data.Graph Methods fmap :: (a -> b) -> SCC a -> SCC b Source # (<$) :: a -> SCC b -> SCC a Source #
Foldable SCC	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods fold :: Monoid m => SCC m -> m Source # foldMap :: Monoid m => (a -> m) -> SCC a -> 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	Since: containers-0.5.9
Instance details Defined in Data.Graph 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	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods liftEq :: (a -> b -> Bool) -> SCC a -> SCC b -> Bool Source #
Read1 SCC	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	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 #
Eq vertex => Eq (SCC vertex)	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods (==) :: SCC vertex -> SCC vertex -> Bool # (/=) :: SCC vertex -> SCC vertex -> Bool #
Data vertex => Data (SCC vertex)	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) 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 :: forall r r'. (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)	Since: containers-0.5.9
Instance details Defined in Data.Graph 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)	Since: containers-0.5.9
Instance details Defined in Data.Graph Methods showsPrec :: Int -> SCC vertex -> ShowS Source # show :: SCC vertex -> String Source # showList :: [SCC vertex] -> ShowS Source #
Generic (SCC vertex)
Instance details Defined in Data.Graph Associated Types type Rep (SCC vertex) :: Type -> Type 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 Defined in Data.Graph Methods rnf :: SCC a -> () Source #
Outputable a => Outputable (SCC a) #
Instance details Defined in Outputable Methods ppr :: SCC a -> SDoc Source # pprPrec :: Rational -> SCC a -> SDoc Source #
Generic1 SCC
Instance details Defined in Data.Graph Associated Types type Rep1 SCC :: k -> Type Source # Methods from1 :: forall (a :: k). SCC a -> Rep1 SCC a Source # to1 :: forall (a :: k). Rep1 SCC a -> SCC a Source #
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.6.2.1" '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	Since: containers-0.5.9
Instance details Defined in Data.Graph type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers-0.6.2.1" '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 #

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

(Outputable a, Outputable b) => Outputable (Node a b) #
Instance details Defined in Digraph 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 #

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 #

Given a list of roots return all reachable nodes.

transposeG :: Graph node -> Graph 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 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 #

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

Eq EdgeType #
Instance details Defined in Digraph Methods (==) :: EdgeType -> EdgeType -> Bool # (/=) :: EdgeType -> EdgeType -> Bool #
Ord EdgeType #
Instance details Defined in Digraph 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 #
Outputable EdgeType #
Instance details Defined in Digraph Methods ppr :: EdgeType -> SDoc Source # pprPrec :: Rational -> EdgeType -> SDoc Source #

classifyEdges :: forall key. 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.