Yesterday, Jamie Cansdale (NunitAddin) and I spent time "pair-programming" on MbUnit, NUnitAddIn and other tools like the Reflector.Graph addins. The collaboration has been very productive! I've got a lot of blog entry to write about the things we have built yesterday, I'll summarize quickly:

• MbUnit has now a much better support for NUnitAddIn:
  • this solution should be "version" proof: it should not break if NUnitAddIn updates and so on,
  • you can select a method and execute the tests involving that method,
  • MbUnit generates the Html report and puts the URL in the output, ready for you
• MbUnit has new fixtures! CrossFixture generates generate the cross products of different data source and hands it to the test...
• Reflector.Graph renders to SVG: we are now hosting IE inside Reflector to display SVD graphs...
• Reflector.Graph graphs has clickable links! You can click on an assembly to load it, and so on...

A lot of work, a lot of fun...

In this entry, I'll give a tutorial on using QuickGraph to compute the maximum flow of a capacitated network. I will start by giving some defnitions in order to make things clear, then I will apply the QuickGraph algorithms to a practical example.

Maximum Flows

Computing the maximum flow in a network is one of the classic graph theory problem (see [1]). Here's a prototype of flow network:

Imagine a pipeline network for transporting oil from a single source to a single sink. Each edge represents a section of pipeline, and the endpoints of the edge corresponds to the junctures at the ends of that section. The edge capacity is the maximum amount of oil that can flow through the corresponding section per unit time.

What is the maximum amount of oil per unit time that can flow through the network ? That question is a maximum flow problem.

A single-source single-sink network is a connected directed graph that has a distinguised vertex called the source with nonzero outdegree, and a distinguished vertex called sink with  nonzero indegree. A single source-single sink network with source s and sink t (also called target) is called a s-t network. A capacitated network is a connected directed graph such that each edge e is assigned a nonnegative weight cap(e), called the capacity of edge e.

In the following, we shall consider a capacitated s-t network.

Sample network

I will illustrate the example on a 5-vertex capacitated network with source s and sink t as depicted below. This network is extracted from Chapter 12 of [1].

By convention, each edge is tagged with it's capacity (on the left) and, if computed, the flow. s is the source, t is the sink.

Building the sample network with QuickGraph

The first step of the tutorial is to create the sample network above using QuickGraph. To do so, we create a AdjacencyGraph and populate it "manually" with the vertices and edges:

using QuickGraph; // NamedVertex
using QuickGraph.Providers; // providers
using QuickGraph.Representations; // AdjacencyGraphg
using QuickGraph.Concepts; // IEdge

// the graph
AdjacencyGraph graph = new AdjacencyGraph(
    new NamedVertexProvider(),
    new EdgeProvider(),
    true);
// the capacity dictionary
EdgeDoubleDictionary capacities = new EdgeDoubleDictionary();

// adding vertices
NamedVertex s = (NamedVertex)graph.AddVertex(); s.Name = "s";
NamedVertex x = (NamedVertex)graph.AddVertex(); x.Name = "x";
NamedVertex v = (NamedVertex)graph.AddVertex(); v.Name = "v";
NamedVertex w = (NamedVertex)graph.AddVertex(); w.Name = "w";
NamedVertex t = (NamedVertex)graph.AddVertex(); t.Name = "t";

// adding edges
IEdge sx = graph.AddEdge(s, x); capacities[sx] = 5;
IEdge sv = graph.AddEdge(s, v); capacities[sv] = 7;
IEdge xv = graph.AddEdge(x, v); capacities[xv] = 3;
IEdge xw = graph.AddEdge(x, w); capacities[xw] = 7;
IEdge wv = graph.AddEdge(w, v); capacities[wv] = 5;
IEdge wt = graph.AddEdge(w, t); capacities[wt] = 4;
IEdge vt = graph.AddEdge(v, t); capacities[vt] = 6;

Once the graph is built, you can easily draw it using GraphvizAlgorithm. This topic has already been discribed in previous posts so I won't enter into the details .

Preparing the network for the Maximum Flow

In order to work properly, the maximum flow algorithms require that for each edge (u,v) in the network, there exists a reversed edge (v,u). Moreover, a dictionary associating each edge to its reversed must be provided. The sample network obviously does not fullfill this requirement. Therefore, we must add "articifial" reversed edge that have capacity equal to zero. In order to help you with this (tedious) task, QuickGraph provides the ReversedEdgeAugmentorAlgorithm algorithm that will do the job for you:

