SteinerPy solves Steiner tree and Steiner forest problems — and many advanced variants — to proven optimality, directly on NetworkX graphs. It uses the open-source HiGHS solver by default, with Gurobi supported as an optional backend.
- One API, many variants — Steiner tree/forest, prize-collecting, node-weighted, maximum-weight connected subgraph, directed (arborescence), hop-constrained, group, rectilinear, terminal-leaf, and budgeted variants.
- Exact, with a certificate — every solve reports a proven optimality gap;
gap == 0.0means provably optimal. - Fast by default — provably optimum-preserving graph reductions from the Steiner-tree literature run automatically, plus an opt-in dual-ascent accelerator and a heuristic-only mode that stays in NetworkX's speed class while still certifying its gap.
📖 Documentation: steinerpy.readthedocs.io
pip install steinerpyRequires Python 3.8+. The HiGHS backend is installed automatically; to use Gurobi instead, install gurobipy and provide a valid license.
import networkx as nx
from steinerpy import SteinerProblem
G = nx.Graph()
G.add_edge("A", "B", weight=1)
G.add_edge("B", "C", weight=2)
G.add_edge("C", "D", weight=1)
# One terminal group = Steiner tree; multiple groups = Steiner forest
# Edge/arc costs must be non-negative.
solution = SteinerProblem(G, [["A", "D"]]).get_solution()
print(f"Optimal cost: {solution.objective}")
print(f"Selected edges: {solution.selected_edges}")
print(f"Proven optimality gap: {solution.gap}") # 0.0 == provably optimalSee the documentation for the full catalogue of problem variants, solver selection, performance features (dual ascent, graph reductions, heuristic-only mode), benchmarks against NetworkX and pcst_fast, and the API reference. The example notebook walks through the main features.
If you use SteinerPy in your research, please cite:
@article{markhorst2025future,
title={Future-proof ship pipe routing: Navigating the energy transition},
author={Markhorst, Berend and Berkhout, Joost and Zocca, Alessandro and Pruyn, Jeroen and van der Mei, Rob},
journal={Ocean Engineering},
volume={319},
pages={120113},
year={2025},
publisher={Elsevier}
}Contributions are very welcome! Please read the contributing guidelines and open an issue to discuss your idea before starting on a pull request.
SteinerPy is available under the MIT license.