Q.e.d. Code

QED 7: Topological Ordering



In a directed acyclic graph, we can use reachability to determine a partial order. But sometimes we want a total ordering of the nodes to accomplish some result. There are usually many possible total orderings that satisfy the partial ordering. Topological sorting algorithms can help us discover them, whether we want just one, or all possible orderings. Unit tests can only cover one scenario. Mathematical proof, while it generalizes to many scenarios, is not always feasible. Thankfully, we have tools that will search the input space to help us find problems in our code. Parameterized unit tests come in two flavors: generitive tests and exploratory tests. Generitive testing tools, like Quick Check and Test.Check, try random inputs. Exploratory testsing tools, like Pex and Code Digger, discover scenarios that cover as many branches in the code as possible. These tools are a good addition to the other two, helping us fill that gap. Leslie Lamport used logical clocks in a distributed system to solve the mutual ex