using QuickGraph.Algorithms.MaximumFlow;

// creating the augmentor
ReversedEdgeAugmentorAlgorithm reversedEdgeAugmentor = new ReversedEdgeAugmentorAlgorithm(this.graph);
// attaching handler to the ReversedEdgeAdded event
// this event is triggered on each "artifical" edge added to the graph
ReversedEdgeAugmentorAlgorithm reversedEdgeAugmentor.ReversedEdgeAdded += new EdgeEventHandler(reversedEdgeAugmentor_ReversedEdgeAdded);

// add the articifial edges
reversedEdgeAugmentor.AddReversedEdges();
...
// cleans up
reversedEdgeAugmentor.RemoveReversedEdges();

// this handler sets the capacity of the new edge to zero
void reversedEdgeAugmentor_ReversedEdgeAdded(Object sender, EdgeEventArgs e)
{
    capacities[e.Edge] = 0;
}

The method AddReversedEdges augments the graph with the reversed edges, while the RemoveReversedEdges "cleans up the mess". If we draw the flow graph after the AddReversedEdges call, it gives the following results (where the reversed edges are dashed):

Computing the MaximumFlow

QuickGraph implements 2 maximum flow algorithms: Edmund Karp and Push Relabel. We will use PushRelabel as it is more efficient, however, both inherit from the abstract base class MaximumFlowAlgorithm. The method Compute computes the maximum flow and returns it's value:

MaximumFlowAlgorithm algo = new PushRelabelMaximumFlowAlgorithm(
    graph,
    capacities,
    reversedEdgeAugmentor.ReversedEdges
    );

double value = algo.Compute(s, t);

After cleaning up the reversed edges, we can draw the graph with the maximum flow in each edge. Note that for this sample, the maxium flow value is 10.

Demo source

The full source of the demo is available in the MbUnit CVS at http://mbunit.tigris.org/source/browse/mbunit/src/QuickGraphTest/MaximumFlowDemo.cs

Acknoledgment

Many thanks to Arun Bhalla for porting PushRelabel to C#

References

[1] Graph Theory and Its applications, Jonathan Gross and Jay Yellen

As mentionned in a previous post, I mentionned that dnAnalytics was a new project providing a managed wrapper above LAPACK. Those guys have been doing a great job and the current release (trunk 271) is already featuring a lot of the "classic" Matrix Algebra algorithms:

• Dense matrices (float or double) with support for the classic operations, +, *, -,
• Norms: norm-1, norm-2, norm-infty, etc...,
• Condition number,
• QR decomposition,
• LU decomposition,
• SVD decomposition

The library is both accessible as a fully managed version, and a managed wrapper above the native, rock solid, LAPACK library. If you are doing matrix algebra in your application, and you care about robustness, efficiency and accuracy, you should be interrested by this project.

