Recently, I decided to write a WPF control that can display graphs (I mean, the kind with edges and nodes; not charts). This post describes the beginning of that little project. It does not contain many technical details, just a few hints and pointers for anyone who would like to start a similar project.
I have the time nor the inclination to write a graph layout algorithm myself. Graph algorithms are complex and fairly specific, and I couldn't really find a good overview of the algorithms involved on the net. I found many references to papers, but it seems some papers are hard to get if you don't have a subscription to the ACM portal. (When I was still a PhD candidate this stuff was much easier). So much for free science.
Maybe I can reuse a graph layout algorithm from some existing Winforms control? After some searching, it seems that .NET lacks a free graph layout control. A good graph algorithm library is QuickGraph , but as far as I can see it does not offer any algorithm for layout. Another library is GLEE from Microsoft, but that's is not available for commercial usage (something I'd like for later when my imaginary startup will take over the world).
Outside the .NET world then? After all, .NET has excellent interoperability.
Graphviz by AT&T is an excellent graph layout utility. Not only can it do beautiful hierarchical graphs (like GLEE does) it can also do spring layout and radial graphs, is fast and is highly configurable. Graphviz reads graphs in a proprietary format, called dot. It then layouts the graph, and can export to a variety of formats, of which attributed dot is one. Attributed dot is basically the same as the dot input file, but attributed with node, edge and label positions, as well as other layout info.
Another C++ based alternative is Dynagraph which is a daughter of Graphviz but is geared toward dynamical graph layout. Whereas Graphviz takes an input graph, does layout and produces an output graph, Dynagraph can add and delete nodes and edges incrementally, keeping existing positions the same as much as possible.
| Graphviz | Dynagraph | |
| .NET interoperability |
|
|
| Maintained | Actively |
Hardly |
| Incremental | No | Yes |
| Algorithms | Hierarchical, spring, radial, circular | Hierarchical |
| Speed | Fast, even for large graphs | Noticeably slower than Graphviz for large graphs |
After some tinkering with Dynagraph, which I liked better at first because of its flexibility, and after some back and forth email with Gordon Woodhull, the maintainer of Dynagraph, it turned out that Dynagraph COM support is not completely implemented yet. By the time we came to that conclusion, I had already sort of given up and started on an interface for Graphviz using the Wingraphviz COM interface.
It turns out that a few people before me had thought of that. Quickgraph can actually output a dot file to be consumed by Graphviz. Furthermore, D ot2Wpf is a WPF control that parses output from Graphviz.
You'd think I'm done, right? So did I. However, there were a few more things I expected from my graph control than dot2wpf offered. For example, I'd like to change the color or line style of an edge without having to do a complete layout of the graph. So I figured I'd take the dot2wpf source and add some features. That didn't quite work out as planned.
That's because dot2wpf actually parses the 'plain' output format of Graphviz. It is supposedly easier to parse than the dot output format, but loses some information. It turns out that it contains a flaw: for cyclic graphs, the plain format does not allow you to determine whether an arrow should be at the beginning or the end of an edge. Graphviz' hierarchical layout algorithm cannot handle cycles, so it reverses one edge in a cycle automatically for layout purposes. However, in the plain output format there is no indication of this reversal, and the points of the edge are given in the reverse direction. There's no way for dot2wpf to distinguish these reversed edges from normal edges in the plain output format, so it has no way to determine where to draw the arrow.
That one took me a while to figure out.
So it turns out that to make a faithful representation of a graph layout by Graphviz, I need to parse the (fairly complicated) dot output format of Graphviz. So my idea now is that the WPF graph control takes as input a string containing a dot representation of the graph it should draw (such a dot representation is easy to get from e.g. Quickgraph), passes this string to Graphviz which passes an annotated dot file back. The control parses it, and draws the visuals on the canvas.
Since I've been wanting to learn F# for a while, and F# comes with a bunch of parsing tools (fslex and fsyacc), I thought it would be a good idea to use F# to write a dot parser - it could be useful for other things than the graph control. More on parsing with F# in a later post.
No comments:
New comments are not allowed.