Algorithms: recursive and iterative depth first search

March 10, 2009 at 1:31 AMAndre Loker

I feel like blogging, but don’t have anything fancy to say – so why not talk about something basic as a graph searching algorithm?

The other day I needed to traverse a graph using depth first search – certainly not the most difficult thing in the world. A very basic recursive version can look like this:

   1: public void DfsRecursive(Node node) {
   2:   DoSomethingWithNode(node);
   3:   foreach(Transition t in node.Transitions){
   4:     Node destNode = t.Destination;
   5:     DfsRecursive(destNode);
   6:   }
   7: }

Assuming that a Node has a number of Transition instances that lead to the next node. BTW: I only consider trees here (i.e. graphs without loops). All snippets shown here can be used for graphs by keeping track of visited transitions and continue only for new ones (HashSet<Transition> is your friend).

My nodes did not contain the transitions as a list or array. Instead a node only had a link to the first transition, each transition had a link to the next transition – a linked list of transitions. Furthermore I needed to perform actions not only when a node was entered but also i) when the transition was followed, ii) when a transition was “undone” and iii) when a node was left. The latter two occur during the backtracking phase. Luckily with the recursive implementation, this was quite easy:

   1: public void Traverse(Node node) {
   2:   EnterNode(node);
   3:  
   4:   var t = node.FirstTransition;
   5:   while(t != null) {
   6:     var destNode = TakeTransition(t);
   7:     Traverse(destNode);
   8:     UndoTransition(t);
   9:     t = t.NextSibling;
  10:   }
  11:  
  12:   ExitNode(node);
  13: }

However, I needed to traverse very deep trees with depths of up to 500.000 nodes which made the recursive implementation unfeasible (it bails out with a StackOverflowException at graphs deeper than a couple of thousand nodes).

The “classical” iterative version of DFS looks like this:

   1: public void DfsIterative(Node node) {
   2:   var trail = new Stack<Transition>();
   3:   DoSomethingWithNode(node);
   4:   PushAllTransitionsToStack(node, trail);
   5:   while(trail.Count>0) {
   6:     Transition t = trail.Pop();
   7:     Node destination = t.Destination;
   8:     DoSomethingWithNode(destination);
   9:     PushAllTransitionsToStack(destination, trail);
  10:   }
  11: }

This is more or less what you will see when someone mentions iterative DFS. Note by the way that this version supports multiple transitions to the same destination node correctly – otherwise the algorithm could be even simpler. Also the order in which transitions of a node are visited is reversed.

The problem was that I needed to place my calls to UndoTransition and ExitNode somehow. Using the approach shown above makes that somewhat difficult. The problem is that the stack does not represent the actual path that is taken through the graph. Instead it contains transitions on the path as well as siblings that are yet to be visited. Interestingly enough I didn’t find something on the net the fitted my need – most sites mentioning iterative DFS use the approach described above. So, here’s what I came with after some time of thinking:

   1: public void Traverse(Node root) {
   2:   var trail = new Stack<Transition>();
   3:   EnterNode(root);
   4:   trail.Push(root.FirstTransition);
   5:  
   6:   while(trail.Count > 0) {
   7:     Transition current = trail.Peek();
   8:  
   9:     Node reachedNode = TakeTransition(current);
  10:     EnterNode(reachedNode);
  11:  
  12:     // try to descend ... 
  13:     Transition next = reachedNode.FirstTransition;
  14:  
  15:     // ... or backtrack
  16:     while(next == null && trail.Count > 0) {
  17:       Transition top = trail.Pop();
  18:       ExitNode(top.Destination);
  19:       UndoTransition(top);
  20:       next = top.NextSibling;
  21:     }
  22:  
  23:     if(next != null) {
  24:       trail.Push(next);
  25:     }
  26:   }
  27:   ExitNode(root);
  28: }

What’s cool about this approach:

  • You can always tell the current depth of the traversal by simply checking trail.Count
  • Trail contains the exact path to the current node, so it’s easy to dump the trail for an interesting node

In my project I used some extensions to this basic version:

  • I used it to traverse graphs (not only trees), so I added a check whether a given state has already been visited before
  • I extended it to traverse over multiple graphs at once. Useful to explore the complete state space of the parallel composition of two graphs. Maybe I’ll go into details in a future post.

