topological sort

[JeffreyBenjaminBrown]

Currently when the user requests a set of expressions, the UI presents them in no particular order. The user should be able to specify a list of relationships (using the QNodes /from and /to) and have the UI attempt to order the relationships lexicographically according to those relationships.

Requirements:

A query syntax.

• A way to parse a list of relationships.
• A distinction between ordered queries and unordered queries.
• A query of the form /order a b, where a is a list of QRels, and b is the query that will be ordered.

Behavior for unsuccessful orderings.

There is no built-in routine to provide an ordering; there is only one to detect cycles. If a set of nodes has cycles, sort them anyway. When displaying them, attach a decorator to any expressions which follow on-screen something which "ought" to precede them. Allow the user to "unfold" (using tab indentation) such nodes, so that things that ought to follow them are displayed below them as children. For instance, in a graph a -> b -> c -> b, the user would see something like:

a
b
c (ORDER PROBLEM)

and upon unfolding them, would see:

a
b
c (ORDER PROBLEM)
  b

Relevant functions and files:

• Data.List.sortOn
• [Dwt.Query.Cycles.hs](https://github.com/JeffreyBenjaminBrown/digraphs-with-text/tree/master/src/Dwt/Query) :: (Graph g) => g a b -> [[Node]].
• topological-sort.hs provides sample data, useful for experimenting with Cycles.hs.