# Wednesday, May 12, 2004

Here's a sample C# application that implements structured numbers. (Practial use of this number is unknown :) )

The maths

The StrutucredNumbers sample contains an implementation of the binary tree operation developped by V. Blondel in Structured Numbers, Properties of a hierarchy of operations on binary trees, Acta Informatica, 35, 1-15, 1998.

We introduce a hierarchy of operations on (finite and infinite) binary trees. The operations are obtained by successive repetition of one initial operation. The ¯rst three operations are generalizations of the operations of addition, multiplication and exponentiation for positive integers.

In the paper, the author defines countably many internal operations on binary trees. The first operation, which he denote by .1. , is obtained by forming the binary tree whose left and right subtrees are equal to the operands. This operation is not associative. The second operation .2. is defined as follows: From the binary trees a and b we construct the binary tree a.2.b by repeating the operation .1. on the tree a with the structure dictated by b. In the same way, we define an operation .3. by repeating .2. , an operation .4. by repeating .3. , etc. We eventually obtain countably many internal operations ( .k. for k>= 1) with the definition

a .k. b = a^(k-1).a^(k-1).a^(k-1)...a^(k-1).a,

where there are b factors.

The code

The code is mainly composed of the BtNode that implements the algebra defined above and some valuators for the tree. At last, NGraphviz is used to render to trees :)

The results

Suppose that we have

x = ..
y = ..
, then
  • x:
  • x.1.y:
  • x.2.y:
  • x.3.y:
  • x.4.y:
posted on Wednesday, May 12, 2004 12:16:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Tuesday, May 11, 2004

In this "episode", we are going to build an application that generates and renders the exection graph of a method using QuickGraph and Lutz Reoder's IlReader. The execution graph is directed graph where each vertex is an IL instruction and each edge represent the transition between two instructions, it could be a jump or a simple move to the next instruction. The graph represents the different path that the application can take into your method. If you have access to the content of a method, you can potentially build.

In a future blog, I will use the execution graph to make "smart" test fixture generator by applying basic graph algorithms on the execution graph. In the following of the blog, I assume you have some basic knowledge of IL, Reflection and Reflection.Emit.

Step 1: creating the graph structures

We begin by creating a specialized type of vertex InstructionVertex that will hold a System.Reflection.Emit.Instruction instance:

using System.Reflection.Emit;
public class InstructionVertex : QuickGraph.Vertex
{
    private Reflector.Disassembler.Instruction instruction=null;
    public InstructionVertex(int id):base(id)
    {}
    public Reflector.Disassembler.Instruction Instruction
    {
        get
        {
            if (this.instruction==null)
                throw new InvalidOperationException();
            return this.instruction;
        }
        set
        {
            this.instruction = value;
        }
    }
    public override string ToString()
    {...}
}

Note that the ToString method uses the code Example.cs in the IlReader source to render an Instruction to string.

To generate a strongly-typed BidirecitonalGraph, that we call InstructionGraph, we use the CodeSmith template called AdjacencyGraph.cst located in the Templates directory.

Step 2: Loading the IL instructions of the method

The building of the graph is done by the IlGraphBuilder class. This class takes the type of the method as an argument. It contains one public method BuildGraph that takes a MethodInfo instance as argument as outputs a InstructionGraph instance containing the execution graph.

The code to extract the MethodBody from the method is almost entirely copy pasted from the IlReader sample:

public class IlGraphBuilder
{
    private Type visitedType;
    private ModuleReader reader;
    public IlGraphBuilder(Type visitedType)
    {
        this.visitedType = visitedType;
        this.reader = new ModuleReader(this.visitedType.Module, new AssemblyProvider());
    }
    public InstructionGraph BuildGraph(MethodInfo mi)
    { 
        // get method body using IlReaderr
        MethodBody methodBody = reader.GetMethodBody(mi);
        ...
    }

    private sealed class AssemblyProvider : IAssemblyProvider
    {
        public Assembly Load(string assemblyName)
        {
            return Assembly.Load(assemblyName); 
        }
        public Assembly[] GetAssemblies()
        {
            throw new NotImplementedException(); 
        }
    }
}

Step 3: Building the graph