In my previous Singleton Unit Testing, I proposed a possible solution for unit testing a singleton (I'll name it the ShortLivingSingleton approach). Omer Van Kloeten came up with another approach (the KillTheSingleton approach), Darren Oakey with the CreateForTesting approach and , Len Holgate finishes the picture tearing appart our the first 2 solutions (the SingletonIsBad approach). Since comments on this topic have been interresting, they are worth a little summary.

The problem

The application you are developping is using a Singleton, that you need to test. How do you test a singleton ?

SingletonIsBad approach

1. Singleton are evil! If you have the opportunity to refactory the code, make sure you definitely need this singleton, otherwize get rid of it.
2. You have no choice and you cannot get rid of the singleton. Make sure you split the singleton functionalities in two classes: The class that does all the work and the singleton aspect that prevents multiple instances. Doing so, you will not have to cheat to test the singleton.
3. You could not fullfill any of the point above, and you will need to cheat...

The two first point came from Len Holgate and I totally agree with him. The third point is for tester who do not have the possiblity of avoiding or refactoring the singleton. To tackle this problem, I and Omer have proposed 2 cheats and Darrel Oakley proposed a wider solution to the problem.

CreateForTesting approach

The approach asks you to embed some functionality in a class that helps other people test it. The most common thing is to add - to most objects - a function CreateTestFoo, where Foo is the object that you are testing. This gives you a new and fully initialized version of Foo - however complicated Fooactually is.

Cheating the singleton.

Both cheat solutions are based on Reflection, therefore they will not work if you have denied Reflection on your tested assembly (Haacked's  comment).

ShortLivingSingleton  approach

This approach consists of creating a new non-singleton approach for each test and do the testing on this instance. To do so, we use reflection to access the private constructor and instanciate the singleton. Therefore, the singleton is never created and never used.

KillTheSingleton approach

This approach kills the singleton after each test, in the TearDown method for example. To "kill" the singleton, the static field holding the singleton reference is nullified using Reflection and garbage collection is forced.

Conclusions

Singletons are evil but yet you find people using them (shame on me). They are problematic to test because you cannot separate the unit tests.  The first step for testing them is actually to refactor your application and get rid of the singleton. If this cannot be done, you have to cheat the singleton using Reflection to properly test them.

ps: I'd like to thank all the people who commented the blog entry for their constructive comments :) Cheers, Jonathan

Here are the NSort benchmarks for arrays of integer filled with random data. These benchmarks are for the non-generic versions.

The code to generate the benchmarks uses NPerf is given below:

using System;
using System.Collections;
using NPerf.Framework;

namespace NSort.Perf
{
    [PerfTester(typeof(ISorter), 10
        , Description = "Sort Algorithm benchmark for Random data"
        , FeatureDescription = "Collection size")]
    public class SorterBenchmark
    {
        protected int[] list;
        public int CollectionCount(int testIndex)
        {
            int n = 0;
            if (testIndex < 0)
                n=10;
            else
                n = (testIndex+1)*500;
            return n; 
        }
        [PerfRunDescriptor]
        public double RunDescription(int testIndex)
        {
            return (double)CollectionCount(testIndex);
        }

        [PerfSetUp]
        public override void SetUp(int testIndex, ISorter sorter)
        {
            Random rnd = new Random();
            this.list = new int[CollectionCount(testIndex)];
            for (int i = 0; i < this.list.Length; ++i)
                this.list[i] = rnd.Next();
        }
        [PerfTest]
        public void SortRandomData(ISorter sorter)
        {
            sorter.Sort(this.list);
        }
    }
}

NSort is a very nice and flexible package of sorting (15) algorithms from which the developer can choose. This library was a jointly work from me, Marc Clifton and Robert Rohde. In this blog, I'll show how NSort can be quickly "upgraded" to Generic and how you can use the extensibility of MbUnit to test it efficiently.

Generic

Converting the algorithms to Generic was really straightforward. For almost all cases, it was just a matter of adding <T> here and there, and replacing temporary object instance by T. Let's see this with the two interfaces of the project: IStorter and ISwap:

using System.Collections;
...

public interface ISorter
{
    IComparer Comparer {get;}
    void Sort(IList list);
}
public interface ISwap
{
    void Swap(IList array, int left, int right);
    void Set(IList array, int left, int right);
    void Set(IList array, int left, object obj);
}

Now, their generic brothers:

using System.Collections.Generic;
...

public interface ISorter<T>
{
    IComparer<T> Comparer {get;}
    void Sort(IList<T> list);
}
public interface ISwap<T>
{
    void Swap(IList<T> array, int left, int right);
    void Set(IList<T> array, int left, int right);
    void Set(IList<T> array, int left, object obj);
}

That was pretty quick. The conversion of the algorithms followed the same ideas and a dozens of cut/paste/replace later the NSort.Generic namespace was born.

Testing

There is a well-know proverb that says "the one who live by the cut-and-paste, die by the cut-and-paste" and that's exactly how I ported NSort to generics... so to ensure the quality of it really needs proper testing.

Testing NSort

Let's start with the testing of the non-generic classes. The main purpose of the NSort is to provide implementation of the ISorter interface that effectively sort list of elements and that's what we are willing to test. A quick (internal) brain strom for test cases of ISorter yields:

• Sort a null list throws ArgumentNullException,
• Sort a list with 0,1,2, n (n large) elements check it is effectively sorted. The purpse of the 0,1,2 is to test "boundary" lists.

Since we are testing an interface, this is a good candidate to use CompositeUnitTesting the TypeFixture of MbUnit:

[TypeFixture(typeof(ISorter))]
public class SorterTest
{
    private int[] list;
    private void CreateSortAndCheckSorted(ISorter sorter, int length)
    {
        Random rnd = new Random();
        list = new int[length];
        // create data
        for (int i = 0; i < list.Length; ++i)
            list[i] = rnd.Next();

        // sort table
        sorter.Sort(list);

        // verify
        for (int i = 0; i < list.Length - 1; ++i)
        {
            Assert.IsTrue(sorter.Comparer.Compare(list[i], list[i + 1]) <= 0,
                "Element {0} ({1}) is strictly greather that {1} ({2})",
                i, list[i], i + 1, list[i + 1]
            );
        }
    }

    [Test]
    [ExpectedArgumentNullException]
    public void SortNulList(ISorter sorter)
    {
        sorter.Sort(null);
    }

    [Test]
    public void SortEmptyList(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 0);
    }
    [Test]
    public void SortListWithOneElement(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 1);
    }
    [Test]
    public void SortListWithTwoElements(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 2);
    }
    [Test]
    public void SortListOfSize100(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 100);
    }
}

