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.0 means 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

Describe connectivity and costs with one class:

from steinerpy import Problem

problem = Problem(graph, terminals=["A", "D"])
solution = problem.get_solution(solver="highs", time_limit=60)

problem = Problem(graph, terminals=[["A", "B"], ["C", "D"]])  # Forest
problem = Problem(digraph, root="A", terminals=["D"])
problem = Problem(graph, groups=[["A", "B"], ["C", "D"]], node_costs={"B": 2})

Flat terminals must all connect; nested lists must each connect internally, with sharing allowed. groups chooses at least one member per group in one connected tree. Group-plus-node-cost problems minimize edge costs plus selected node costs; this combination requires non-negative costs and exact solving. With preprocess=True, only reductions compatible with the requested features are applied.

See the variant guide for supported combinations. Explicit variant= calls, terminal_groups=, and existing classes remain supported.

pip install steinerpy

Supports standard CPython 3.8–3.15, with Python 3.8 retained as the minimum. The HiGHS backend is installed automatically. Python 3.15 currently requires building highspy from source with a C++ toolchain; see the installation requirements. To use Gurobi, install gurobipy and provide a valid license; its Python compatibility is separate from HiGHS support.

import networkx as nx
from steinerpy import Problem

G = nx.Graph()
G.add_edge("A", "B", weight=1)
G.add_edge("B", "C", weight=2)
G.add_edge("C", "D", weight=1)

# Flat terminals = Steiner tree; nested lists = Steiner forest
# Edge/arc costs must be non-negative.
solution = Problem(G, terminals=["A", "D"]).get_solution()

print(f"Optimal cost: {solution.objective}")
print(f"Selected edges: {solution.edges}")
print(f"Proven optimality gap: {solution.gap}")  # 0.0 == provably optimal

See 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.

Existing problem classes remain supported. See the migration and compatibility guide for equivalent Problem(...) calls and the existing degree/budget wrapper deprecations.

For measurements on the three PACE 2018 tracks and historical participant results, see the PACE benchmark report.

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.