[StructureGraphic] Drawing DAG's – Part 1

As I promised, it’s time to take StructureGraphic to the next level – drawing DAG’s. I have spent several hours today on formalizing what makes people think a graph layout is aesthetical, and how to make an algorithm that can draw a graph in such a way. You can see some quick sketches from the process below:

Quick: Just display connections, somehow
Better: Since it's a DAG, make all edges point down and try to
reduce the amount of edges that cross one another
Best: Align vertices to make it look better

Note: the rest of this post is going to get very technical in algorithms. Users that have no interest in algorithms should probably stop reading here…

The bad part, was that formalizing the problem directly gave me ridiculously high computational cost. Let a Graph be G=(V,E), then the naive algorithm I had ran in a time of O(|V|^3). To those of you who don’t speak math, this means that for a graph with 1000 vertices (the ultimate goal that I wish my library to survive) it would take about one billion computations(!) multiplied by some positive constant. This is not practical for any reasonable case.

The bottleneck was the fact that my “nice-looking” layout algorithm relies on finding the longest (i.e. in the amount of edges) path between two nodes in the graph (we know it’s has no circles – since we are still talking about DAG’s). The naive way to do that is:

• Give every edge a weight of –1
• Solve the All Pairs Shortest Paths using the Floyd–Warshall algorithm
• Find the shortest path out of all the paths (shortest for equal negative weights = longest in edge count)

Now, Floyd-Warshall does run in O(|V|^3), which makes it probably impractical for my case.

So, I kept on thinking since I thought to myself “Oh, we know it’s a DAG! That should somehow help us!”. At lunch I sat with 2 friends and discussed the problem (the student cafeteria we eat in is usually a great place to think – for some reason you simply “get” ideas while you sit there :D), and we devised a way to do this in O(|V|*|E|) using Dynamic Programming and Topological Sorting. Now this is an improvement, since DAGs are usually more sparse than general graphs, so |E| should be lower that |V|^2 (and even if that isn’t always true, in the cases it is, the algorithm will perform faster).

Now I said to myself, “I want it faster!”. While waiting for someone tonight, I had 10 minutes of thinking, and then I found it!(?) If I’m correct, and I hope I am, then I think I found a way to do this in O(|V|+|E|) using topological sorting!

Now, while writing this line, I decided to use the forbidden tool – Google. I generally tried to evade searching the web when working on StructureGraphic, since I want this project to be a chance for me to develop serious algorithms myself (developing your brain is good, and preparing yourself to the exam in algorithms next week while doing this is even better). So Google+Wikipedia confirmed my theory – it is possible to do this in O(|V|+|E|) using topological sorting! Note: I didn’t update the paragraph above this one, since I only googled it after I wrote it… I’ll complete my algorithm when I’m a bit more awake (it’s midnight here) and then I’ll compare it to the Wikipedia one.

I’ll introduce the “nice-layout” algorithm (how to take a graph and draw it so that it’s layout looks aesthetical) in my next post. Until then, good night and thanks for reading :)