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?

Selfwill

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.

Oly

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/

Harri

I tried GLEE/MSAGL, but it only outputs images AFAIK - do you know if you can get the coordinates? – Selfwill

I was under the impression that the layout engine was independent of the rendering components, but I cannot state that with absolute certainty. This paper talks about the theory behind it, including the Sugiyama algorithm. ftp.research.microsoft.com/pub/tr/TR-2007-72.pdf – Harri

Yes, you can get only coordinates from MSAGL(formerly GLEE) and implement your own rendering - coding-time.blogspot.com/2009/03/… – Typebar

Its true that MSAGL is the further developed and paid version of GLEE, but its important to note that GLEE still exists and is free of use for non-commercial purposes. Download the free version of GLEE here: research.microsoft.com/en-us/downloads/… – Babettebabeuf

MSAGL is now available as opensource in GitHub: github.com/Microsoft/automatic-graph-layout – Unequal

MSAGL seems to be now under MIT license: github.com/Microsoft/automatic-graph-layout/blob/master/LICENSE, plus it is maintained, since I see they've pushed-in fixes for the Silverlight version recently – Unequal

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

Farant

Answer 4

yFiles has very sophisticated implementations of both force-directed (called "Organic") and Sugiyama based ("Called Hierarchic") layout algorithms. They offer viewer-less implementations for Java, .net, Silverlight, Flex, and Javascript. The API to retrieve the coordinates is available online here.

The algorithms and their quality can be tested in the free yEd Graph Editor application, the libraries are only commercially available, though.

Sibert

a bit expensive solution, but very nice architecture and documentation, plus libraries for several platforms (including some HTML5 now) – Unequal

Answer 5

there's a Sugiyama layout implementation in Java as part of the modsl system, Apache license. source is here.

i was able to convert it reasonably easily to a mixed Objective-C/Objective-C++ implementation based on digraph.

Grotesque

Answer 6

I had got the coordinates of nodes in this way

namespace GleeTest
{
    class GleeTest
    {

        static void Main() {
            Microsoft.Glee.GleeGraph oGleeGraph = new Microsoft.Glee.GleeGraph();

            Microsoft.Glee.Splines.ICurve oCurve =
               Microsoft.Glee.Splines.CurveFactory.CreateEllipse(
                   1, 1,
                   new Microsoft.Glee.Splines.Point(0, 0)
                   );
            Microsoft.Glee.Node strNode1 = new Microsoft.Glee.Node("Circle", oCurve);

            Microsoft.Glee.Node strNode3 = new Microsoft.Glee.Node("Diamond", oCurve);
            Microsoft.Glee.Node strNode4 = new Microsoft.Glee.Node("Standard", oCurve);
            Microsoft.Glee.Node strNode2 = new Microsoft.Glee.Node("Home", oCurve);

            oGleeGraph.AddNode(strNode1);
            oGleeGraph.AddNode(strNode2);
            oGleeGraph.AddNode(strNode3);
            oGleeGraph.AddNode(strNode4);

            Microsoft.Glee.Edge oGleeEdge1 =
               new Microsoft.Glee.Edge(strNode1, strNode2);
            Microsoft.Glee.Edge oGleeEdge2 =
            new Microsoft.Glee.Edge(strNode2, strNode1);
            Microsoft.Glee.Edge oGleeEdge3 =
            new Microsoft.Glee.Edge(strNode2, strNode2);
            Microsoft.Glee.Edge oGleeEdge4 =
            new Microsoft.Glee.Edge(strNode1, strNode3);
            Microsoft.Glee.Edge oGleeEdge5 =
            new Microsoft.Glee.Edge(strNode1, strNode4);
            Microsoft.Glee.Edge oGleeEdge6 =
          new Microsoft.Glee.Edge(strNode4, strNode1);


            oGleeGraph.AddEdge(oGleeEdge1);
            oGleeGraph.AddEdge(oGleeEdge2);
            oGleeGraph.AddEdge(oGleeEdge3);
            oGleeGraph.AddEdge(oGleeEdge4);
            oGleeGraph.AddEdge(oGleeEdge5);
            oGleeGraph.AddEdge(oGleeEdge6);

            oGleeGraph.CalculateLayout();


            System.Console.WriteLine("Circle position  " + oGleeGraph.FindNode("Circle").Center.X + "," + oGleeGraph.FindNode("Circle").Center.Y);
            System.Console.WriteLine("Home position = " + oGleeGraph.FindNode("Home").Center.X + "," + oGleeGraph.FindNode("Home").Center.Y);
            System.Console.WriteLine("Diamond position = " + oGleeGraph.FindNode("Diamond").Center.X + "," + oGleeGraph.FindNode("Diamond").Center.Y);
            System.Console.WriteLine("Standard position = " + oGleeGraph.FindNode("Standard").Center.X + "," + oGleeGraph.FindNode("Standard").Center.Y);




        }

    }
}

Tremann