Is it something new? Certainly not. Is it rocket science? No! Could it be useful for you to have the skeleton of an iterative DFS with the ability to define backtracking actions at hand next time you need it? I hope so. Have fun!

Posted in: Snippets

Tags:

Simple AOP: call interception with DynamicProxy

February 14, 2009 at 2:37 AMAndre Loker

Aspect oriented programming (AOP) allows us to keep implement different concerns in isolation. In this article series I’ll describe ways to make use of AOP without much hassle. After the introduction to AOP in the first article I’ll show how we can use Castle DynamicProxy to intercept method calls for the injection of advice code.

Introduction

If you’re reading this, you are probably interested in AOP and want to know how you can practise separation of concerns in you .NET application. There are quite some AOP frameworks available for .NET, so you might just grab the one that best fits your need. Below you’ll find an (incomplete!) overview of existing AOP frameworks for .NET

Examples for frameworks using compile time weaving/IL level manipulation:

Those frameworks weave the aspect code into compiled assemblies by modifying the IL code.

Examples for frameworks using proxy-based runtime weaving

The common technique behind those framework is this: for each class that needs to have advices applied to it the framework creates a subclass at runtime using the runtime code generation facilities of .NET. Each virtual call or interface method implementation is overridden. Those overridden methods can then redirect the call to the advices. As a result those frameworks normally only support a very small join point model, limited to the calls of virtual methods or interface methods. However, in many practical cases, this limitation is not that much of an issue.

Choose your destiny

Here we already have six frameworks to choose from. The question is: which one should I use or should I even use a different approach? I haven’t used all of those frameworks, so I can’t go into a detailed analysis of their commonalities and differences. Nevertheless, here are some general thoughts:

  1. If a specific concern is suitable for static weaving you probably want to go that way. As mentioned in the first article, compile time weaving has several benefits, especially allowing a much richer join point model and slightly less overhead.
  2. If you use Spring.NET or S2Container as your IoC container, using the respective AOP facility is probably the recommended way.
  3. If you need dynamic weaving and use the Castle stack read on, that’s what the rest of this article is about!

Castle facilities

Interestingly enough, Castle once had an AOP facility itself. It has been discontinued a while ago because apparently it wasn’t used much. It’s not that people find AOP as a concept useless, but it seems that a fully blown AOP framework is not required in many cases. Instead, people find a different facility to be sufficient, namely DynamicProxy2.

DynamicProxy2 (DP2) is a library that generates proxy types at runtime. DP2 supports different proxy strategies. In the case of AOP, two strategies are the most important:

  1. Create a class proxy: DP2 derives a proxy class from a given type.

class proxy

  1. Create an interface proxy with a target: instead of deriving from the target type, this strategy creates an implementation of one (or multiple) of the interfaces that the target type implements. This strategy resembles the classic Proxy pattern, because the instance created by DP2 replaces the target object.

interface proxy

Interceptors

Just creating new types at runtime is rather useless if that’s all. Of course, there is more. When you use DP2 to create the proxy instances you can provide one or more interceptors. An interceptor is an object implementing IInterceptor, which looks like this:

   1: public interface IInterceptor
   2: {
   3:     void Intercept(IInvocation invocation);
   4: }

Each virtual or interface method that the DP2 proxy generator overrides or implements respectively will call the Intercept() method of the interceptors you pass to the generator method. The IInvocation instance passed to the interceptor contains information about the method being intercepted:

   1: public interface IInvocation
   2: {
   3:     // Methods
   4:     object GetArgumentValue(int index);
   5:     MethodInfo GetConcreteMethod();
   6:     MethodInfo GetConcreteMethodInvocationTarget();
   7:     void Proceed();
   8:     void SetArgumentValue(int index, object value);
   9:  
  10:     // Properties
  11:     object[] Arguments { get; }
  12:     Type[] GenericArguments { get; }
  13:     object InvocationTarget { get; }
  14:     MethodInfo Method { get; }
  15:     MethodInfo MethodInvocationTarget { get; }
  16:     object Proxy { get; }
  17:     object ReturnValue { get; set; }
  18:     Type TargetType { get; }
  19: }

