Graph layout optimization in C#

Question

I've got a list of objects that I need to organize as an aesthetic graph. My current approach involves IronPython and a genetic algorithm, but this takes way too long.

I've been reading up on Graphviz, QuickGraph and Graph#, but I don't need the visualization part - I already have an app that will display the nodes given the x/y coordinates. I've been told that both the Sugiyama algorithm and the force-based family of algorithms tend to output pleasing graphs, but I can't seem to find a .NET library that will output the coordinates instead of the image without some pretty severe sourcecode hacking.

Can anyone recommend libraries, algorithms or the like?

Answer 1

There are a number of options, with various pros and cons - you may want to sift through this which is a list of software that does, more or less, what you're looking for.

It used to be the case that finding an open source solution was difficult, but the once commercially licensed MSAGL now seems to be open source.

The distinction between Graph# and QuickGraph is that the latter provides graph traversal and manipulation primitives but does not provide any layout algorithms. Graph# has all the source available, and from what I've (briefly) looked at, has a neat separation between layout engine and drawing implementation.

Graphviz is written in pure C/C++ and is fairly monolithic, taking as input a text file describing the graph and producing various types of output, both vector and raster based. It isn't a great fit as a plug-in layout engine, but could be used by shelling out and providing the requisite input file and parsing the output. Not a very clean solution though.

There's also something called OGDF. Although it's written entirely in C++, it has been designed to be used as a layout engine library and has a well-structured interface for this. It supports various layout algorithms including optimised Sugiyama if that's what you're interested in.

If you're interested in implementing an optimised variation on Sugiyama, you could always roll your own using a neat description of the algorithm :)

Ultimately though, you should probably decide what type of layout you're after before you make a decision on the library.

Answer 2

Microsoft Research has an automated graph layout engine that might assist you in this effort.

You may read more about it here:

http://research.microsoft.com/en-us/downloads/f1303e46-965f-401a-87c3-34e1331d32c5/

Answer 3

Just in case someone will face similar problem. There is a GraphX for .NET open-source project which incorporates many layout algorithms separated from the visualization engine. So you can just take the logic library, perform calculations and get the coordinates pack to be used in your own vis tool.

https://github.com/panthernet/GraphX