This app illustrates the Borah-Owens-Irwin algorithm for constructing a Steiner Tree. The algorithm starts with a Rectilinear Minimum Spanning Tree (RSMT) and searches for node/edge pairs such that connecting the node to the edge creates a new Steiner Point and creates a cycle in the tree. The longest edge in the cycle is then deleted, creating a new tree that improves the overall cost of the tree. Node/edge pairs are examined and ranked by potential gain and applied in that order.
To Use the App
This app creates a small number of terminals at random locations. Use the “VCR” controls to start, pause, single-step, or stop the animation.
A gain table is placed in the right area of the window to display the gain of node-edge pairs.
The Hanan Grid can also be displayed at the back of the window.
If you’re interested, here is the source code
References
M. Borah, R. Owens, and M. J. Irwin, “An Edge-Based Heuristic for Steiner Routing”, IEEE Trans. CAD, Vol 13, No. 12, pp 1563-1568. December, 1994.
J. Ganley, P. Madden, G. Robins, and I. Mandoiu, “GSRC Bookshelf Rectilinear Steiner Minimum Tree Slot”, February 2003. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/.
M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design, McGraw-Hill, 1996.
Acknowledgment
This RMST code in this app is derived from Patrick Madden’s Steiner Tree code which can be found at the href=”http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/” target=”_new”>http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/.