The MethodBody instance contains the list of Instruction instances and the list of exception handlers. The building of the graph is done in 3 steps:

  1. iterate the Instruction list and create the vertices in the graph. We also build a dictionary that associates the instruction offset to the corresponding vertex,
    // new field in the class
    Hashtable instructionVertices;
    ...
    foreach(Instruction i in methodBody.GetInstructions())
    {
        // avoid certain instructions
        if (i.Code.FlowControl == FlowControl.Phi || i.Code.FlowControl == FlowControl.Meta)
            continue;
        // add vertex
        InstructionVertex iv = g.AddVertex();
        iv.Instruction = i;
        // store in hashtable
        this.instructionVertices.Add(i.Offset,iv);
    }
    
  2. iterate again over the instructions and add the edges that represent the transitions. This is the tricky part, I use a recursive exploration of the instructions, (this part of the code is a bit heavy for the blog)
  3. iterate over the exception handlers to link the different sections: create the link to catch,finally handlers, etc...

Step 4: Drawing the graph

Drawing the graph is straight-foward using the GraphvizAlgorithm class:

GraphvizAlgorithm gv = new GraphvizAlgorithm(g); 
gv.Write(mi.Name);

Analysing some basic flow contructions:

As an application, I going to show the graph of some basic instruction flow like for, while, if, foreach, etc...

public void HelloWorld()
{
    Console.WriteLine("Hello World");
}

public void IfAlone(bool value)
{
    if (value)
        Console.Write("value is true");
}

public void IfThenElse(bool value)
{
    if (value)
        Console.Write("value is true");
    else
        Console.Write("value is false");
}

public void For()
{
    for(int i = 0;i!=10;++i)
    {
        Console.Write(i);
    }
}

public void While()
{
    int i = 0;
    while(i!=10)
    {
        i++;
    }
}

public void TryCatchFinally()
{
    try
    {
        Console.WriteLine("try");
    }
    catch(Exception)
    {
        Console.WriteLine("catch"); 
    }
    finally
    {
        Console.WriteLine("finally");
    }
}

public void TryMultiCatchFinally()
{
    try
    {
        Console.WriteLine("try");
    }
    catch(ArgumentException)
    {
        Console.WriteLine("catch(arg)"); 
    }
    catch(Exception)
    {
        Console.WriteLine("catch"); 
    }
    finally
    {
        Console.WriteLine("finally");
    }
}

public void ForEach(ICollection col)
{
    foreach(Object o in col)
    {
        Console.WriteLine(o);
    }
}

public void ForEachContinue(int[] col)
{
    foreach(int o in col)
    {
        Console.WriteLine(o);
        if (o == 0)
            continue;
    }
}

public void ForEachBreak(int[] col)
{
    foreach(int o in col)
    {
        Console.WriteLine(o);
        if (o == 0)
            break;
    }
}

public void SwitchIt(int value)
{
    switch(value)
    {
    case 0:
        Console.Write("0");
        break;
    case 1:
        Console.Write("1");
        break;
    default:
        Console.Write("default");
        break;
    }
}

posted on Tuesday, May 11, 2004 10:51:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [9]
# Monday, May 10, 2004

I have just finished a CodeSmith template that "automatically" generates empty tests case for a given type.

This template does a little bit more than just enumerating the available methods: it explores MSIL using RAIL and creates test case following the given rules:

  • if the IL instruction is a conditional branch, create a test case for both possibilities (true/false case)
  • if the IL instruction throws, create a test case expecting the exception,
  • if the IL instruction is returning, create a test case that checks the returned value

Those rules are quite simplistic but can already generate a "huge" number of test case automatically. Each test case comes with a piece of documentation and the method IL code where the target instruction has been set in bold. Currently, the documentation contains IL code, but in the future it would be nicer to output real code, using Reflector for example.

In order to make the template work, you need to put RAIL assemblies and the AssemblyHelper assembly in the CodeSmith directory.

Here's a quick example. The method:

public void ABitMoreComplext(bool goForIt)
{
    if (goForIt)
        throw new Exception();
    else
        Console.Write("did not throw");
        // other instruction 
    Console.Write("hello");
}

