The topological autorouter began as a project funded by Google and mentored by DJ Delorie in 2008. The goal was to create a topological autorouter for the gEDA suite of open source hardware development tools, mostly implementing the algorithms described in Tal Dayans PhD thesis, "Rubberband based topological router".
Although the resulting code demonstrated the capability of the algorithms by solving some simple and contrived problems that geometric routers could not, I became aware of issues when applied to real world PCB problems.
Since the initial project, a new topological autorouter has been started, in an effort to address some of the shortcomings of the first implementation. The layout program in gEDA already has a highly optimized an efficient autorouter developed by Harry Eaton and C. Scott Ananian, however in various cases a topological and curvilinear autorouter can provide better results.
The following sections demonstrate some results obtained with the new code (available in the git repository). Please keep the following in mind when comparing the results:
This simple contrived layout demonstrates the power of topological autorouters over geometric autorouters. Geometric autorouters trying to route the nets with a shortest path will obstruct at least one of the nets, resulting in failure. The runtime of each router was << one second. The toporouter runtime was 0.08 second.
This board was designed by DJ Delorie (its purpose is unknown). The board contains 69 nets to route. The autorouter runtime was approx. one second, and failed eights nets. The toporouter runtime was 4.19 seconds, and failed four nets.
This board was designed by DJ Delorie to add digital temperature control to an otherwise fixed-temperature laminator (or other heating device). The board contains of 111 nets to route. The autorouter runtime was approx. two to three seconds, and failed seven nets. The toporouter runtime was 10.248 seconds, and failed two nets.
This board is a temperature controller for beer brewing designed by Sam Bartels. It is constrained to one layer and contains 72 nets to route. The autorouter took approx. one second and failed eight nets. The toporoute routed all nets successfully with a runtime of 0.853 second.
The Flare Genesis board by Harry Eaton is contained in the PCB source code as the standard example board. The board contains 123 nets to route. The autorouter takes less than one second and routes all nets. The toporouter runtime was 2.318 seconds and routed all nets.
This board was submitted by Dima Kogan to the bug tracker in 2008 to illustrate a problem with the autorouter which has since been fixed. The board contains 63 nets to route. The autorouter runtime was approx. one second and six nets failed routing. The toporouter runtime was 1.944 seconds and all nets were routed.
2009-06-27 - One pass curvilinear wiring.
2009-06-27 - Multiple traces on constraint edges.
2009-07-02 - Greedy ROAR routing and optimization.
2009-07-02 - Replaced last years outdated webpage.
Eric Brombaugh - Web page style.
Peter Clifton - PCB colour scheme.