Now that we have defined the fixture, we need to feed it with ISorter instances. Usually, you would need to write a factory class that would create the instance, but this task was too boring not to be automated. What I want is a way to tell MbUnit to look for all the classes in NProf that implemented ISorter that apply the fixture to it...

Implementing a custom factory attribute:

The TypeFixture fixture looks for attributes that derive from ProviderFixtureDecoratorPatternAttribute and invoke their GetRun method to gather the IRun instance. Therefore, we "just" need to inherit from this attribute and implement the behavior we want:

[AttributeUsage(AttributeTargets.Class,AllowMultiple =true,Inherited =true)]
public class AssemblyProviderFactoryAttribute : ProviderFixtureDecoratorPatternAttribute
{
    private Type assemblyType; // type contained in the assembly to test
    private Type targetType; // the tested type
    public AssemblyProviderFactoryAttribute(Type assemblyType, Type targetType)
    {
        ...
        this.assemblyType = assemblyType;
        this.targetType = targetType;
    }
    public Assembly Assembly
    {
        get { return this.assemblyType.Assembly;}
    }
    public Type TargetType
    {
    get { return this.targetType;}
    }
    public override IRun GetRun(Type decoratedType)
    {
        throw new NotImplementedException();
    }
}

The GetRun still needs to be implemented. The task for the returned Run object is to explore the tested Assembly (assemblyType.Assembly) for types  compatible with targetType. MbUnit provides an abstract base class, Run, for implementing IRun:

public class AssemblyProviderRun : Run
{
    private AssemblyProviderFactoryAttribute attribute;
    public AssemblyProviderRun(AssemblyProviderFactoryAttribute attribute)
    {
        this.attribute = attribute;
    }

    public override void Reflect(RunInvokerTree tree, RunInvokerVertex parent, Type t)
    {
        foreach (Type type in this.attribute.Assembly.GetExportedTypes())
        {
            if (!type.IsClass) // interrested in class only,
                continue;
            if (type.IsAbstract) // abstract class cannot be created
                continue;
            if (!this.attribute.TargetType.IsAssignableFrom(type)) // must be assignable to TargetType
                continue;
            // trying to get the default constructor
            ConstructorInfo ci = type.GetConstructor(Type.EmptyTypes);
            if (ci == null)// no default constructor
                continue;

            ActivatorRunInvoker invoker = new ActivatorRunInvoker(this, type);
            tree.AddChild(parent, invoker);
        }
    }
}

ActivatorRunInvoker is a IRunInvoker implementation that takes a type, creates an new instance of it and feeds it to the arguments of the next invoker. We implement this invoker by inheriting from the abstract base class RunInvoker:

public class ActivatorRunInvoker : RunInvoker
{
   private Type targetType;
   public ActivatorRunInvoker(IRun run, Type targetType)
   :base(run)
   {
      this.targetType = targetType;
   }
   public override string Name
   {
   get {return this.targetType.Name;}
   }
   public override object Execute(object o, System.Collections.IList args)
   {
      Object target = Activator.CreateInstance(targetType);
      args.Add(target);
      return null;
   }
}

That's the end of the journey. The attribute is ready to be used to tag the SorterTest fixture:

[TypeFixture(typeof(ISorter))]
[AssemblyProviderFactory(typeof(ISorter),typeof(ISorter))]
public class SorterTest
{
   ...
}

Let's launch those test and see what happens. I like having my Test assemblies "self-executable" so I make it a Console application and the AutorRunner in the Main method. The Text report spits out:

Tests run: 75, Failures: 0, Not run: 0