and the resulting output in the generated class:

        
        /// <summary>
        /// Tests ABitMoreComplext method when condition is executed as true
        /// (see remarks).
        /// </summary>
        /// <remark>
        /// <para>
        /// Not implemented
        /// </para>
        /// <code>
        /// ldarg.1
        /// <b>brfalse.s</b>
        /// newobj
        /// throw
        /// ldstr
        /// call
        /// ldstr
        /// call
        /// ret
        /// </code>
        /// </remarks>
        [Test]
        [Ignore]
        public void ABitMoreComplextIfTrue1()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// Tests ABitMoreComplext method when condition is executed as true
        /// (see remarks).
        /// </summary>
        /// <remark>
        /// <para>
        /// Not implemented
        /// </para>
        /// <code>
        /// ldarg.1
        /// <b>brfalse.s</b>
        /// newobj
        /// throw
        /// ldstr
        /// call
        /// ldstr
        /// call
        /// ret
        /// </code>
        /// </remarks>
        [Test]
        [Ignore]
        public void ABitMoreComplextIfFalse1()
        {
            throw new NotImplementedException();
        }
        /// <summary>
        /// Tests that the ABitMoreComplext method throws (see remarks)
        /// </summary>
        /// <remark>
        /// <para>
        /// Not implemented
        /// </para>
        /// <code>
        /// ldarg.1
        /// brfalse.s
        /// newobj
        /// <b>throw</b>
        /// ldstr
        /// call
        /// ldstr
        /// call
        /// ret
        /// </code>
        /// </remarks>
        [Test]
        [Ignore]
        [ExpectedException(typeof(Exception))]
        public void ABitMoreComplextThrow3()
        {
            // don't forget to update the exception type.
            throw new NotImplementedException();
        }

ps: The template is called TestFixture and is in the Templates directory in the MbUnit CVS.

 

posted on Monday, May 10, 2004 2:25:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [13]

A co-worker, Jacques Theys, sent me this link:

"GPGPU stands for General-Purpose computation on GPUs. With the increasing programmability of commodity graphics processing units (GPUs), these chips are capable of performing more than the specific graphics computations for which they were designed. They are now capable coprocessors, and their high speed makes them useful for a variety of applications. The goal of this page is to catalog the current and historical use of GPUs for general-purpose computation."

 

posted on Monday, May 10, 2004 10:17:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Sunday, May 09, 2004

MbUnit has a Visual Studio Add-In using the NUnitAddIn framework. Setting the framework is done through the following steps:

  1. Get the latest NUnitAddIn installed on your machine,
  2. Copy the MbUnit binaries to the NUnitAddIn folder,
  3. Edit the NUnitAddIn.config file as follows:
    <?xml version="1.0"?>
    <configuration>
      <nunitaddin>
        <frameworktestrunners>
          <testRunner name="MbUnit"
                         typeName="MbUnit.AddIn.MbUnitTestRunner" 
                         assemblyPath="MbUnit.AddIn.dll"  />
          <testRunner name="NUnit"
                         typeName="NUnitAddIn.NUnit.TestRunner.SimpleNUnitTestRunner" 
                         assemblyPath="NUnitAddIn.NUnit.dll"  />
          ...
        </frameworktestrunners>
      </nunitaddin>
    </configuration>

That's it. You can now right click on an assembly, namespace or fixture and execute it using "Run Tests...".

posted on Sunday, May 09, 2004 10:54:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [6]

The major addition of this release if the implementation of a Visual Studio Add-in.

Download the files.

posted on Sunday, May 09, 2004 10:40:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]

As GPU power goes "exponentially" up, using it as a number cruncher becomes a reality.

http://www.cs.washington.edu/homes/oskin/thompson-micro2002.pdf

posted on Sunday, May 09, 2004 10:36:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]

The last few days have been very exciting for MbUnit. I have been working (remotely) with Jamie Cansdale, creator of NUnitAddIn, to create a Visual Studio Add-in for MbUnit. It turned out to be surpringly simple, thanks to the extensible architecture of NUnitAddIn and the expertise of Jamie.

A quick NUnitAddIn introduction

