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

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.

Answer 4

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

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.

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);




        }

    }
}