# Sunday, September 21, 2008

I’ve upgraded QuickGraph to C# 3.0, and it’s extension methods and lambdas (requires .net 3.5). The result is fairly nice, specially the extension methods who make algorithms more discoverable.

For example, the following snippet shows how to get the topological sort of tables out of a DataSet (useful when you need to fill/delete tables):

DateSet ds = …; // get some DataSet
// ToGraph() is an extension method on DataSet, which builds
// the Table/Relation graph from the data set schema
var g = ds.ToGraph();
// TopologicalSort() is an extension method on IVertexAndEdgeListGraph<T,E>
// which returns the graph topological sort
var tables = g.TopologicalSort();
foreach(DataTable table in tables)

More changes were made on the API to take advantage of delegates (i.e. since it’s easier to write them): no more predicate interfaces, dropping dictionaries for delegates in shortest path algorithm etc…

posted on Sunday, September 21, 2008 1:00:51 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [5]
# Wednesday, September 17, 2008

In the previous post, we implemented the insertion method of a binary heap using Test Driven Development (TDD) and parameterized unit tests (I'll leave the full implementation of the insertion method as an exercise).

In this post, we will take a closer look at the development flow that we used and show how it relates to traditional TDD. For many people, combining TDD and automated test generation makes no sense. I believe this is not true anymore, and this is what this post is about.

Test Driven Development Flow

TDD has a well-defined flow where developers

  1. write a unit test,
  2. run the test and watch it fail,
  3. fix the code,
  4. run the test and watch the test pass. Start again (I'll skip refactoring in this discussion)

During this flow, practitioners also refer to the green state when all tests are passing and red state when some tests are failing. The little picture below depicts this little state machine.


A key aspect of this approach is that the design of the API is inferred by writing the 'scenarios', i.e. tests. Therefore, unit tests are a critical building block of the TDD flow.

Note also that xUnit-like test frameworks (pick your favorite framework here) provide the automation tools so that the execution of the test and the investigation of a failure is painless for the programmer.

Test Driven Development Flow With Parameterized Unit Tests

Parameterized unit tests and Pex change the TDD flow while retaining its essence: building the design from tests. Here are the steps, we'll discuss them in detail later on:

  1. Write a parameterized unit test,
  2. Run Pex and watch some generated unit tests fail,
  3. Fix the code,
  4. Run Pex again,
    1. Some previously generated unit tests now pass, at least one new failing unit test get generated (go to 3)
    2. All generated tests are passing, start again (go to 1)

The key difference is the shortcut from step 4 (generating unit tests) to 3 (fix the code), without passing through step 1 (write a new test). This is illustrated by the yellow feedback loop in the diagram below:


To the risk of repeating myself, let me emphasize some important points here:

  • you still need to write unit tests, it's just that they can have parameters: Pex generates unit tests from parameterized unit tests, by instantiating them. The person who writes the parameterized unit test is you, not the tool!
  • it is still about design: using parameterized unit tests is as much about design as closed (i.e. parameterless) unit tests. In fact, one can argue that parameterized unit tests are way closer to a specification that closed unit tests.
  • it is test first: in case it was not obvious by now :)

The shortcut from 4 to 3

As mentioned above, the main difference in the flow is that jump from running the tool (step 4) to fixing the code (step 3), without writing new tests (step 1). This happens because a parameterized unit tests captures equivalence classes rather than a single scenario like closed unit tests. As a result,

  • you spend more time fixing/implementing the code: the nice thing about the shortcut is that you can spend more time writing the code, rather than writing tests.
  • you can leverage automated white-box testing tools: Pex tries to get the maximum coverage out of your parameterized unit test (note remember that getting coverage also means covering the throwing branches in Assert), using an automated white-box code analysis. Now that you have also those manycore CPUs on your motherboard, you can finally make a good use of them :)

To Pex and not to Pex

An important aspect of parameterized unit tests (and tools like Pex) is that you do not have to drop (completely) your existing habits: in many cases, it is easier to write closed unit tests! In fact, you can always start from a closed unit test and refactor it later. We do not expect users to parameterized unit tests write exclusively (another nice read here), but when you do write them, we expect you'll get much more 'out of your buck'.

In future posts, we'll discuss different ways to write parameterized unit tests: from refactoring existing unit tests to using test patterns.

To be continued...

Next time, we'll go back to the heap and look at implementing the 'remove minimum' method...

