Skip to main content

SteinerPy

PyPI version PyPI - Downloads Python 3.8+ License: MIT CI/CD codecov Documentation

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

Unified problem interface

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.

Installation

pip install steinerpy

Requires Python 3.8+. The HiGHS backend is installed automatically; to use Gurobi instead, install gurobipy and provide a valid license.

Quick start

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.

Citing

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}
}

Contributing

Contributions are very welcome! Please read the contributing guidelines and open an issue to discuss your idea before starting on a pull request.

License

SteinerPy is available under the MIT license.

Star History

Star History Chart

Metadata

Release files for steinerpy 1.1.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for steinerpy 1.1.0
File Size Uploaded Provenance Actions
steinerpy-1.1.0.tar.gz 175.2 kB Without provenance Details for steinerpy-1.1.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for steinerpy 1.1.0
File Interpreter ABI Platform Actions
steinerpy-1.1.0-py3-none-any.whl Python 3 none any Details for steinerpy-1.1.0-py3-none-any.whl

Total release size: 333.0 kB

Release files / steinerpy-1.1.0.tar.gz

Download URL steinerpy-1.1.0.tar.gz
Size 175.2 kB
Tags Source
SHA-256 checksum
How to use checksums
893acdc11f32f4fdb8f2a5c73b6e2fc160d5c32c73ba5ce63387fa69cd456cba
BLAKE2b-256 checksum
How to use checksums
3b9d8409b9637f74a2b9dfa29f88da4f59919a8b6efe238bf2ac0635aa95eefd
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via uv/0.13.6 {"installer":{"name":"uv","version":"0.13.6","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / steinerpy-1.1.0-py3-none-any.whl

Download URL steinerpy-1.1.0-py3-none-any.whl
Size 157.8 kB
Tags Python 3
SHA-256 checksum
How to use checksums
58ae071f906c15f804e2d495df398e9e04e7242681b77b0e9477db172984b7f3
BLAKE2b-256 checksum
How to use checksums
d74c86e7acda9d01b51407c5313d35cf876580db300a9d113e8efce241686734
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via uv/0.13.6 {"installer":{"name":"uv","version":"0.13.6","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Security for steinerpy 1.1.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page