| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Digraph
- data Graph node
- graphFromEdgedVertices :: Ord key => [Node key payload] -> Graph (Node key payload)
- data SCC vertex :: TYPE Lifted -> TYPE Lifted
- = AcyclicSCC vertex
- | CyclicSCC [vertex]
- type Node key payload = (payload, key, [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]
- stronglyConnCompFromEdgedVertices :: Ord key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesR :: Ord key => [Node key payload] -> [SCC (Node key payload)]
Documentation
Instances
| Outputable node => Outputable (Graph node) | |
data SCC vertex :: TYPE Lifted -> TYPE Lifted 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 | |
| NFData a => NFData (SCC a) | |
| Outputable a => Outputable (SCC a) | |
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
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
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.
stronglyConnCompFromEdgedVertices :: Ord key => [Node key payload] -> [SCC payload] Source