NUnitAddIn is not just an Add-in for NUnit as it's name seems to tell. It is far more than that. It is a extensible framework to build Add-ins. All the words are important here: extensible, because it is designed to accept any type of Add-in (at least test runners) and framework because it takes care of all the complicated/technical task of launching processes, attaching debuggers, etc. In fact, writing an Add-in with NUnitAddIn is as simple as implementing an interface!

Add-in How-to

I will give here a detailled how-to on the Add-in creation. This is the summary of few hours of coding and dozens of MSN messages with Jamie Cansdale (very active support!). Now let's go for the fun (I will assume you have NUnitAddIn installed in c:\Program Files\NUnitAddIn)

Setup the project

  1. Create a new Assembly project and name it as you like. In this example, it will be named MbUnit.AddIn
  2. Add the following references
    • NUnitAddIn.TestRunner.dll
    • NUnitAddIn.TestRunner.Framework.dll
  3. Change to ouput directory to the NUnitAddIn directory: Projet -> Properties -> Common Properties -> Output Path -> Select NUnitAddIn directory
  4. Make the assembly strongly named

Setup NUnitAddIn

You need to edit NUnitAddIn.config in the NUnitAddIn directory (do not edit NUnitAddIn.exe.config). The file looks like this:

<?xml version="1.0"?>
<configuration>
  <nunitaddin>
    <frameworktestrunners>
      <testrunner name="NUnit"
                     typeName="NUnitAddin.NUnit.TestRunner.SimpleNUnitTestRunner" 
                     assemblyPath="NUnitAddin.NUnit.dll"  />
      ...
    </frameworktestrunners>
  </nunitaddin>
</configuration>

Add your Add-in on top of the "food chain":

<?xml version="1.0"?>
<configuration>
  <nunitaddin>
    <frameworktestrunners>
      <testrunner name="MbUnit"
                     typeName="MbUnit.AddIn.MbUnitTestRunner" 
                     assemblyPath="MbUnit.AddIn.dll"  />
      <testrunner name="NUnit"
                     typeName="NUnitAddin.NUnit.TestRunner.SimpleNUnitTestRunner" 
                     assemblyPath="NUnitAddin.NUnit.dll"  />
      ...
    </frameworktestrunners>
  </nunitaddin>
</configuration>

Every is now setup. NUnitAddIn will use the MbUnit.AddIn.MbUnitTestRunner class as test runner.

Getting started with ITestRunner

The last step of the job is to implement ITestRunner. We will name our runner accordingly to the name with have putted in the config file.

  1. Create the class
    using NUnitAddIn.TestRunner.Framework;
    
    public class MbUnitTestRunner : ITestRunner, MarshalByRefObject
    {...}
  2. Tag the class with the assemblies used by your test runner using the DependencyAttribute attribute. For MbUnit there are quite a few:
    [
    DependentAssembly("NUnitAddin.TestRunner"),
    DependentAssembly("NUnitAddin.TestRunner.Framework"),
    DependentAssembly("QuickGraph.Exceptions"), 
    DependentAssembly("QuickGraph.Concepts"),
    DependentAssembly("QuickGraph.Predicates"),
    DependentAssembly("QuickGraph.Collections"),
    DependentAssembly("QuickGraph.Representations"),
    DependentAssembly("QuickGraph.Algorithms"),
    DependentAssembly("QuickGraph.Serialization"),
    DependentAssembly("QuickGraph"),
    DependentAssembly("MbUnit.Core")
    ]
    public class MbUnitTestRunner : MarshalByRefObject, ITestRunner
    
    The two reference to NUnitAddin.TestRunner and NUnitAddIn.TestRunner.Framework are obligatory.
  3. Make the object "long living" by making InitializeLifetimeService return null:
    public class MbUnitTestRunner : ITestRunner, MarshalByRefObject
    {
        public override Object InitializeLifeTimeService()
        {
            return null; 
        }
    }
  4. ITestRunner define two methods, Abort and Run. Abort does not need to be implemented, so yoiu can throw a NotImplementedException in it. Run is where the job is done.
    public void Abort() 
    { 
        throw new NotImplementedException(); 
    } 
    
    public TestResultSummary Run( 
        ITestListener testListener, 
        ITraceListener traceListener, 
        string assemblyPath, 
        string testPath 
    ) 
    {
        ...
    }
    In the Run method, testListener is used to send test results to NUnitAddIn, ITraceListener is used to ouput messages to the console window, assemblyPath is the path to the test assembly and testPath is a string describing what has to be tested formatted as follows:
    ('N' | 'T' | 'M') : Type
    For example, values of testPath can be
    • N:MyTests.Tests, the namespace (and sub-namespaces) MyTests.Tests has to be run,
    • T:MyTests.Tests.SimpleFixture, the class SimpleFixture has to be run,
    • M:MyTests.Tests.SimpleFixture.SomeTest, the method SimpleFixture.SomeTest has to be run
    • null, the entire assembly is run
  5. Let's start with an "hello world" test runner:
    public TestResultSummary Run( 
        ITestListener testListener, 
        ITraceListener traceListener, 
        string assemblyPath, 
        string testPath 
    ) 
    {
        traceListener.WriteLine("Hello World!");
    }
    