One of the most important members is Proceed() which will call the next IInterceptor for the current proxy or – if the current interceptor is the last one – it will invoke the “real” method.

DP2 in practice

Let’s put all this theoretic mumbo-jumbo into practice, shall we?

First, here’s our ultra complex domain model:

   1: // A service interface...
   2: public interface IService {
   3:   void DoSomething();
   4: }
   5:  
   6: // ... and its implementation
   7: public class Service : IService {
   8:   public void DoSomething() {
   9:     Console.Out.WriteLine("Service.DoSomething()");
  10:   }
  11: }

Nothing fancy here. Here’s our application code:

   1: public class Program {
   2:   public static void Main() {
   3:     IService service = CreateService();
   4:     service.DoSomething();
   5:   }
   6:  
   7:   private static IService CreateService() {
   8:     return new Service();
   9:   }
  10: }

If we run this – surprise – this is the result (the last line is “Press any key” in German)

image

Now we introduce DynamicProxy2. First off, add a reference to Castle.Core.dll and Castle.DynamicProxy2.dll.  Now we can write our first interceptor:

   1: public class LogInterceptor : IInterceptor {
   2:   public void Intercept(IInvocation invocation) {
   3:     Console.WriteLine("Intercepting {0}", invocation.Method.Name);
   4:   }
   5: }

Not bad so far. Finally, we need to inject the interceptor into the target. To do this, modify CreateService like this:

   1: private static IService CreateService() {
   2:   var dp = new ProxyGenerator();
   3:   var target = new Service();
   4:   var interceptor = new LogInterceptor();
   5:   return dp.CreateInterfaceProxyWithTarget<IService>(target, interceptor);
   6: } 

Now run the code again:

image

Wait, where’s “Service.DoSomething()”? We forgot one thing: if we don’t call Proceed() on the IInvocation object in Intercept(), the original method (or the next interceptor) won’t be called, so adjust the LogInterceptor like this:

   1: public void Intercept(IInvocation invocation) {
   2:   Console.WriteLine("Intercepting {0}", invocation.Method.Name);
   3:   // invoke next interceptor/intercepted method
   4:   invocation.Proceed();
   5: }

And voilá:

image

You see, calling Proceed() is necessary to have the intercepted method executed. This has several positive side effects:

  1. We can intentionally decide to block the call to the intercepted methods, for example for security reasons
  2. In the interceptor we can provide that has to be called before and after the execution of the intercepted method (“around advice” anyone?)
  3. We can “fork”, i.e. we can invoke the intercepted method multiple times

If we have more than one interceptor, calling Proceed() will only invoke the intercepted method if the current interceptor is the last one. Calling Proceed() in interceptors that are earlier in the chain will instead invoke the next interceptor. Here’s a collaboration diagram of a proxy with two interceptors:

image

Personally I think that having Proceed() do the right thing transparently is a wise choice.

The link to AOP

You’ve probably already noticed where this is going. We can use DP2 and the interceptors to implement our advices. Out advices are in fact implementations of IInterceptor and the ProxyGenerator acts as the weaver. Here’s another (not really useful) advice using IInterceptor:

   1: public class ExceptionAdvice : IInterceptor {
   2:  
   3:   public bool EatAll { get; set; }
   4:  
   5:   public void Intercept(IInvocation invocation) {
   6:     try {
   7:       invocation.Proceed();
   8:     } catch (Exception e) {
   9:       Console.WriteLine("{0} caught: {1}", e.GetType().Name, e.Message);
  10:       if (!EatAll) {
  11:         throw;
  12:       }
  13:     }
  14:   }
  15: }

Let’s add it into our case:

   1: private static IService CreateService() {
   2:   var dp = new ProxyGenerator();
   3:   var target = new Service();
   4:   var interceptor = new LogInterceptor();
   5:   // swallow all exceptions
   6:   var exceptionAdvice = new ExceptionAdvice {EatAll = true};
   7:   return dp.CreateInterfaceProxyWithTarget<IService>(target, interceptor, exceptionAdvice);
   8: }

If Service.SomeMethod now throws an exception we see this:

image

