Drawing Circuit Diagrams

If you've been browsing some of my previous posts, you'll know that I'm interested in writing an open source tool to generate schematics from some Verilog RTL. And you'll also probably remember that I was trying to come up with the layout & routing algorithms for the schematics myself.
I'm also failing miserably, you may remember. This is as far as I got with the genetic algorithm layout before I decided to abandon it on speed and reproducability grounds:


So, I've honoured the pragmatic promise I made to myself, and I've turned to the interwebs for help.

Vocabulary

Drawing automated pictures of relationships in Computer Science goes by the name of Graph Drawing, a branch of Graph Theory. According to this stuff, I'm looking to draw Layered Orthogonal Directed Graphs:

• 'Layered' from the fact that I can arrange the instances into columns. Sugiyama seems to be the main man when it comes to algorithms for this sort of graph.
  
• 'Orthogonal' because I want the nets to go in right-angles.
• 'Directed' because there's a flow in the drawing. For us EEs, this flow is left to right, but in graph theory it's usually top to bottom. So my problem would've been with the x-placement.

In graph theory, my RTL module instantiations are nodes and nets are edges.

Existing Code

The first thing I did with my new-found pragmatism was to look for open-sourced code I could rob use. Preferably this code would be a C/C++ library (for speed) with Python bindings (for handiness), but I'd settle for pure Python. I didn't find exactly what I was looking for; either there was a lack of examples and screenshots, no python bindings, or the library was closed source. That said, if I'm willing to learn SWIG to create python bindings, or I'm willing to create my own examples, there are a few libraries to investigate further:

• OGDF: C++
• networkx: Python
• igraph: Python binding of C library.

Some of the proprietary stuff could've been exactly what I need: tomsayer.com (sorry, this tries to resize your browser window) had a teaser of a circuit diagram, and yFiles had intrigingly-named ChannelEdgeRouter class.

Even if none of the above open source libraries end up suiting my project, at least I have the freedom to look at the code and study the algorithms they use when cooking my own.

Literature Search

Then I stuck a whole pile of terms into the search engine to see what turned up. I tried various combinations of terms including 'graph', 'drawing', 'routing', 'layout', 'channel', 'layered', '2d' etc. and added more as they turned up. Although I got some useful introductory slide decks from university courses, I did bang my head up against sites such as ieeexplore and springerlinks which expected me to pay for stuff.

The searching did throw up a pair of papers by Eschbach, Günther & Becker which seem promising. One of which, Orthogonal Circuit Visualization Improved by Merging the Placement and Routing Phases, especially so.

Homework

I think the next stage of my endeavour is to read the papers by EGB (hehe, Eternal Golden Braid) I mentioned above, and have a look into those graph drawing libraries, maybe igraph seems the most appealing at a first cut.