Safe Haskell | None |
---|---|

Language | Haskell2010 |

- data Graph node
- graphFromEdgedVertices :: Ord 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]
- stronglyConnCompFromEdgedVertices :: Ord key => [Node key payload] -> [SCC payload]
- stronglyConnCompFromEdgedVerticesR :: Ord key => [Node key payload] -> [SCC (Node key payload)]

# Documentation

Outputable node => Outputable (Graph node) # | |

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 | |

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] #

topologicalSortG :: Graph node -> [node] #

dfsTopSortG :: Graph node -> [[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 #

vertexGroupsG :: Graph node -> [[node]] #

componentsG :: Graph node -> [[node]] #

findCycle :: forall payload key. Ord key => [Node key payload] -> Maybe [payload] #

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] #