We are ready to make the first run of the Add-in. Open you dummy test project and right click either on the assembly, on a namespace, a type or a method and hit the "Run Tests..." rocket. If everything goes to plan, you should something like this appear in the output window:

------ Test started: Assembly: MbUnit.Tests.dll ------
Hello World!
---------------------- Done ----------------------

If you are lucky it worked out-of-the box, otherwize the next section deals with the Add-in debugging.

Debugging the Add-in

Different failure can appear at different levels. I have encountered several but hopefully, I had Jamie on my back helping me all the way. Here's a simple procedure:

  1. Add a break point on the "Hello World" line inside the Run method,
  2. Right-click on a test class, choose Test With... -> Debugger. If you are lucky, the debugger will hit the break point and you can do "classic" debugging.
  3. If the debugger did not hit the break point, it is likely that NUnitAddIn failed to load the Add-In. You need to make the debugger break on exceptions:
    1. go to Debug -> Exceptions
    2. choose Commmon Language Runtime
    3. When exception is thrown, break into debugger
  4. Run the tests again, this should give you the exception that make the Add-in loading fail.

Important note: when you recomile your project, you may have an error saying the assembly file cannot be copied because it is used by another process. At this point, you need to restart NUnitAddIn. To do this, right click on the rocket icon in the taskbar and click "Close". Recompile and yes it works!

Implementing the Run method

The rest of the work is mainly up to you. You need to load the assembly, look for the test fixture according to the "testPath" and execute them. The important thing is that the notification is done throught ITestListener.

Just for the fun, here's the output of the Add-in on the TestFixtureTest in MbUnit.Tests assembly:

------ Test started: Assembly: MbUnit.Tests.dll ------
C:\Documents and Settings\Peli\Mes documents\Tigris\mbunit\src\MbUnit.Tests\bin\StrongDebug\MbUnit.Tests.dll: [mbunit] Test Execution
[mbunit][setup] Load C:\Documents and Settings\Peli\Mes documents\Tigris\mbunit\src\MbUnit.Tests\bin\StrongDebug\MbUnit.Tests.dll assembly.
[mbunit][setup] Exploring types for fixtures.
[mbunit][setup] Setup Successfull, starting 1 tests.
[fixture] TestFixtureAttributeTest
[start] TestFixtureAttributeTest.SetUpMethod.TestMethod.TearDownMethod
[success] TestFixtureAttributeTest.SetUpMethod.TestMethod.TearDownMethod
[start] TestFixtureAttributeTest.SetUpMethod.FailedTest.TearDownMethod
[failure] TestFixtureAttributeTest.SetUpMethod.FailedTest.TearDownMethod
TestCase 'TestFixtureAttributeTest.SetUpMethod.FailedTest.TearDownMethod' failed: 
Equal assertion failed.
[[0]]!=[[1]]
MbUnit.Core.Exceptions.NotEqualAssertionException
C:\Documents and Settings\Peli\Mes documents\Tigris\mbunit\src\MbUnit.Core\Framework\Assert.cs(649,0): at MbUnit.Core.Framework.Assert.FailNotEquals(Object expected, Object actual, String format, Object[] args)
C:\Documents and Settings\Peli\Mes documents\Tigris\mbunit\src\MbUnit.Core\Framework\Assert.cs(208,0): at MbUnit.Core.Framework.Assert.AreEqual(Int32 expected, Int32 actual, String format, Object[] args)
C:\Documents and Settings\Peli\Mes documents\Tigris\mbunit\src\MbUnit.Core\Framework\Assert.cs(220,0): at MbUnit.Core.Framework.Assert.AreEqual(Int32 expected, Int32 actual)
c:\documents and settings\peli\mes documents\tigris\mbunit\src\mbunit.tests\testfixtureattributetest.cs(33,0): at MbUnit.Tests.TestFixtureAttributeTest.FailedTest()

