stob: Obstacle-Avoiding Euclidian Steiner Trees in the Plane

This repository contains the code from M. Zachariasen and P. Winter's 1999 paper Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm¹, released with their permission and adapted for modern platforms.

The original, non-modernized code can be found in the repository's initial commit.

At the time of writing and to the best knowledge of the authors, this is the only publicly available implementation of an exact algorithm for the obstacle-avoiding Euclidian Steiner minimum tree (ESMTO).

The original framework involved a two-step process, with the generation of all Full Steiner Trees (FSTs) and then their concatenation into the minimum tree. The code for this second step is not available anymore. Instead, it is suggested to convert the FSTs into a graph and solve the corresponding Steiner tree problem in graphs using another code such as SCIP-Jack. For convenience, options have been added to output the graph in STP or GR format.

Compiling

The code relies on LEDA, in version 7.2 for the modernized code. A few patches are included to compile LEDA on the latest g++. LEDA requires yasm. On GNU/Linux, libX11 and libXft are required as well.

Compiling has been adapted for and tested on GNU/Linux and Microsoft Windows 10. For convenience, rudimentary Bourne Shell and PowerShell scripts are provided in make.sh and make.ps1 for downloading and compiling LEDA then stob.

Two executables are generated, stob.batch and stob. The former is fully automatic while the latter provides an interactive and graphical environment for defining the obstacles and terminals.

Build scripts for SCIP-Jack are provided as well.

Command-line options

Command	Description
-L path	Library file name, in stob format Use - to pass content through the standard input
-N integer	Number of terminals to be generated randomly in addition to the library input Default is 0
-S integer	Random number generator seed for the additional terminals If 0 or unset, a unique seed is used
-K integer	Maximum size of FSTs Not limited if 0 or unset
-V integer	Verbosity level From 0 to 5, default is 1
-C command	FSTs concatenation command Mostly kept for historical reference
-O path	Output file name Use - to pass content through the standard output
-F extension	Output file format One of fsts, stp or gr

Input file format

The ad-hoc stob file format contains terminal and polygonal obstacle data:

<Number of terminals>
For each terminal:
    <X-coord> <Y-coord>
<Number of obstacles>
For each obstacle:
    <Number of vertices>
    For each vertex:
        <X-coord> <Y-coord>

Obstacle vertices should be defined in counterclockwise order. The first polygon is expected to serve as the domain's outer boundary and as such to contain all terminals and other obstacles. If that is not the case, i.e. if terminals are outside all obstacles, the first polygon should be defined in clockwise order instead.

Output file formats

Extension	Description
fsts	GeoSteiner's FST data format (Appendix E, Version 2) Note that contrary to the standard format, the <<Number of duplicate terminal groups (ndg)>> is replaced with the number of pseudo-terminals and the For each duplicate terminal group: block is absent.
stp	SteinLib's STP data format
gr	PACE Challenge's simplification of the STP data format

Files

Path	Description
README.md	The present documentation file
LICENSE	CC-BY-NC-4.0 license text
make.sh	Bourne Shell script for downloading and compiling LEDA, then compiling stob
make.ps1	PowerShell script for downloading yasm, downloading and compiling LEDA, then compiling stob
make_scipjack.sh	Bourne Shell script for downloading and compiling SCIP-Jack
make_scipjack.ps1	PowerShell script for downloading and compiling SCIP-Jack
leda.patch	Patch to make LEDA 7.2 compile on latest g++ versions
params.set	Settings file to make SCIP-Jack output the minimal tree to a *.stplog file
src/stob.cpp	Main program
src/stob_fsts.*	FST generation
src/stob_general.*	General functions
src/stob_heuristics.*	Heuristics
src/stob_instances.*	Instance generation procedures
src/dyn_partition.*	Utility: special semi-dynamic union-find
data/*.stob	Example library input files
build/	Created upon compiling, output directory for the executables
.editorconfig	Standard setup for code formatting in editors
.gitignore	Files excluded from the git repository
data/*.(fsts|ps|eps)	(historical) Output corresponding to the example library files
src/generatesierpinski*	(not tested / historical) Programs generating stob code for Sierpinski triangle fractal
src/showvlsigridgraph.cpp	(not tested / historical) Program displaying VLSI grid graphs
run_*	(not tested / historical) tcsh script for running the example library files

License

Copyright (c) 1997-2025 by David M. Warme, Quentin Wenger, Pawel Winter and Martin Zachariasen. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. You should have received a copy of the license along with this work. If not, see https://creativecommons.org/licenses/by-nc/4.0/.

Reference

Footnotes

1. Zachariasen, M., Winter, P. (1999). Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm. In: Goodrich, M.T., McGeoch, C.C. (eds) Algorithm Engineering and Experimentation. ALENEX 1999. Lecture Notes in Computer Science, vol 1619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48518-X_17 ↩