Safe Haskell | None |
---|---|
Language | Haskell2010 |
- 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]
- 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]
- 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
Outputable node => Outputable (Graph node) # | |
graphFromEdgedVerticesUniq :: Uniquable key => [Node key payload] -> Graph (Node key payload) Source #
data SCC vertex :: * -> * Source #
Strongly connected component.
AcyclicSCC vertex | A single vertex that is not in any cycle. |
CyclicSCC [vertex] | A maximal set of mutually reachable vertices. |
Functor SCC | |
Foldable SCC | |
Traversable SCC | |
Eq1 SCC | |
Read1 SCC | |
Show1 SCC | |
Eq vertex => Eq (SCC vertex) | |
Data vertex => Data (SCC vertex) | |
Read vertex => Read (SCC vertex) | |
Show vertex => Show (SCC vertex) | |
Generic (SCC vertex) | |
NFData a => NFData (SCC a) | |
Outputable a => Outputable (SCC a) # | |
Generic1 * SCC | |
type Rep (SCC vertex) | |
type Rep1 * SCC | |
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 #
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 #