1 succeeded, 1 failed, 0 skipped, took 0,00 seconds.


---------------------- Done ----------------------
posted on Sunday, May 09, 2004 9:13:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [3]
# Friday, May 07, 2004

Drawing a graph, although it sounds intuitive, is a tricky task. It usually involves a number of sophisticated algorithms and even more numerous parameters to set up the layout.

QuickGraph comes with a Managed C++ wrapper of Graphviz, a famous graph drawing library from AT&T. In this blog, I will show how to draw a graph in a few lines.

Let's build a dependency graph between some good old C files:

// create a new adjacency graph
AdjacencyGraph g = new AdjacencyGraph(false);
// adding files and storing names
IVertex boz_h = g.AddVertex(); 
IVertex zag_cpp = g.AddVertex(); 
IVertex yow_h = g.AddVertex();
...

// adding dependencies
g.AddEdge(dax_h, foo_cpp); 
g.AddEdge(dax_h, bar_cpp); 
...

At this point, the graph structure is built and ready to be drawed by graphviz. You need to create an instance of QuickGraph.Algorithms.Graphviz.GraphvizAlgorithm and call it's write method:

// creating graphviz algorithm
GraphvizAlgorithm gw = new GraphvizAlgorithm(
    g, // graph to draw
    ".", // output file path
    GraphvizImageType.Png // output file type
    );
// outputing to graph.
gw.Write("filedependency");

And the result is:

That's not so bad but we would like to see the names of the files. First thing to do, is to tell QuickGraph to produce NamedVertex vertices instead of Vertex. This is done by feeding the AdjacencyGraph constructor with two class factories, one for the vertices, one for the edges:

AdjacencyGraph g = new AdjacencyGraph(
    new NamedVertexProvider(),
    new EdgeVertexProvider(),
    false);

The NamedVertex class a Name property that we can use to store the name of the file:

// adding files and storing names
NamedVertex boz_h = (NamedVertex)g.AddVertex();     boz_h.Name = "boz.h"; 
NamedVertex zag_cpp = (NamedVertex)g.AddVertex();   zag_cpp.Name = "zag.cpp";
NamedVertex yow_h = (NamedVertex)g.AddVertex();     yow_h.Name = "yow.h";

The last step is add attach an event handler to the event of GraphvizAlgorithm that renders the vertices and add the name property:

// outputing graph to png
GraphvizAlgorithm gw = new GraphvizAlgorithm(
    g, // graph to draw
    ".", // output file path
    GraphvizImageType.Png // output file type
    );
gw.FormatVertex +=new FormatVertexEventHandler(gw_FormatVertex);
gw.Write("filedependency");
}
private void gw_FormatVertex(object sender, FormatVertexEventArgs e)
{
    NamedVertex v = (NamedVertex)e.Vertex;
    e.VertexFormatter.Label = v.Name;
}

and now the result is much better:

posted on Friday, May 07, 2004 8:10:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [2]

Let's have some fun with graph theory. Today, I'm showing how to generate a random maze with Quickgraph. Before going into the code, let see how we are going to make it.

The maths

Consider that you have a regular lattice like in the image below. If you consider each edge as a path, the lattice represents a highly connected network. The question is: which edge should you delete to make it a maze ?

The answer to this questions is trivial in terms of graph theory: you just need to extract a tree out of the graph and this will be a maze.  In fact in a tree, there is only 1 way from the root to each of the leaf, like in mazes. This leaves us with the problem of extracting a tree from a graph.

The maze generation example was originaly brought up by David Wilson (a researcher from Microsoft). He has designed an efficient algorithm, known as Cycle-Popping Tree Generator, for extracting random tree out of graphs. This algorithm is implemented in QuickGraph so we have all the tools on our hand to start solving the problem.

