| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Graph.Inductive.Query.Topsort
- nodeLabel :: Graph g => g a b -> Node -> a
- class NodeSet s where
- data TraversalOrder b
- = InOrder
- | ReverseOrder
- | SortedOrder ((Node, b) -> (Node, b) -> Ordering)
- | CustomOrder ([(Node, b)] -> [(Node, b)])
- class ResultList l where
- topsortKahn :: (DynGraph g, NodeSet s, ResultList l) => g a b -> s -> TraversalOrder b -> Maybe (l Node)
- newtype NodeStack = NodeStack [Node]
- topsortUnmix :: (DynGraph g, ResultList l) => g a b -> NodeStack -> TraversalOrder b -> Maybe (l Node)
- topsortUnmixOrder :: (Ord b, DynGraph g, ResultList l) => g a b -> NodeStack -> Maybe (l Node)
Documentation
nodeLabel :: Graph g => g a b -> Node -> a Source #
Find the label for a Node, assuming you know the node exists in the
graph. If the node isn't found, an exception is thrown.
class NodeSet s where Source #
A graph node container to be used with Kanh's topsort algorithm.
Minimal complete definition
Methods
insertNode :: Node -> s -> s Source #
Take a graph node and a container, insert the node into it and return the resulting container. insert :: LNode a -> s a -> s a
extractNode :: s -> Maybe (Node, s) Source #
Remove a node from the container. Return the removed node and the
resulting container after removal. If the container is empty (i.e. there
is no node to remove), return Nothing.
extract :: s a -> Maybe (LNode a, s a)
data TraversalOrder b Source #
Specification of the order in which a node's outgoing edges should be traversed.
Constructors
| InOrder | The order in which they're listed by FGL functions. The FGL
documentation doesn't seem to specify the order, which means it may
depend entirely on the |
| ReverseOrder | Reverse of |
| SortedOrder ((Node, b) -> (Node, b) -> Ordering) | Sort the outgoing edge list before traversal, using the given ordering
function. It takes two pairs, each pair having a labeled node and the
label of the edge, and determines the order they should be visited. |
| CustomOrder ([(Node, b)] -> [(Node, b)]) | Lets you reorder the edge list in an arbitrary way before it gets traversed. Note that it's up to you to make sure the list you return really contains all the items of the input list. |
class ResultList l where Source #
A container for storing the result of the sorting. Kahn's algorithm begins with an empty structure and then appends nodes to produce the result. Therefore almost any sequence container could work.
You can also use a regular Haskell list. Implement append using list
prepend and remember to reverse the list returned by the algorithm.
Minimal complete definition
Arguments
| :: (DynGraph g, NodeSet s, ResultList l) | |
| => g a b | Graph whose nodes to sort |
| -> s | The set of graph nodes which don't have inbound edges |
| -> TraversalOrder b | In which order to go over the outgoing edges of a node |
| -> Maybe (l Node) | Topologically sorted list. For each edge from node |
Flexible topological sort using Kahn's algorithm.
It seems that Haskell graph libraries (and perhaps graph libraries in general) tend to implement topological sort using depth-first search (DFS). While it's probably easier (since these libraries also implement DFS), the result is that you pass a graph to a function and get back the sorted list. There is no room left for specifying variable parts of the algorithm, which means you can't control which topsort order (out of potentially many orders possible) you get. Sometimes you don't care, but sometimes you do.
Kahn's algorithm has room for variations in two places:
- When traversing a node's outgoing edges, the order in which this traversal happens isn't specified.
- The internals of structure S, the set of nodes with no inbound edges, aren't specified. Therefore, so is the order in which nodes are removed from it.
https://en.wikipedia.org/wiki/Topological_sort#Kahn.27s_algorithm
topsortUnmix :: (DynGraph g, ResultList l) => g a b -> NodeStack -> TraversalOrder b -> Maybe (l Node) Source #
Topologically sort commits so that parallel lines of work, e.g. a master branch and a short topic branch merged into it, don't get their commits mixed in the sorted order.
topsortUnmixOrder :: (Ord b, DynGraph g, ResultList l) => g a b -> NodeStack -> Maybe (l Node) Source #
Adds an additioal constraint to topsortUnmix: When traversing a node's
outgoing edges, do so using the Ord instance of the labels of the edges.