Is there a good graph layout library callable from C++?

Question

The (directed) graphs represent finite automata. Up until now my test program has been writing out dot files for testing. This is pretty good both for regression testing (keep the verified output files in subversion, ask it if there has been a change) and for visualisation. However, there are some problems...

Basically, I want something callable from C++ and which plans a layout for my states and transitions but leaves the drawing to me - something that will allow me to draw things however I want and draw on GUI (wxWidgets) windows.

I also want a license which will allow commercial use - I don't need that at present, and I may very well release as open source, but I don't want to limit my options ATM.

The problems with GraphViz are (1) the warnings about building from source on Windows, (2) all the unnecessary dependencies for rendering and parsing, and (3) the (presumed) lack of a documented API specifically and purely for layout.

Basically, I want to be able to specify my states (with bounding rectangle sizes) and transitions, and read out positions for the states and waypoints for each transition, then draw based on those co-ordinates myself. I haven't really figured out how annotations on transitions should be handled, but there should be some kind of provision for specifying bounding-box-sizes for those, associating them with transitions, and reading out positions.

Does anyone know of a library that can handle those requirements?

I'm not necessarily against implementing something for myself, but in this case I'd rather avoid it if possible.

Weidar

+1 for an excellent, well-stated question. Unfortunately, I don't have an answer. – Arquit

Boost has graph algorithms: boost.org/doc/libs/1_42_0/libs/graph/doc/index.html I think visualization is out of its scope though. – Passive

There are layout algorithms within the boost graph module, but unfortunately they are not appropriate for directed graphs. See section 22.12 here: boost.org/doc/libs/1_42_0/libs/graph/doc/table_of_contents.html – Cowpuncher

Answer 1

Although the answers so far were worth an upvote, I can't really accept any of them. I've still been searching, though.

One thing I found is AGLO. The code is GPL v1, but there are papers that describe the algorithms, so it should be easy enough to re-implement from scratch if necessary.

There's also the paper by Gansner, Koutsofios, North and Vo - "A Technique for Drawing Directed Graphs" - available from here on the Graphviz site.

I've also been looking closely at the BSD-licensed (but Java) JGraph.

One way or the other, it looks like I might be re-implementing the wheel, if not actually re-inventing it.

Weidar

People aren't always so motivated to write a BSD replacement for a GPL library, unless there's a really large market niche for the library in the first place. – Plaintiff

Answer 2

OGDF is under the GPL.

Pigale is also under the GPL.

GoVisual is commercial software, but it looks like it starts at $1800 for one developer.

Plaintiff

Awkward for commercial use, but +1 as probably not impossible (e.g. separate the GPL code into a dynamically linked binary, separate from closed code). – Weidar

Separating GPL code into a dynamically linked binary doesn't help. The whole thing is still a derived work of the GPL code. – Plaintiff

Really - so if I use GPL code to write a Photoshop plugin, the whole of Photoshop suddenly becomes a derived work of the GPL code? Adobe really won't be very happy about that! Or is it that Adobe isn't allowed to use GPL code in an open-source Photoshop plugin, but I am? – Weidar

That's as clear as mud. E.g. what about that Photoshop plugin using GPL code. There's calls both ways and data structure sharing, but that makes my plugin a part of Photoshop? Clearly not. That part of the FAQ talks about exemptions to the license for the plugin, so even GNU are clearly aware, deep down, that it is separate from the host app. And don't forget - every app is just an operating system plugin, with calls made both ways and data structures being shared with the host program - that doesn't make every GPL app "a part of" Windows or whatever. – Weidar

Still - I take the point. Clearly I cannot take the risk of using a GPL library - I cannot guarantee that I can sell my own code safely if I do so, if I decide to go that route. You keep the +1 - because GoVisual may be an option, though the price is steep for something that I may never make money from myself, and I'd be paying for stuff I don't want along with the stuff I do. – Weidar

Answer 3

Hmm, GDToolkit (or GDT) looks okay: many of the images in the tutorial look pretty nice, and it doesn't look like it's terribly complicated to use.

Edit: But checking the license, it looks like it's commercial software :-(. Whoops!

Stealth

Commercial may be better than GPL, depending on cost, so +1 again. – Weidar

Answer 4

I was dealing with a similar problem earlier this year. One important input parameter for a decision however is the expected number of nodes.

I decided to use the Browser as the GUI and therefore looked for nice Javascript libraries, one i came across was wireit, it is very well suited for technical layouts (and also editing with drag and drop and "on the fly" layouting). You could easily connect that to your c++ by running a small webserver in a thread (You will need some kind of eventloop/thread thingie for GUI anyways).

Well just my 2 cents.

Hobnail

This is more thought-provoking than practical. Requiring a webserver is not an option, but using an HTML control with Javascript support may not be, and there' also the option of embedding a Javascript engine or simply translating the code. +1 again. – Weidar

Well, i think that embedding a webserver is easier than embedding a Javascript engine (code.google.com/p/mongoos/wiki/EmbeddingMongoose). Especially with factoring out every graphics related stuff to the Browser you save a lot of dependencies. But also i won't hide from you that javascript has it's own quirks. But i think GUI development in javascipt+jQuery UI (or some other lib) is easier (and more maintainable) -- THNX for the +1 – Hobnail

One more comment: When using (X)HTML and JavaScript currently you have no solution for "free-drawing" supported on all mayor Browsers. If you on the other hand are happy with using Firefox, Safari, Chrome, Opera (all but IE) you could use SVG. Graphviz can directly produce SVG output (or easy translate), which you than could control and animate via javascript directly. Thereby you might reuse some of your current setup. (code.google.com/p/svgweb also allows for svg support in IE) – Hobnail

I may be misunderstanding, but I assume an embedded server in my app means my app is messing around with networking stuff, even if just on localhost. That means firewall issues, among other things. It's one of those things that in my mind fits in the category of "I don't own other peoples machines just because they run my program, so I have no right to dictate how it is configured etc". For the record, I have thrown out software precisely because, despite having no good reason to need network access, it required me to install a loopback device and change my firewall. – Weidar

Answer 5

Here is a good collection of Graph Libs with comparison and searching functionality:
http://gvsr.polytech.univ-nantes.fr/GVSR/task?action=browse#

Maybe you find a lib which fits for you.

Baroque

Unfortunately this link is now dead, and there doesn't appear to be a new location for it. – Cowpuncher