I am a visual oriented person, so when working with graphs, trees, state engines or basically anything that can be represented as a network, I like to have an visual representation of it. In the past I usually exported such structures to a .dot file and processed it with Graphviz to a JPG or PNG. However a more convenient way would be, to be able to view and modify such drawings online, so I decided to write a widget to do this for my current project.

I quickly identified two key questions which needed answering first:
1. How to display this in the application
2. how to compute the layouting of the graph and do the routing of the edges of it

As the project I'm working on is Qt-Based the first question was easily answered. QGraphView and the connected classes are perfect for this. They even support dragging around shapes, selecting them and so on.

First iteration: Graphviz

Layouting a graph can be tricky, especially if one wants to minimize the edge crossing and wants to have nice curvy splines or at least proper angled chinks for edges. So I started to look for a 3rd party library which I could interface over C++ to do the layouting for me. Since I already knew that graphviz is very powerful this was my first try. A bit of sifting through the web and I found this nice tutorial about using graphviz with Qt: I was quickly able to get a running prototype up. But the joy soon ended, as I tried to get the prototype fully integrated into our proejct. Graphviz is completely missing 64 bit support for windows and even after spending three days I could not get graphviz to compile on my own. So I started looking for alternatives.

Second Iteration: boost::graph

After a bit of asking around I stumbled on boost::graph which was nice, as I am already familiar with boost. Layouting a graph also worked out of the box by only including some headers without any previous compilation needed. However boost::graph quickly showed its limitations by not having the functionality to route the edges at all. So hoping that this function was not actually missing but that I just had not found it yet, I was prepared to accept this and just keep going. So I started looking around for theory on routing edges which lead me to OGDF which proved to be the solution.

Final iteration: OGDF

Already the name of the Project: The Open Graph Drawing Framework looked very promising, after all this was exactly what I wanted to do. After donwloading compilation was very straight forward with options for debug & release compilation as well as 32 or 64 bit. The documentation of it is a bit flimsy but with a bit of guesswork and rooting around in the reference documentation I quickly got another prototype running with only around 20 lines of code for setting up and layouting the graph. Integrating the protoype into the existing project was straight forward, however I needed to change a few parameters when building the library, so the debug-information was removed for the release version. So after this journey over three different libraries I'm very excited to start bring this up to a full functional tool and learn more about it.

Conclusion

• QGraphView is perfect for the purpose
  
• Graphviz: nice and powerful, but lacking 64bit support and I could not compile it
  
• boost::graph: works for layouting, no spline generation for edges.
  
• OGDF: Download & build witout problems documentation a bit sparse
  

There is a follow up post to this entry which shows the code for the prototype