(Pex is a automated structural testing tool from Microsoft Research. More information at http://research.microsoft.com/pex.)

posted on Wednesday, September 17, 2008 5:15:26 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [6]
# Monday, September 08, 2008

The other day I stumbled on a first draft on a new book on algorithms (Data Structure and Algorithms). After taking a peak at the draft, I found some (hidden) motivation to finally write a decent binary heap for QuickGraph. A heap is a critical data structure for Dijkstra shortest path or Prim's minimum spanning tree algorithm, since it is used to build efficient priority queues.

In this post, we'll start building a binary heap using Test-Driven Development (write the tests first, etc...) and parameterized unit tests.


The heap is a tree where each parent node has a value smaller or equal to the child nodes. The binary heap is a heap implemented through a binary tree, and to make things more interesting (and fast), the tree is usually mapped to an array using indexing magic:

  • parent node index: (index - 1) /2
  • left child node: 2*index + 1
  • right child node: 2*index + 2

The indexing magic is typically the kind of things that introduce bugs.

Let's write that first test

We start by writing a test that simply fills any binary heap with a number of entries. A possible test for this is written as follows:

public void Insert<TPriority, TValue>(
    [PexAssumeUnderTest]BinaryHeap<TPriority, TValue> target,
    [PexAssumeNotNull] KeyValuePair<TPriority, TValue>[] kvs)
    var count = target.Count;
    foreach (var kv in kvs) {
        target.Add(kv.Key, kv.Value);
        AssertInvariant<TPriority, TValue>(target);
    Assert.IsTrue(count + kvs.Length == target.Count);

There are a number of unusual annotations in this test. Let's review all of them:

  • The test is generic: Pex supports generic unit tests. This is really convenient when testing a generic type.
  • PexAssumeUnderTest, PexAssumeNotNull: it basically tells Pex that we don't care about the case where kvs or target is null.
  • We've added a Add(TPriority priority, TValue value) method and Count property to the BinaryHeap

There are also two assertions in the test. Inlined in the loop, we check the invariant of the heap (AssertInvariant). We'll fill up this method as we go. At the end of the test, we check that the Count property.

BinaryHeap version #0

We start with a simple (broken) implementation that does nothing:

public class BinaryHeap<TPriority, TValue> {
    public void Add(TPriority priority, TValue value) { }
    public int Count { returnt 0; }

Now that the code compiles, we run Pex which quickly finds that a non-empty array breaks the count assertion.


BinaryHeap version #1

We have a failing test so let's fix the code by storing the items in a list:

public class BinaryHeap<TPriority, TValue> {
    List<KeyValuePair<TPriority, TValue>> items = new List<KeyValuePair<TPriority, TValue>>();
    public void Add(TPriority priority, TValue value) {
        this.items.Add(new KeyValuePair<TPriority, TValue>(priority, value));
    public int Count {
        get { return this.items.Count; }

We run Pex again and all the previous failing tests are now passing :)


There's a new object creation event that happened (bold events should be looked at). Remember that the test takes a binary heap as argument, well we probably need to tell Pex how to instantiate that class. In fact, this is exactly what happens when I click on the object creation button:


Pex tells me that it guessed how to create the binary heap instance and gives me the opportunity to save and edit the factory. The factory looks like this and get included automatically in the test project:

public partial class BinaryHeapFactory {
    [PexFactoryMethod(typeof(BinaryHeap<int, int>))]
    public static BinaryHeap<int, int> Create() {
        BinaryHeap<int, int> binaryHeap = new BinaryHeap<int, int>();
        return binaryHeap;

All our tests are passing, we can write the next test... but wait!

We have an invariant!

The nice thing about data structures is that they have fairly well defined invariants. These are very useful for testing!

In the case of the heap, we know that the parent node priority should always be less or equal to the priorities of both of his left and right children. Therefore, we can add a method to BinaryHeap that walks the array and checks this property on each node:

public void ObjectInvariant() {
    for (int index = 0; index < this.count; ++index) {
        var left = 2 * index + 1;
        Debug.Assert(left >= count || this.Less(index, left));
        var right = 2 * index + 2;
        Debug.Assert(right >= count || this.Less(index, right));
private bool Less(int i, int j) { return false; }

Remember that AssertInvariant method, let's call ObjectInvariant in that method and run Pex again.

void AssertInvariant<TPriority,TValue>(BinaryHeap<TPriority,TValue> target) {

Pex immediately finds an issue:


This assertion is due to our overly simplified implementation of Less, which always return false.

Fixing tests, and finding new failing tests

We have failing tests so it's time to fix the code again. Let's start fixing on the Less method by using a comparer:

readonly Comparison<TPriority> comparison =
private bool Less(int i, int j)
    return this.comparison(this.items[i].Key, this.items[j].Key) >= 0;

We run Pex and it comes back with the following tests:


Two interesting things happened here:

  • the previous failing test (with [0,0], [0,0]) was fixed by fixing Less
  • Pex found a new issue where the input array involves a small key (3584), then a larger key (4098). A correct heap implementation would have kept the smaller key at the first position.

The coolest part is we did not have to write any additional line of code to get to this point: Pex updated the previous tests and generated the new failure for us.

This is a new kind of flow that occurs when using Pex in TDD: a code update has fixed some issues but created new ones. We are still moving towards our goal but we did not have to pay the price of writing a new unit test.

In fact, to fulfill the invariant and make this test pass we will have to write a correct implementation of the Add method.... without writing a single additional line of test code :)

to be continued...

posted on Monday, September 08, 2008 10:39:35 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]
# Tuesday, August 26, 2008

Update: renamed project to YUnit to avoid clashing with other frameworks.

I've been playing with custom test types for team test lately and the result of this experiment is YUnit. A microscopic test framework that lets you write tests anywhere since it only uses the Conditional attribute. That's right, any public static parameterless method tagged with [Conditional("TEST")] becomes a test :)

If you've always dreamed of implementing your own custom test type, this sample could be helpful to you. Remember that this is only a sample and comes with no guarantees of support.

Sources and installer available at: http://code.msdn.microsoft.com/yunit.


posted on Tuesday, August 26, 2008 8:26:36 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]

It's that time of the year where a little refresh of QuickGraph (http://www.codeplex.com/quickgraph) is needed.

What's new?

  • New API to add and remove vertices from the graphs
  • Important bug fixes in the shortest path algorithms (oops!)
  • Support for MSAGL ( http://research.microsoft.com/research/msagl/ )
  • QuickGraph.Data, provides data structures build graphs of databases (given a DataSet)
  • QuickGraph.Heap, provides data structure to build graphs of SOS managed memory dumps (more later)



posted on Tuesday, August 26, 2008 9:11:35 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Wednesday, August 06, 2008

Read on Nikolai's announcement on the latest drop of Pex.

posted on Wednesday, August 06, 2008 11:06:59 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Thursday, July 31, 2008

Alexander Nowak has started a blog post chronicle on Pex and already has 6 episodes to it!

  • Pex - test Case 5 (regular expressions)
  • Pex - test case 4 (strings and parameter validation)
  • Pex - Test case 3 (enums and business rules validation)
  • Pex - test case 2 
  • Pex - test case 1
  • Starting with Pex (Program Exploration)

    The posts give a nice point of view of Pex from a user perspective, and against classic testing techniques such as equivalence classes.

  • posted on Thursday, July 31, 2008 7:25:49 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Tuesday, July 29, 2008

    Linear programming problems are usually solved using the simplex algorithm. While it is easy to encode a constraint system of linear equalities and inequalities as a Parameterized Unit Test for Pex, there is currently no way to tell Pex that we want test inputs that are “minimal” according to a custom objective function. However, Pex can still generate *surprising* feasible solutions.

    Let's start with a simple set of linear inequalities that define our problem.

    public int Test(int x, int y)
    // PexAssume is used to add 'constraints' on the input
    // in this case, we simply encode the inequalities in a boolean formula PexAssume.IsTrue( x + y < 10 & // using bitwise & to avoid introducing branches 5 * x + 2 * y > 20 & -x + 2 * y > 0 & x > 0 & y > 0);
    // the profit is returned so that it is automatically logged by Pex return x + 4 * y; }

    After running Pex, we get one feasible solution. It is not optimal as expected since we don't apply the simplex algorithm.


    Enter overflows

    Remember that .Net arithmetic operations will silently overflow unless you execute them in a checked context? Let's push our luck and try to force an overflow by changing x > 0 constraint to x > 1000:

    public int Test(int x, int y)
            x + y < 10 &
            5 * x + 2 * y > 20 &
            -x + 2 * y > 0 &
            x > 1000 & y > 0
        return x + 4 * y;

    Z3, the constraint solver that Pex uses to compute new test inputs, uses bitvector arithmetic to find a surprising solution that fulfills all the inequalities (our profit has just gone of the roof :)).


    Z3 is truly an astonishing tool!

    Checked context

    In order to avoid overflow, one should use a checked context. Let's update the parameterized unit test:

    public int Test(int x, int y)
                x + y < 10 &
                5 * x + 2 * y > 20 &
                -x + 2 * y > 0 &
                x > 0 & y > 0
        return x + 4 * y;

    In fact, in that case, Pex generates 2 test cases. One test that passes and the other test that triggers an OverflowException (implicit branch).


    Stay tuned for more surprising discoveries using Pex.

    posted on Tuesday, July 29, 2008 6:35:31 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [2]
    # Thursday, July 03, 2008

    Brian Keller dropped by our offices to record a movie on Pex. A good old white board session to explain how pex works:



    posted on Thursday, July 03, 2008 11:21:54 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Monday, June 23, 2008

    We've added a little filter to Pex that flags potential testability issues in your source code (at least in the context of unit testing). The idea is simple: if your code logic branches over API that depends on the environment (file system, UI, network, time, etc...), you're not doing 'pure' unit testing anymore and it could be flagged as a testability issue.

    Why do we do this anyway?

    The problem is that Pex is very sensitive to those issues: it cannot control the environment. Let's take a look at a simple example where we write a custom stream class with a testability issue in one of the constructor:


    The constructor checks that the file exists. In order to pass that point in the program, you would actually need to create or find an actual file in the file system. You're talking to the file system, this is already integration testing.

    Parameterized drama

    Let's be optimistic and write a parameterized unit test that reads a file:


    Pex comes back with a single test, passing null as fileName (i.e. default(string)). Since Pex does not know how the file system works, it cannot create a valid file name, and that's where the story ends.


    Help is on the way

    To help you diagnose these issues, we've added specialized logging flags. Pex shows hints in the issue notification area:


    Clicking on that event will give you additional important data: which API was called and the stacktrace at the time of the call :)


    posted on Monday, June 23, 2008 11:08:33 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]