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]
 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
 classifyEdges :: forall key. Uniquable key => key > (key > [key]) > [(key, key)] > [((key, key), EdgeType)]
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 # 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 :: 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) #  
Read vertex => Read (SCC vertex)  Since: containers0.5.9 
Show vertex => Show (SCC vertex)  Since: containers0.5.9 
Generic (SCC vertex)  Since: containers0.5.9 
NFData a => NFData (SCC a)  
Defined in Data.Graph  
Outputable a => Outputable (SCC a) Source #  
Generic1 SCC  Since: containers0.5.9 
type Rep (SCC vertex)  
Defined in Data.Graph type Rep (SCC vertex) = D1 ('MetaData "SCC" "Data.Graph" "containers0.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  
Defined in Data.Graph type Rep1 SCC = D1 ('MetaData "SCC" "Data.Graph" "containers0.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
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 #
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 #
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 #
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 :: 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.