I’m sure you can come up with a bunch of more realistic concerns that could be implemented using IInterceptors.

Loose ends

Intercepting join points is probably one of the technically most difficult parts of an AOP framework. Luckily Castle DynamicProxy is a feasible tool for this. Let’s see how this intermediate solution compares to a “real” AOP framework:

  • All methods of the target are intercepted. Sometimes you want only a subset of the methods based e.g. on an attribute or the name of the method. Therefore the Intercept method needs to further filter invocations. It would be cool if we could somehow more declaratively define our pointcuts.
  • We have to explicitly generate the proxies with the interceptors. We’d like to have this done automatically. Luckily Castle Windsor, the IoC container of the Castle stack, has this feature built in, so we can make the interceptors part of the component model.
  • We can only intercept virtual methods or interface methods. Well, there’s not much we can do about it, this is an inherent problem of the proxy based weaving approach. If you need a richer join point model, have a look at frameworks supporting compile time weaving.
  • We currently only support around advices. That’s not too bad, given that it is the “mother” of all advices we can “derive” all kind of advice types. For example, you can provide a set of abstract advice classes from which the concrete advices are derived. Just derive from the correct advice type and implement the abstract method (decide for yourself whether this approach is useful for you):
   1: public abstract class AroundAdvice : IInterceptor {
   2:   void IInterceptor.Intercept(IInvocation invocation) {
   3:     Around(invocation);
   4:   }
   5:  
   6:   protected abstract void Around(IInvocation invocation);
   7: }
   8:  
   9: public abstract class BeforeAdvice : IInterceptor {
  10:   void IInterceptor.Intercept(IInvocation invocation) {
  11:     Before(invocation);
  12:     invocation.Proceed();
  13:   }
  14:  
  15:   protected abstract void Before(IInvocation invocation);
  16: }
  17:  
  18: public abstract class AfterAdvice : IInterceptor {
  19:   void IInterceptor.Intercept(IInvocation invocation) {
  20:     try {
  21:       invocation.Proceed();
  22:     } finally {
  23:       After(invocation);
  24:     }
  25:   }
  26:  
  27:   protected abstract void After(IInvocation invocation);
  28: }
  29:  
  30: public abstract class AfterReturningAdvice : IInterceptor {
  31:   void IInterceptor.Intercept(IInvocation invocation) {
  32:     invocation.Proceed();
  33:     AfterReturning(invocation);
  34:   }
  35:  
  36:   protected abstract void AfterReturning(IInvocation invocation);
  37: }
  38:  
  39: public abstract class AfterThrowingAdvice : IInterceptor {
  40:   void IInterceptor.Intercept(IInvocation invocation) {
  41:     try {
  42:       invocation.Proceed();
  43:     } catch (Exception e) {
  44:       AfterThrowing(invocation, e);
  45:     }
  46:   }
  47:  
  48:   protected abstract void AfterThrowing(IInvocation invocation, Exception e);
  49: }

Preview

The next part of the series will cover integration of interceptors into Castle Windsor. Have fun!

Attached you'll find the source code for this article.

DynamicProxyEx1.zip (243.14 kb)

Other articles in this series:

Posted in: Castle | Design | Snippets

Tags: , , , , , ,

Using Nant for Metabase backup on 64bit Windows Server 2003

January 28, 2009 at 4:26 PMAndre Loker

For while now I’ve been using NAnt not only as a build tool but also as the tool running all my backup tasks, such as:

  • database backups
  • Subversion repository backups
  • mail backup
  • website backup

I’ve also used it to create backups of the IIS Metabase using the iisback.vbs script, which works perfectly smooth as long as it is running on a 32 bit Windows.

I’ve been trying to backup the IIS Metabase on a 64 bit Windows Server 2003 server for a while now, but for some reasons I could not make it work. If I tried to call the script directly using the commandline, e.g.

   1: iisback.vbs /backup /s localhost /e something /v NEXT_VERSION 
   2:       /b Metabase123 //E:vbscript

it would ran perfectly fine. However, when executed as a NAnt task I got an error:

Could not create an instance of the CmdLib object.
Please register the Microsoft.CmdLib component.

