Draw a graph from a list of connected nodes

Question

In a system I Have a list of nodes which are connected like in a normal graph. We know the whole system and all of their connections and we also have a startpoint. All my edges has a direction.

Now I want to draw all of these nodes and edges automatically. The problem is not the actual drawing, but calculating the (x,y) coordinates. So basically I would like to draw this whole graph so it looks good.

My datastructure would be something like:

class node:
string text
List<edge> connections

There must be some well known algorithms for this problem? I haven't been able to find any, but I might be using the wrong keywords.

My thoughts:

One way would be to position our startnode at (0,0), and then have some constant which is "distance". Then for each neighbor, it would add distance to the y position, and for each node which is a neighbor, set x= distance*n.

But this will really give a lot of problems - so that's definetely not the way to go.

Answer 1

By far the most common approach for this is to use a force-directed layout instead of a deterministic one. The gist is that you have every node repel each other (anti-gravity) and have any connected pairs of nodes attract each other. After several iterations of a physics simulation you can get a reasonable layout.

There are many layout algorithms you can use, with vastly different results. The GraphViz fdp (Fruchterman & Reingold '91) and neato (Kamada & Kawai '89) algorithms work, but are rather old and there are much better alternatives. The Fruchterman & Reingold '91 algorithm is also available in Python in NetworkX.

Prefuse provides a ForceDirectedLayout Java class that is pretty fast and good. Hachul & Jünger '05 detail the FM^3 algorithm, which appears to do quite well in practice (Hachul & Jünger '06) and is available in C++ in Tulip.

There are tons of other open source tools to visualize graphs, like NodeXL (C#), a great introductory tool that integrates network analysis into Excel 2007/2010 (Disclaimer: I'm an advisor for it). Other awesome tools include Gephi (Java) and Cytoscape (Java), while Pajek, UCINet, yEd and Tom Sawyer are some proprietary alternatives.

Answer 2

In general this is a tricky problem, especially if you want to start dealing with edge routing and making things look pretty. You might look at http://www.graphviz.org/ and using either their command line tools, or using the graphviz library to do your layout and get your x,y coordinates within your application.