The code

Let's start by building the graph and the lattice. For the cycle popping algorithm, we need a BidirectionalGraph (a graph where you can iterate the out-edges and the in-edges of the vertices). For the lattice, we create a two dimensional array of vertices and finally, we store the vertex -> lattice index relation into a Hashtable:

// We need a few namespaces for QuickGraph 
using QuickGraph.Concepts;
using QuickGraph.Concepts.Traversals;
using QuickGraph.Algorithms.RandomWalks;
using QuickGraph;
using QuickGraph.Providers;
using QuickGraph.Collections;
using QuickGraph.Representations;

public class MazeGenerator
{
    // the bidirecitonal graph
    private BidirectionalGraph graph = null;
    // 2D array of vertices
    private IVertex[,] latice;
    // v -> (i,j)
    private Hashtable vertexIndices = null;

Next, we write the method that will populate the graph. If the lattice has m rows and n columns, the method will create m*n vertices and (m-1)*(n-1)*2 edges to link those vertices:

public void GenerateGraph(int rows, int columns)
{
    this.latice=new IVertex[rows,columns];
    this.vertexIndices = new Hashtable();
    this.graph = new BidirectionalGraph(false); // false = does not allow parallel edges

    // adding vertices
    for(int i=0;icolumns;++j)
        {
            IVertex v =this.graph.AddVertex();
            this.latice[i,j] = v;
            this.vertexIndices[v]=new DictionaryEntry(i,j);
        }
    }

    // adding edges
    for(int i =0;icolumns-1;++j)
        {
            this.graph.AddEdge(latice[i,j], latice[i,j+1]);
            this.graph.AddEdge(latice[i,j+1], latice[i,j]);
            this.graph.AddEdge(latice[i,j], latice[i+1,j]);
            this.graph.AddEdge(latice[i+1,j], latice[i,j]);
        }
    }
    ...

There is a bit of index gymnastics in the code above, but drawing it on a sheet of paper should make things clear. I will not focus on the drawing code on this blog: I'm using basic features of System.Drawing namespace, nothing really "extreme". So back to our maze problem, we need to apply the cycle-popping algorithm to generate a maze.

Cycle-popping algorithm

The cycle poping algorithm is implement in the QuickGraph.Algorithms.RandomWalks.CyclePoppingRandomTreeAlgorithm class. Using this algorithm is quite straightforward:

// (outi,outj) is the coordinate of the exit vertex in the lattice
// (ini,inj) is the coordinate of the entry vertex in the lattice
public void GenerateWalls(int outi, int outj, int ini, int inj)
{
    // we build the algo and attach it to the graph
    CyclePoppingRandomTreeAlgorithm pop = new CyclePoppingRandomTreeAlgorithm(this.graph);

    // finding the root vertex
    IVertex root = this.latice[outi,outj];
    if (root==null)
        throw new ArgumentException("outi,outj vertex not found");

    // this lines lanches the tree generation 
    pop.RandomTreeWithRoot(root);

At this point, pop contains a dictionary which associates each vertex to it's successor edge in the tree. Remember that the tree is directed towards the root here. This dictionary has two roles: it contains the edges that are part of the maze (that's what we needed) and even better you can build the way-out using the dictionary by following the successors until you hit the root:

    // we add two fields to the class:
    private VertexEdgeDictionary successors = null;
    private EdgeCollection outPath = null;
    ...
    ///////////////////////////////////
    // GenerateMaze continued
    // storing the successors
    this.successors = pop.Successors;

    // build the path to ini, inj
    IVertex v = this.latice[ini,inj];
    if (v==null)
    throw new ArgumentException("ini,inj vertex not found");

    // building the solution path
    this.outPath = new EdgeCollection();
    while (v!=root)
    {
        IEdge e = this.successors[v];
        this.outPath.Add(e);
        v = e.Target;
    }
}

That's it. We can now draw the walls of the maze and draw the solution on top. Thank you Mister Propp and Mister Wilson! (The source of this example is available in the QuickGraph CVS)

posted on Friday, May 07, 2004 9:13:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [8]