# Tuesday, August 31, 2004

This post presents a new Reflector Addin that creates and diplays the graph of statement inside methods: the StatementGraph. This addin is an evolution of the IL graph. (this addin is not yet available for download).

 The statement graph is built from the Reflector CodeModel where each IStatement instance is a vertex and edges are added accordingly to the code "flow" (creating the edges is the most involved task). The rest of the job is handled by the QuickGraph library. When it makes sense, the vertices are clickable and you can jump to the invoked method, etc... The next step will be to update the Automatic Unit Test generator with the StatementGraph...

Let's see some simple methods and their corresponding graphs:

Simple

  • Original code:
    public void Simple()
    {
        Console.WriteLine("hello");
    }
    
  • Decompiled:
    public void Simple()
    {
          Console.WriteLine("hello");
    }
  • Graph:

Two statements in sequence

  • Original code:
    public void Body()
    {
        Console.WriteLine("hello");
        Console.WriteLine("world");
    }
    
  • Decompiled:
    public void Body()
    {
          Console.WriteLine("hello");
          Console.WriteLine("world");
    }
  • Graph:

If - Then - Else

  • Original code:
    public void If(int value)
    {
        if (value<0)
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
  • Decompiled:
    public void If(int value)
    {
          if (value < 0)
          {
                Console.WriteLine("true");
                return;
          }
          Console.WriteLine("false");
    }
    
  • Graph:

While

  • Original code:
    public void While()
    {
        int i = 0;
        while(i<10)
        {
            Console.Write(i++);
        }
    }
  • Decompiled:
    public void While()
    {
          int num1 = 0;
          while ((num1 < 10))
          {
                Console.Write(num1++);
          }
    }
  • Graph:

While with break and continue

  • Original code:
    public void WhileBreakContinue()
    {
        int i = 0;
        while (i < 10)
        {
            if (i == 5)
                continue;
            if (i == 7)
                break;
            Console.Write(i++);
        }
        Console.WriteLine("Finished");
    }
  • Decompiled:
    public void WhileBreakContinue()
    {
          int num1 = 0;
          while ((num1 < 10))
          {
                if (num1 == 5)
                {
                      continue;
                }
                if (num1 == 7)
                {
                      break;
                }
                Console.Write(num1++);
          }
          Console.WriteLine("Finished");
    }
    
    
    
  • Graph:

Try - Catch

  • Original code:
    public void TryCatch()
    {
        try
        {
            Console.WriteLine("hello");
        }
        catch (Exception ex)
        {
            Console.WriteLine("Boom: {0}",ex);
        }
    }
    
  • Decompiled:
    public void TryCatch()
    {
          try
          {
                Console.WriteLine("hello");
          }
          catch (Exception exception1)
          {
                Console.WriteLine("Boom: {0}", exception1);
          }
    }
  • Graph:

posted on Tuesday, August 31, 2004 4:40:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [18]
# Monday, August 30, 2004

Just finished the private presentation of the PhD... One month to go and I'll get the degree :)

For the curious, here's a link to the presentation: http://blog.dotnetwiki.org/downloads/PhDPresentationdeHalleux.pdf

posted on Monday, August 30, 2004 2:00:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [6]
# Sunday, August 29, 2004

The "classic" TestFixture now supports a new type of test case: combinatorial tests. This fixture comes from an original idea of Jamie Cansdale, and it's design has been refined with the joint help of Jamie, Omer van Kloeten and the dev@mbunit.tigris.org mailing list.

A simple example

Suppose that we have a ICountX interface that defines a method that counts the number of 'x' in a string:

interface ICountX
{
   int Count(string s);
}

You have two classes that implement that interface:

class SickCountX : ICountX
{
   public int Count(string s)
   {
       return 2;
   }
}

class CountX : ICountX
{
   public int Count(string s)
   {
       int count = 0;
       foreach(char c in s)
           if (c=='x')
              count++;
       return count;
   }
}

Now you would like to test that those two interface implementations work correctly. Let's start by writing a test method inside a TestFixture. The CountIsExact method receives a string, the number of x in the string and checks that a provided ICountX implementation computes the expected x count:

[TestFixture]
public class ICountXTest
{
   public class StringX
   {
       public StringX(string value, int xcount){Value = value; XCount = xcount;}
       public string Value;
       public int XCount;
       public override string ToString() { return String.Format("{0},{1}",this.Value,this.XCount);}
   }

   [CombinatorialTest]
   public void CountIsExact(
      ICountX counter,
      StringX s
      )
   {
       Assert.AreEqual(s.XCount, counter.Count(s.Value));
   }
}

Next, we create a few strings and xcount that can serve for creating test case. By simplicity we use the new C# 2.0 iterators to implement that:

[Factory(typeof(StringX))]
public IEnumerable Strings()
{
    yield return new StringX("",0);
    yield return new StringX("x",1);
    yield return new StringX("xa",1);
    yield return new StringX("xax",2);
    yield return new StringX("aaa",0);
}

Note that we have tagged the method with Factory so that MbUnit knows this method creates StringX instances. We also create another method that will create instance of ICountX to test:

[Factory(typeof(ICountX))]
public IEnumerable Counters()
{
   yield return new SickCountX();
   yield return new CountX();
}

Now, we would like to cross product the output of Counters and StringX and feed the combination in the CountIsExact test method. To do so, we use the UsingFactories attribute to tag the parameters of the method:

[CombinatorialTest]
public void CountIsExact(
   [UsingFactories("Counters")] ICountX counter,
   [UsingFactories("Strings")] StringX s
)
{...}

The fixture is ready, so we can give it a run. The output of the test execution is as follows:

[mbunit][Failure] CountIsExact(Counters(SandBox.SickCountX),Strings(,0))
[mbunit][Failure] CountIsExact(Counters(SandBox.SickCountX),Strings(x,1))
[mbunit][Failure] CountIsExact(Counters(SandBox.SickCountX),Strings(xa,1))
[mbunit][Success] CountIsExact(Counters(SandBox.SickCountX),Strings(xax,2))
[mbunit][Failure] CountIsExact(Counters(SandBox.SickCountX),Strings(aaa,0))
[mbunit][Success] CountIsExact(Counters(SandBox.CountX),Strings(,0))
[mbunit][Success] CountIsExact(Counters(SandBox.CountX),Strings(x,1))
[mbunit][Success] CountIsExact(Counters(SandBox.CountX),Strings(xa,1))
[mbunit][Success] CountIsExact(Counters(SandBox.CountX),Strings(xax,2))
[mbunit][Success] CountIsExact(Counters(SandBox.CountX),Strings(aaa,0))

6 succeeded, 4 failed, 0 skipped, took 0,00 seconds.

It worked! As expected, we have 5 x 2 = 10 test case generated. Each test case name is generated out of the data source and different data values. Of course, you can "bind" data to the parameters using various other ways and the tests support more that 2 parameters as we will see in the following. We could also have added multiple Using Attributes.

Prequisites

This new features uses the TestFu.Operations framework in the background. This framework is detailed in the here (part 1) and here (part 2).

Rationale

The CombinatorialTest has the following workflow:

  • for each parameter of the test method, get all the domains D of the parameter from the UsingAttributes (there are a bunch of those). This creates a collection of domain for each parameter which is also a domain itself, which we'll call parameter domain: PD = collection of D,
  • foreach tuple in the CartesianProduct of the parameter domains
    • foreach ptuple in the PairWizeProduct of the domain in the tuple (each entry is a domain for the corresponding method parameters)
      • Create a test case that will invoke the test method with the values in ptuple.

Note that in the example above, PD = { { Counters }, { Strings } }, hence the Cartesian product has only one element {Counters} x {Strings} = (Counters,Strings). 

Custom Using Attributes

All Using attribute inherit from the abstract base class attribute UsingBaseAttribute which defines one abstract method:

public abstract class UsingBaseAttribute : Attribute
{
    public abstract void GetDomains(
        IDomainCollection domains, 
        ParameterInfo parameter,
        object fixture);
}

This method receives the tagged parameter, an instance of the fixture class and a collection of domains. It can add new domain to this fixture. For example, the following attribute, UsingLinear, generate a linearly spaced vector of integers:

public sealed class UsingLinearAttribute : UsingBaseAttribute
{
    private IDomain domain;
    public UsingLinearAttribute(int start, int stepCount)
    {
        this.domain = new LinearInt32Domain(start, stepCount);
    }
    public override void GetDomains(IDomainCollection domains, ParameterInfo parameter, object fixture)
    {
        domains.Add(domain);
    }
}

Here we have used the LinearInt32Domain shipped with TestFu.Operations and we have added that domain to the domain collection. Let's write a test that uses that attribute and see the result:

[CombinatorialTest]
public void UsingLinear(
    [UsingLinear(0, 10)] int i)
{
    Console.WriteLine(i);
}


--- output
[mbunit][Success] UsingLinear(0)
[mbunit][Success] UsingLinear(1)
[mbunit][Success] UsingLinear(2)
[mbunit][Success] UsingLinear(3)
[mbunit][Success] UsingLinear(4)
[mbunit][Success] UsingLinear(5)
[mbunit][Success] UsingLinear(6)
[mbunit][Success] UsingLinear(7)
[mbunit][Success] UsingLinear(8)
[mbunit][Success] UsingLinear(9)
10 succeeded, 0 failed, 0 skipped, took 0,00 seconds.

Built in Using Attributes

MbUnit comes with a number of built-in using attribute that should get you started almost all situations.

UsingLinearAttribute

Already described previously.

UsingLiteralsAttribute

This attribute lets you specify a list of value separated by ';'. MbUnit will try to convert those to the parameter type using Convert.ChangeType method:

[CombinatorialTest]
public void UsingLinearAndLiterals(
    [UsingLinear(0, 3)] int i,
    [UsingLiterals("a;b")] char c
)
{
    Console.WriteLine("{0} {1}",i,c);
}
--- output
[mbunit][Success] UsingLinearAndLiterals(0,a)
[mbunit][Success] UsingLinearAndLiterals(0,b)
[mbunit][Success] UsingLinearAndLiterals(1,a)
[mbunit][Success] UsingLinearAndLiterals(1,b)
[mbunit][Success] UsingLinearAndLiterals(2,a)
[mbunit][Success] UsingLinearAndLiterals(2,b)
6 succeeded, 0 failed, 0 skipped, took 0,00 seconds.

UsingFactoriesAttribute

This attribute will look for factory method in a specified type. If the factory type is not specified, it will default it to the fixture type. If the member name is not specified, it will look for all the methods tagged with Factory attribute and compatible with the parameter type:

  • Not specifying the member name, MbUnit looks for all the compatible factories:
    [Factory]
    public int GetZero()
    {
        return 0;
    }
    [Factory]
    public int[] GetZeroOne()
    {
        return new int[] { 0, 1 };
    }
    [Factory(typeof(int))] // we need to specify the factory type
    public IEnumerable GetZeroOneAsEnumerable()
    {
        return this.GetZeroOne();
    }
    [CombinatorialTest]
    public void UsingFactories(
        [UsingFactories] int i
        )
    {
        Console.WriteLine("{0}", i);
    }
    
    
    -- output
    
    [mbunit][Success] UsingFactories(GetZero(0))
    [mbunit][Success] UsingFactories(GetZeroOne(0))
    [mbunit][Success] UsingFactories(GetZeroOne(1))
    [mbunit][Success] UsingFactories(GetZeroOneAsEnumerable(0))
    [mbunit][Success] UsingFactories(GetZeroOneAsEnumerable(1))
    
    
  • Using external factories by specifying a factory type:
    public class IntFactory
    {
        [Factory]
        public int One()
        {
            return 1;
        }
    }
    
    
    [CombinatorialTest]
    public void UsingFactory(
        [UsingFactories(typeof(IntFactory))] int i)
    {
        Console.WriteLine("{0}", i);
    }
    
    --- output
    
    [mbunit][Success] UsingFactory(One(1))
    1 succeeded, 0 failed, 0 skipped, took 0,00 seconds.
    

UsingImplementationsAttribute

This attribute looks for all the implementation of a type in an assembly, creates an instance and feeds it to the test.

[CombinatorialTest]
public void TestCountX([UsingImplementationsAttribute(typeof(ICountX))] ICountX countX)

What about tuple filtering ?

In some situation you may want to filter out tuple. For example, we want to check that a methods throws ArgumentNullException on null arguments:

[Factory]
public string[] Strings()
{
    return new string[] { null, "hello" };
}

[CombinatorialTest]
[ExpectedArgumentNullException]
public void TestWithValidator(
    [UsingFactories("Strings")] string s1,
    [UsingFactories("Strings")] string s2
)
{
    if (s1 == null)
        throw new ArgumentNullException();
    if (s2 == null)
        throw new ArgumentNullException();
}

(Note that ExceptedException and all the other decorator work on the combinatorial tests). If we run the test now, we wil have unwanted tuple such as (null, null) and ("hello", "hello"): the first does not give much information and the second will not throw and hence, is erroneous. In this kind of situation, you can specify a "filter" method that takes the same arguments as the test method and return bool:

public bool IsValid(string s1, string s2)
{
   if (s1 == null && s2 == null)
      return false;
   if (s1 != null && s2 != null)
      return false;
   return true;
}

[CombinatorialTest(TupleValidatorMethod = "IsValid")]
[ExpectedArgumentNullException]
public void TestWithValidator(...

--- output

[mbunit][Success] TestWithValidator(Strings(),Strings(hello))
[mbunit][Success] TestWithValidator(Strings(hello),Strings())

As expected, the unwanted tuple have been dropped.

Conclusion

Combinatorial test provides a flexible, extensible and powerfull way of generating test case. It implements the classic PairWize combinatorial generation in order to avoid exponential test explosion while integrating smoothly in the MbUnit architecture.

posted on Sunday, August 29, 2004 3:51:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [4]
# Saturday, August 28, 2004

Reflector version: 4.1.2.0
Reflector.Graph version: 4.1.2.0
Download: www.dotnetwiki.org

Before getting the new version, make sure you have a look at the release notes below!

Important Changes:

  • The graphs are now visualized in SVG by embedding Internet Explorer inside Reflector. Make sure you have a SVG viewer that works with IE installed on your machine. I strongly recommend Adobe SVG Viewer.
  • The version number of the assemblies is now following Reflector version. Hence, current version number is 4.1.2.0.

Release Notes:

  • The Assembly Graph and IL graph now have clickable nodes. In general, clicking on a vertex will move the selection to that element in the Reflector tree.
  • The Assembly Graph now shows all the referenced even if they are not loaded. Click on a unloaded assembly will load it in Reflector,

Adobe SVG viewer tips:

If you are using Adobe SVG viewer, here are a few tips:

  • Alt + left down + move move = panning the view,
  • Ctrl + left click = zoom in,
  • Ctrl + Shift + left click = zoom out,
  • Ctrl + left click + mouse move = zoom region,
  • Right click pops up the SVG viewer context menu.

Here's the new look of the Assembly graph.

posted on Saturday, August 28, 2004 12:38:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [15]
# Friday, August 27, 2004

In the previous post on combinatorial testing, I mentionned that Cartesian product was not a good solution when the number of domains and their dimension grew, because of obvious explosion of the number of tests.

A common approach to this problem is to consider a set of combination to create all the possible 2-tuples between the domains. It is called  PairWize or AllPairs suites generation. In TestFu.Operations, I decided to implement the algorithms found in [1]. Currently only the A1 algorithm is implemented. A2 and A4 should follow soon. Note that those algorithms are constructive, memory cheap and fast.

PairWize suite generation

The use of the PairWize algorithm is straightforward and follows the same semantics as the cartesian product. In the example below, we want to generate the allpairs for 3 domains of respective size 2,3,4.

int[] array1 = new int[] { 1, 2 };
char[] array2 = new char[] { 'a', 'b','c' };
string[] array3 = new string[] { "a", "combinatorial", "hello","world" };

int i = 1;
foreach (ITuple tuple in Products.PairWize(array1, array2, array3))
{
    Console.WriteLine("{0}: {1}",i++, tuple);
}

-- output
1: 1, a, a
2: 1, a, combinatorial
3: 2, a, a
4: 1, a, hello
5: 1, a, a
6: 1, a, world
7: 2, a, a
8: 2, b, a
9: 1, b, combinatorial
10: 2, b, combinatorial
11: 2, b, hello
12: 1, b, combinatorial
13: 2, b, world
14: 2, b, combinatorial
15: 1, c, a
16: 1, c, hello
17: 1, c, combinatorial
18: 2, c, hello
19: 1, c, hello
20: 1, c, world
21: 2, c, hello
22: 2, c, a
23: 1, c, world
24: 2, c, combinatorial
25: 2, c, world
26: 2, c, hello
27: 1, c, world
28: 2, c, world

If you wish to compare with the article, this is the output for a (k,l) = (7,3) and for the bipartite graphs A1 = {0,1,2,3} B1={4,5,6}, A2 = {0,4,2,3} B2={1,5,6} and A3 = {0,1,5,3} B3={4,2,6}. Remember that if we want to generate the test cases using the Cartesian product, we would have 3^7 = 2187 tests to run.

1: 0, 0, 0, 0, 0, 0, 0
2: 0, 0, 0, 0, 1, 1, 1
3: 1, 0, 0, 0, 0, 1, 1
4: 0, 1, 0, 0, 1, 0, 1
5: 0, 0, 0, 0, 2, 2, 2
6: 2, 0, 0, 0, 0, 2, 2
7: 0, 2, 0, 0, 2, 0, 2
8: 1, 1, 1, 1, 0, 0, 0
9: 0, 1, 1, 1, 1, 0, 0
10: 1, 0, 1, 1, 0, 1, 0
11: 1, 1, 1, 1, 1, 1, 1
12: 1, 1, 1, 1, 2, 2, 2
13: 2, 1, 1, 1, 1, 2, 2
14: 1, 2, 1, 1, 2, 1, 2
15: 2, 2, 2, 2, 0, 0, 0
16: 0, 2, 2, 2, 2, 0, 0
17: 2, 0, 2, 2, 0, 2, 0
18: 2, 2, 2, 2, 1, 1, 1
19: 1, 2, 2, 2, 2, 1, 1
20: 2, 1, 2, 2, 1, 2, 1
21: 2, 2, 2, 2, 2, 2, 2

Compairing results with AllPairs

For 10 domains with 10 values each, the TestFu algorithm generate 370 test suite. The AllPairs tool generate 177 which is roughly 50% less. This behavior was expected by the algorithm author. A greedy algorithm on the output could lower our result. Note that the tests were generate in 36.419ms which shows the efficiency of the algorithm.

References:

[1] Efficient Algorithms for Generation of Combinatorial Covering Suites, by Adrian Dumitrescu

posted on Friday, August 27, 2004 5:09:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [6]

TestFu has now limited support for generate test suites using Combinatorial Testing as the TestFu.Operations namespace. Combinatorial Testing is an interresting testing technique that has been studied a quite some time now (see citeseer search). There already exists a few package that provide tools to generate test suites (see jenny, allpairs) but none in the .Net framework.

Combinatorial Testing description and Glossary

In this chapter, I will define the different "actors" that interact in the combinatorial testing. I will link them to their corresponding interface in TestFu.

  • A domain (IDomain) is a finite set of objects.
    • Ex: {1,2,3} is a domain composed of the integers 1,2,3
  • The boundary of a domain D is the set of objects in D that are at the boundary of the domain.  The boundary is also a domain,
    • If we decide that the first and last element of an array is it's domain, {1,3} is the boundary of {1;2,3}
  • A tuple (ITuple) acts as a container for other objects,
  • A product on a domain collection (IDomainCollection) is an algorithm (ITupleEnumerable) that generate a suite of tuples (ITupleEnumerator), created by combining one element of each domain, using a predefined strategy.

Currently, the only product available is the cartesian product which returns an exhaustive enumeration of the all possible combination. It is well-known that this product is not efficient at all covering the tests because of the exponential explosion of the number of suites, better strategy have been developped such as the PairWaise covering (all pairs), t-wize, etc... I haven't had the time to look at those yet.

Let's see some code

The TestFu.Operations namespace is designed to be simpler but no simpler. Let's start by defining some domains:

int[] array1 = { 1, 2 };
string[] array2 = { "a", "combinatorial", "hello", "world" };
char[] array3 = { 'a', 'b', 'c' };

Note: TestFu.Operations currently supports arrays, collection (ICollection), enumerable collection (IEnumerable) or singleton domain (1 element). Of course, this is totally extendible. You could easily think about a domain reading the rows of a DataTable, or the elements of a XmlDocument

The static class Products contains a rich set of methods that can create the different products. Let's start with the cartesian product of array1 x array2:

int i = 1;
foreach (ITuple tuple in Products.Cartesian(array1, array2))
{
    Console.WriteLine("\t{0}: {1}",i++,tuple);
}

-- output
        1: 1, a
        2: 1, combinatorial
        3: 1, hello
        4: 1, world
        5: 2, a
        6: 2, combinatorial
        7: 2, hello
        8: 2, world

As expected, each returned tuple is a collection of element from each domain. We could also decide to test the boundaries of the arrays only (first and last element each time):

i = 1;
foreach (ITuple tuple in Products.BoundaryCartesian(array1, array2))
{
    Console.WriteLine("\t{0}: {1}", i++, tuple);
}

-- output
        1: 1, a
        2: 1, world
        3: 2, a
        4: 2, world

The products can act on an arbitrary number of domains so we can add array3 in the product (don't forget about the explosion of the tests number!):

i = 1;
foreach (ITuple tuple in Products.Cartesian(array1, array2, array3))
{
    Console.WriteLine("\t{0}: {1}", i++, tuple);
}

-- output
        1: 1, a, a
        2: 1, a, b
        3: 1, a, c
        4: 1, combinatorial, a
        5: 1, combinatorial, b
        6: 1, combinatorial, c
        7: 1, hello, a
        8: 1, hello, b
        9: 1, hello, c
        10: 1, world, a
        11: 1, world, b
        12: 1, world, c
        13: 2, a, a
        14: 2, a, b
        15: 2, a, c
        16: 2, combinatorial, a
        17: 2, combinatorial, b
        18: 2, combinatorial, c
        19: 2, hello, a
        20: 2, hello, b
        21: 2, hello, c
        22: 2, world, a
        23: 2, world, b
        24: 2, world, c

Where to go from here ?

The next important step is to implement an algorithm that computes the pair-wize or t-wize suite generation. This is very important if you have a lot of domains. In a near future, I will also show how we can use these products to produce a new type of fixture in MbUnit. This fixture was suggested by Jamie Cansdale.

In this post, I have showed a new, simple, way of creating combinatorial tests using the TestFu.Operations namespace.

posted on Friday, August 27, 2004 1:07:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [5]
# Thursday, August 26, 2004

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...

 

posted on Thursday, August 26, 2004 12:27:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Tuesday, August 24, 2004

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

posted on Tuesday, August 24, 2004 9:02:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [7]
# Monday, August 23, 2004

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.

 

posted on Monday, August 23, 2004 11:22:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Sunday, August 22, 2004

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

posted on Sunday, August 22, 2004 11:06:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [6]