Safe Haskell  None 

Language  GHC2021 
Synopsis
 data Graph node
 graphFromEdgedVerticesOrd :: Ord key => [Node key payload] > Graph (Node key payload)
 graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] > Graph (Node key payload)
 graphFromVerticesAndAdjacency :: Ord key => [Node key payload] > [(key, key)] > Graph (Node key payload)
 data SCC vertex where
 AcyclicSCC vertex
 NECyclicSCC !(NonEmpty vertex)
 pattern CyclicSCC :: [vertex] > SCC 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
 allReachable :: Ord key => Graph node > (node > key) > Map key (Set key)
 allReachableCyclic :: Ord key => Graph node > (node > key) > Map key (Set key)
 outgoingG :: Graph node > node > [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
 classifyEdges :: Uniquable key => key > (key > [key]) > [(key, key)] > [((key, key), EdgeType)]
Documentation
Instances
Outputable node => Outputable (Graph node) Source #  
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] > Graph (Node key payload) Source #
graphFromVerticesAndAdjacency :: Ord key => [Node key payload] > [(key, key)] > Graph (Node key payload) Source #
Strongly connected component.
AcyclicSCC vertex  A single vertex that is not in any cycle. 
NECyclicSCC !(NonEmpty vertex)  A maximal set of mutually reachable vertices. Since: containers0.7.0 
pattern CyclicSCC :: [vertex] > SCC vertex  Partial pattern synonym for backward compatibility with 
Instances
Foldable1 SCC Source #  Since: containers0.7.0  
Defined in Data.Graph fold1 :: Semigroup m => SCC m > m Source # foldMap1 :: Semigroup m => (a > m) > SCC a > m Source # foldMap1' :: Semigroup m => (a > m) > SCC a > m Source # toNonEmpty :: SCC a > NonEmpty a Source # maximum :: Ord a => SCC a > a Source # minimum :: Ord a => SCC a > a Source # foldrMap1 :: (a > b) > (a > b > b) > SCC a > b Source # foldlMap1' :: (a > b) > (b > a > b) > SCC a > b Source # foldlMap1 :: (a > b) > (b > a > b) > SCC a > b Source # foldrMap1' :: (a > b) > (a > b > b) > SCC a > b Source #  
Eq1 SCC Source #  Since: containers0.5.9  
Read1 SCC Source #  Since: containers0.5.9  
Defined in Data.Graph  
Show1 SCC Source #  Since: containers0.5.9  
Functor SCC Source #  Since: containers0.5.4  
Foldable SCC Source #  Since: containers0.5.9  
Defined in Data.Graph fold :: Monoid m => SCC m > m # foldMap :: Monoid m => (a > m) > SCC a > 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 # elem :: Eq a => a > SCC a > Bool # maximum :: Ord a => SCC a > a #  
Traversable SCC Source #  Since: containers0.5.9  
Generic1 SCC Source #  
Defined in Data.Graph
 
OutputableP env a => OutputableP env (SCC a) Source #  
Lift vertex => Lift (SCC vertex :: Type)  Since: containers0.6.6  
NFData a => NFData (SCC a) Source #  
Defined in Data.Graph  
Outputable a => Outputable (SCC a) Source #  
Data vertex => Data (SCC vertex) Source #  Since: containers0.5.9  
Defined in Data.Graph gfoldl :: (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 :: forall r r'. (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) #  
Generic (SCC vertex) Source #  
Defined in Data.Graph
 
Read vertex => Read (SCC vertex) Source #  Since: containers0.5.9  
Show vertex => Show (SCC vertex) Source #  Since: containers0.5.9  
Eq vertex => Eq (SCC vertex) Source #  Since: containers0.5.9  
type Rep1 SCC Source #  Since: containers0.5.9  
Defined in Data.Graph type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers0.7inplace" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec1 NonEmpty)))  
type Rep (SCC vertex) Source #  Since: containers0.5.9  
Defined in Data.Graph type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers0.7inplace" 'False) (C1 ('MetaCons "AcyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 vertex)) :+: C1 ('MetaCons "NECyclicSCC" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'SourceUnpack 'SourceStrict 'DecidedUnpack) (Rec0 (NonEmpty vertex)))) 
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
DigraphNode  

Instances
Functor (Node key) Source #  
(Outputable a, Outputable b) => Outputable (Node a b) 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 #
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 #
allReachable :: Ord key => Graph node > (node > key) > Map key (Set key) Source #
Efficiently construct a map which maps each key to it's set of transitive dependencies. Only works on acyclic input.
allReachableCyclic :: Ord key => Graph node > (node > key) > Map key (Set key) Source #
Efficiently construct a map which maps each key to it's set of transitive
dependencies. Less efficient than allReachable
, but works on cyclic input as well.
findCycle :: forall payload key. Ord key => [Node key payload] > Maybe [payload] Source #
Find a reasonably short cycle a>b>c>a, in a graph The graph might not necessarily be strongly connected.
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 #
Edge direction based on DFS Classification
classifyEdges :: 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.