Graph algorithms are fun

I have recently rediscovered (yet again) the joys of coding graph algorithms.

It's been a few years since the last time I worked on some of them: for example, I "reinvented" DFS (depth-first-search - I didn't really know about this concept at the time) as part of an implementation of a graph representing a set of possible chord progressions with weights/probabilities that a node should be randomly visited, to be used in a automated music generator.

Consider the nodes
Walk along spanning arcs
Lost in traversal

Maybe one day, I'll release that library of them that I've been building up. Then again, it means someone else might not have this fun themselves.

And day by day the monster grew,
byte by bite,
y wiser too.

IMO, graphs are one of the most versatile (and useful) data structures out there. Since practically every other interesting data structure is practically a sub-case of graphs, they're my favourite data structure.




Furthermore, in many ways, Blender can also act as a nice graphical testbed for graphs. See http://blenderartists.org/forum/showthread.php?p=1684709 for an example of someone trying to use Blender for related applications. But for that to be really useful though, it might be useful to consider some graph layout algorithms for automatically laying out a set of vertices, which could potentially have some other unexpected artistic consequences.

Certainly from my limited experience playing with these things (see dbcskit, a set of utilities primarily aimed at trying to get ER-Schema Diagrams automatically laid out using GraphViz as the underlying engine), we still have a long way to go with our algorithms for dealing with this problem. (As a side note, through my experiments using this on an evolving schema, it appeared that being able to lay out the graph without having overlapping lines was a promising metric for the "goodness" of the schema, though I'd really need to do this analysis on a large number of such "good" schemas before being able to say conclusively whether this is the case).

In the situations I had, the existing algorithms were ok when it came to really simple cases. But as soon as you chuck a slightly more 'involved' diagram at them, they start overlapping all critical elements senselessly, as if there wasn't any collision detection at all. After trialling various settings, the current iteration uses a set of settings which causes the nodes to be spread out quite far apart (like fireworks) so that no elements overlap. However, this comes at the cost of a lot of wasted 'page space' and a not-very optimal layout, though at least everything is laid out ok, so at the time I considered it the best I could get out of it.

AFAIK, GraphViz is already one of the bigger and more established set of algorithms for dealing with this problem in general, but I'm also aware of at least a few other promising approaches too (though I haven't tried them out for size yet). Anyways, it's an interesting area of research to say the least...