Data.Graph.Inductive.Query.Topsort

Documentation

nodeLabel :: Graph g => g a b -> Node -> a

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

A graph node container to be used with Kanh's topsort algorithm.

Minimal complete definition

insertNode, extractNode

Methods

insertNode :: Node -> s -> s

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)

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)

Instances

NodeSet NodeStack

Methods

insertNode :: Node -> NodeStack -> NodeStack

extractNode :: NodeStack -> Maybe (Node, NodeStack)

data TraversalOrder b

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 Graph instance you are using.

ReverseOrder

Reverse of InOrder.

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. LT means the first edge is visited first. GT means the second edge is visited first. EQ means it doesn't matter and the implementation can choose arbitrarily.

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

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

emptyList, appendItem

Methods

emptyList :: l a

appendItem :: a -> l a -> l a

topsortKahn

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 u to node v, u appears before v in this list. If the graph is empty or the initial node set is empty, an empty list is returned. If the graph contains a cycle, Nothing is returned.

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:

1. When traversing a node's outgoing edges, the order in which this traversal happens isn't specified.
2. 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

newtype NodeStack

Constructors

NodeStack [Node]

Instances

NodeSet NodeStack

Methods

insertNode :: Node -> NodeStack -> NodeStack

extractNode :: NodeStack -> Maybe (Node, NodeStack)

topsortUnmix :: (DynGraph g, ResultList l) => g a b -> NodeStack -> TraversalOrder b -> Maybe (l Node)

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)

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.