# Sunday, November 07, 2010

http://rise4fun.com/ is a web front end to a number of tools produced by the RiSE group. It also exposes REST services that allow you to play with the tools from your favorite environment.

Rendering DOT graphs to SVG

DOT is a popular language to describe graphs. It can be rendered into SVG using the MSAGL tool on http://rise4fun.com . To do so, you simply need to do a POST query to http://rise4fun.com/services.svc/ask/agl where the dot code is passed in the request body. rise4fun returns SVG markup that can be viewed in browsers that support it.

Wondering what graph SVG look like? Check out http://rise4fun.com/agl/cilreader to see this beautiful graph. Make sure to zoom out as the graph is rather laaaaaarge.

image

Cheers, Peli

posted on Sunday, November 07, 2010 12:09:47 PM (Pacific Standard Time, UTC-08:00)  #    Comments [0]
# Sunday, January 04, 2009

The k-shortest paths computes the k first shortest path between two vertices in a directed graph. If you put this in the context of route planning, it gives you k alternative routes in case the shortest path is blocked by snow :) While the single source shortest path is well-known and implemented in many languages, there are not many implementations available for this problem, although it has been extensively studied. After looking around, I stumbled on a nice article comparing various approaches. The authors pointed out an algorithm from 1959 from Hoffman and Pavley that solved this problem (there are actually many others). This algorithm looked like a good fit:

  • it requires a single call to a single-source shortest path algorithm. Other approaches will require as much as kn calls to a shortest path algorithm.
  • it sounded simple and did not require new specialized data structures.

I want to try it!

The algorithm is available in QuickGraph 3.1.40104.00 and up. You can take a look at it at http://www.codeplex.com/quickgraph/SourceControl/changeset/view/29858#377982. To use it on a BidirectionalGraph,

IBidirectionalGraph<TVertex, TEdge> g = …;
foreach(IEnumerable<TEdge> path in g.RankedShortestPathHoffmanPavley(weights, source, goal, 4))
     …

A glimpse at the Hoffmann-Pavley algorithm

The algorithm works in 2 phases.

On the first phase, we build a minimum ‘successor’ tree towards the goal vertex. This tree can be used to build a shortest path from any (reachable) vertex to the goal vertex. To build this tree, we can simply apply the Dijkstra shortest path algorithm on the reversed graph. This can be done in a couple lines with QuickGraph.

As for many other k-shortest path algorithm, phase works by building deviation path and picking the best one. In the case of the Hoffman-Pavley algorithm, it works as follows: pick the latest shortest path, for each vertex of this path, build a deviation path (more later) for each out-edge and add it to a priority queue. Then start again:

var queue = new PriorityQueue<Path>();
queue.Enqueue(shortestpath);
while(queue.Count > 0) {
    var path = queue.Dequeue();
    foreach(var vertex in path)
        foreach(var edge in graph.OutEdges(vertex))
             queue.Enqueue(CreateDeviation(path, vertex, edge));
}

A deviation path is composed of three parts:

  1. the initial part of the ‘seeding’ path, i.e. the edges before the deviation edge,
  2. the deviation edge
  3. the remaining shortest path to the goal. When we build the deviation path, we also compute it’s weight. A nice property of the deviation paths is that they can be ‘built’ when needed. This saves a lot of space and computation as most deviation paths will probably not end up in the winning set of paths – instead of storing a full path, we store a path index and an edge index.

That’s it! The details contain more code to deal with self-edges and loops but the main idea is there. This is definitely a very elegant algorithm!

What about testing!

Algorithm authors usually illustrate their approach with an example. This is a good way to get started on a small graph example and ensure that the algorithm works as the original author expected. This is the kind of unit test I get started with.

The next step is to apply the algorithm to a large number of graph instances. Unfortunately, I do not have any other k-shortest path algorithm, so the oracle is harder to build here. Nevertheless, the result of the algorithm, i.e. the shortest path collection, has a couple of properties that should always be true:

  • the algorithm produces loopless paths,
  • path k is lower or equal to path k + 1.

The problem with this test is that it does not guarantee that some shortest path have been missed. At this point, I’m a bit puzzled on how to test that.

posted on Sunday, January 04, 2009 11:05:14 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]
# Monday, September 08, 2008

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

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

BinaryHeap?

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

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

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

Let's write that first test

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

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

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

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

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

BinaryHeap version #0

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

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

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

image

BinaryHeap version #1

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

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

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

image

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

image

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

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

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

We have an invariant!

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

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

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

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

void AssertInvariant<TPriority,TValue>(BinaryHeap<TPriority,TValue> target) {
    target.ObjectInvariant();
}

Pex immediately finds an issue:

image

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

Fixing tests, and finding new failing tests

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

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

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

image

Two interesting things happened here:

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

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

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

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

to be continued...

posted on Monday, September 08, 2008 10:39:35 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]
# Sunday, April 22, 2007

3 years after being released on CodeProject, it was about time to dust off QuickGraph and give it generics support.

posted on Sunday, April 22, 2007 1:49:21 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [2]
# Monday, September 11, 2006

GLEE, a graph layout engine developed in Microsoft Research. It is now available for downloading at http://research.microsoft.com/research/downloads/download.aspx?FUID=c927728f-8872-4826-80ee-ecb842d10371.

 

posted on Monday, September 11, 2006 5:13:07 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]
# Saturday, September 09, 2006

After 2 years in the CLR, I'm moving job (and building) to Microsoft Research. I will be working on Parametrized Unit Testing.

 

posted on Saturday, September 09, 2006 11:21:39 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [3]
# Friday, June 04, 2004

This is a new experimental Reflector Add-In that will be part of the upcoming Reflector.Graph addin (see Assembly Grapher and Il Grapher). The objective of this addin is to rank methods using a method similar to google.

The graph

Consider a graph where the vertices are the methods of the classes, and each edge represents the fact that the source method calls the target method. For example, take the following dummy class:

public class Test
{
   public void Hello()
   {...}
   public void HelloWorld()
   {
       this.Hello();
   }
}

The method graph from this class will contain

  • 2 vertices: Test.Hello and Test.HelloWorld
  • 1 edge: Test.HelloWorld -> Test.Hello.

PageRank, The Algorithm

PageRank, which is the algorithm that Google uses to rank pages, is a well known and easy to implement algorithm (it is implemented in QuickGraph). The idea behing is very simple and elegant: important pages are reference by other important pages. So basically, PageRank algorithms can help you order the vertices of your graph by order of importance.

PageRank and MethodRank

Contrary to Google, where the vertices are pages and edges are the hyperlinks, the vertices are methods. However, the PageRank idea translates naturally to the method graph: important methods are called by other important methods. Why would we need to know which are the important vertices ? Here are my intuition (not tested) about this:

  • if a important method contains a bug, it is likely that a lot of test cases will fail, (this a BIG assumption)
  • using the previous point, it is clear that important methods are a good target for mutation testing,
  • if you have to start testing, it can give you a "test writting" order,
  • it's fun

The AddIn

for the pleasure of the eyes

posted on Friday, June 04, 2004 8:55:00 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [10]
# Monday, May 31, 2004

With the kind help of Lutz Roeder, I have recompiled the IL Grapher into a Reflector Add-in...

posted on Monday, May 31, 2004 11:37:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [15]