Safe Haskell  None 

Language  Haskell2010 
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
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] > Graph (Node key payload) Source #
Strongly connected component.
AcyclicSCC vertex  A single vertex that is not in any cycle. 
CyclicSCC [vertex]  A maximal set of mutually reachable vertices. 
Instances
Functor SCC  Since: containers0.5.4 
Foldable SCC  Since: containers0.5.9 
Defined in Data.Graph fold :: 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 # elem :: Eq a => a > SCC a > Bool # maximum :: Ord a => SCC a > a #  
Traversable SCC  Since: containers0.5.9 
Eq1 SCC  Since: containers0.5.9 
Read1 SCC  Since: containers0.5.9 
Show1 SCC  Since: containers0.5.9 
Eq vertex => Eq (SCC vertex)  Since: containers0.5.9 
Data vertex => Data (SCC vertex)  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 :: (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)  Since: containers0.5.9 
Show vertex => Show (SCC vertex)  Since: containers0.5.9 
Generic (SCC vertex)  
NFData a => NFData (SCC a)  
Defined in Data.Graph  
Outputable a => Outputable (SCC a) Source #  
Generic1 SCC  
type Rep (SCC vertex)  Since: containers0.5.9 
Defined in Data.Graph type Rep (SCC vertex) = D1 (MetaData "SCC" "Data.Graph" "containers0.5.11.0" 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: containers0.5.9 
Defined in Data.Graph type Rep1 SCC = D1 (MetaData "SCC" "Data.Graph" "containers0.5.11.0" 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 #
DigraphNode  

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 #
hasVertexG :: Graph node > node > Bool Source #
reachableG :: Graph node > node > [node] Source #
reachablesG :: Graph node > [node] > [node] Source #
transposeG :: Graph node > Graph node Source #
vertexGroupsG :: Graph node > [[node]] 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.
stronglyConnCompFromEdgedVerticesOrdR :: Ord key => [Node key payload] > [SCC (Node key payload)] Source #