This makes sense because there are 15 ISorter implementation times 5 tests applied to them. Of course, I would like to have more information, so I generate the Html report:

Here we see clearly which class is being tested and so, our new attribute is working perfectly without recompiling MbUnit!

Testing NSort.Generics

In order to test the generic sort algorithm, we need to take the following steps:

1. adapt the SorterTest fixture for the ISorter<int> interface (I choose to test int only),
2. adapt the AssemblyProviderRun to support generics

The task 1 is trivial and is similar to the ISorter to ISorter<T> transformation. The second task is more technical because we need to check that types are generic and handle them differently. To cut the story short, here is the method that iterates over generic types:

private void ReflectGenericTypes(RunInvokerTree tree, RunInvokerVertex parent)
{
    Type[] args = this.attribute.TargetType.GetGenericArguments();
    foreach (Type type in this.attribute.Assembly.GetExportedTypes())
    {
        if (!type.IsClass)
            continue;
        if (type.IsAbstract)
            continue;
        if (!type.HasGenericArguments) // true if type is a generic
            continue;

        // get the generic type definition
        Type genericType = type.GetGenericTypeDefinition();
        // bind types
        Type gtype = genericType.BindGenericParameters(args);
        // check if assignable
        if (!this.attribute.TargetType.IsAssignableFrom(gtype))
            continue;
        // create new invoker
        AddInvoker(tree, parent, gtype);
    }
}

It took me a while to fix that up but I finally got though. Now, the GenericSorterTest looked as follows and I was ready to hit the "Run" button:

[TypeFixture(typeof(ISorter<int>))]
[AssemblyProviderFactory(typeof(ISorter), typeof(ISorter<int>))]
public class GenericSorterTest
{...

The text report of the tests returned 150 tests, which was logical and they all passed (after some bug fixing). And I'm happy.

The method of testing I showed here worked well because of the nature of the problem to test: the ISorter class are all well separated and do not need mocking and so on.  One of the nicest thing about this is that if you write new ISorter implementations, you do not need to modify your fixutre, they will be automatically tested by MbUnit.

The date finally came through. I will present a workshop on testing on September 9 for the BENUG (Benelux .Net User Group) association on Testing. This will be a "exercise" oriented workshop.

Eric Gunnerson has recently blog about a Trebuchet (that he offered to his wife?). This remembered me of the one I built, with my friends, a few years ago.

The photo below shows the "implementation" of the Trebuchet and some facts about it:

• the rotating pole was 7m long and composed of two wooden poles of 15cm of diameter
• the rotation axis was made of a steel stick of 26mm of diameter. It was at 3.5 m of the ground. Note because the construction was not perfectly symmetric, it got twisted.
• the "counter"-weight was about 100kg altough not measured,
• the structure was composed of 10 wooden poles buried 50cm into ground.
• the projectile was a piece of wood, 50cm long, 15cm diameter, it got throwed at around 60 meter althought the trajectory was far from behing optimal (too vertical).

At first sight it may seem that Singleton and Unit Testing are not compatible since you cannot ensure the separation between the tests. We could solve the problem by instanciating a new "Singleton" instance for each test and apply test on this "local" instance. The problem is that a well implemented Singleton is sealed and it's constructor are private (see Singleton Pattern here) and thus you cannot create this instance.

using System;

public sealed class Singleton
{
   ...
   private Singleton() {}

   public static Singleton Instance
   {
      get { ...}
   }
}

Reflection to the rescue

An elegant way for bypassing the "creation problem" is to use Reflection to get the private constructor (ConstructorInfo) and then use this constructor info to create a new "Singleton" instance.

using System.Reflection;

[TestFixture]
public class SingletonTest
{
    private Singleton target = null;
    [SetUp]
    public void SetUp()
    {
        ConstructorInfo ci =
            typeof(Singleton).GetConstructor(
                BindingFlags.Instance |
                BindingFlags.NonPublic,
                null,
                Type.EmptyTypes,
                null
                );
         Assert.IsNotNull(ci);
         this.target = (Singleton)ci.Invoke(null);
    }
}

Now we have a new instance of the Singleton for each test and we are happy.

Jamie Cansdale has found a hidden gem in .Net 2.0: the much awaited InternalsVisibleTo attribute. This attribute let's you specify the name of an assembly that can view the internals... That's perfect for testing internal classes.

http://weblogs.asp.net/nunitaddin/archive/2004/08/13/214130.aspx