After digging in the dark for a while I found an interesting forum thread of somebody with a similar problem. So I more or less did what has been proposed in that thread:

  1. I copied cmdlib.wsc over from %WINDIR%\System32 to %WINDIR%\SysWOW64
  2. I also copied isschlp.wsc the same way
  3. I registered cmdlib.wsc and isschlp.wsc using regsvr32 cmdlib.wsc and regsvr32 isschlp.wsc respectively

At that point my NAnt script was happy again and created the backups.

The reason and more trouble

As far as I understand the problem was that NAnt is for some reason running as a 32 bit application. On 64bit Windows boxes, the System32 folder contains the 64bit binaries whereas the SysWOW64 folder contains the 32bit versions. Frankly, this is not the most intuitive naming ever, but it has a reason. If a 32 bit application is running the System32 folder becomes an alias for the SysWOW64 folder, with the effect that for 32 bit applications, Windows looks totally normal (ie. 32 bit). However, this also means that binaries that are found in the unaliased System32 folder are not accessible for 32 bit application. Hence the need to copy and reregister cmdlib.wsc and isshlp.wsc.

Now that I had this one working I directly faced a second problem: the backups of the metabase are stored at %WINDIR%\System32\inetserv\MetaBack. I think you can guess what’s the problem: the folder is hidden for 32 bit applications, which means that I can’t copy the Metabase backups using NAnt, because NAnt only sees the aliased version of System32.

So here’s what I did to solve this issue: I couldn’t find a way to disable the file system aliasing though standard means in NAnt, but I found an API that could help me:

Using the first of those two method disables the aliasing for the current thread. So I wrote a small C# program that first disables the aliasing (by P/Invoking the methods mentioned above) and then copies the backed up files out of the System32 folder into a conventional folder. I could then continue to use NAnt to further process those files (e.g. zipping them, mailing them somewhere – whatever).

Here’s the code of the class that disables/reverts the file system aliasing:

   1: /// <summary>
   2: /// Disables file system aliasing for 32 bit applications
   3: /// on 64 bit systems.
   4: /// </summary>
   5: public class DisableWow64Redirect : IDisposable {
   6:   #region P/invoke
   7:   [DllImport("Kernel32")]
   8:   private static extern bool Wow64DisableWow64FsRedirection(out IntPtr oldValue);
   9:  
  10:   [DllImport("Kernel32")]
  11:   private static extern bool Wow64RevertWow64FsRedirection(IntPtr oldValue)
  12:   #endregion
  13:  
  14:   private readonly IntPtr oldValue;
  15:  
  16:   /// <summary>
  17:   /// Creating a new object disables file system aliasing for the current thread.
  18:   /// </summary>
  19:   /// <remarks>
  20:   /// Use <see cref="Dispose"/> to re-enable file system aliasing.</remarks>
  21:   public DisableWow64Redirect() {
  22:     Success = Wow64DisableWow64FsRedirection(out oldValue);
  23:   }
  24:  
  25:   public bool Success { get; private set; }
  26:  
  27:   /// <summary>
  28:   /// Disposes this object and reenables the file system aliasing.
  29:   /// </summary>
  30:   public void Dispose() {
  31:     if (Success) {
  32:       Success = Wow64RevertWow64FsRedirection(oldValue);
  33:     }
  34:   }
  35: }

Granted, this is probably not the best solution one could think of, but it works for me for the moment. If anyone has a better idea, let me know!

 

Posted in: Windows | Snippets | C#

Tags: , ,

The almighty boolean toggle

August 5, 2008 at 10:53 PMAndre Loker

Do you the feeling when you know exactly what you mean, but you can't find a succinct way to express it? The guy that posted this classic piece of code to the forum surely does:

   1: if (flag == false)
   2:   flag = true;
   3: else if (flag == true)
   4:   flag = false;

Hint: flag = !flag

Sorry for not posting anything of greater importance. I'm rather tired :-)

Posted in: Snippets

Tags:

Did you know that...

July 8, 2008 at 7:24 PMAndre Loker

... you can annotate an attribute class with an attribute of that very type?

   1: [ThisIsCool]
   2: public class ThisIsCoolAttribute : System.Attribute {
   3: }

Admittedly I did not.

Posted in: C# | Snippets

Tags: