API reference¶

All public classes are importable directly from the top-level steinerpy package:

from steinerpy import SteinerProblem, PrizeCollectingProblem, ...

Core problems¶

class steinerpy.SteinerProblem(graph, terminal_groups, weight='weight', preprocess=True, **kwargs)[source]¶

Parameters:

graph (Graph)
terminal_groups (List[List])

__init__(graph, terminal_groups, weight='weight', preprocess=True, **kwargs)¶

Initialize the SteinerProblem (can be tree or forest).

Parameters:

graph (Graph) – networkx graph (Graph or DiGraph).
terminal_groups (List[List]) – nested list of terminals.
weight – edge attribute specified by this string as the edge weight.

get_solution(time_limit=300, log_file='', solver='highs', dual_ascent=None, exact=True, threads=None, decompose=None)¶

Get the solution of the Steiner Problem.

When budget was supplied at construction time the solver maximises the number of connected terminals subject to the budget constraint and returns a BudgetSolution. Otherwise the solver minimises the total edge cost and returns a plain Solution.

Optional modifiers set at construction time (max_degree, budget) are applied automatically regardless of which problem class is used.

Parameters:

time_limit (float) – time limit in seconds.
log_file (str) – path to the log file.
solver (str) – which MIP solver to use – "highs" (default) or "gurobi". When "gurobi" is chosen the cut-based formulation is solved with Gurobi lazy-cut callbacks, which requires gurobipy and a valid Gurobi license to be installed.
exact (bool) – when True (default) solve to optimality. When False run heuristic-only mode: return the dual-ascent primal with no ILP — much faster, and the returned Solution.gap is a valid optimality gap (0.0 ⇒ provably optimal). Supported for plain Steiner tree/forest and directed problems only; raises NotImplementedError for budget/degree-constrained variants.
dual_ascent (bool)
threads (int)
decompose (bool)

Returns:

Solution (or BudgetSolution when a budget is set).

Raises:

ValueError – if an unknown solver name is provided.
ImportError – if solver="gurobi" but gurobipy is not installed.

Return type:

Solution

class steinerpy.DirectedSteinerProblem(graph, root, terminals, weight='weight', **kwargs)[source]¶

Bases: BaseSteinerProblem

Directed Steiner Tree Problem (Steiner Arborescence Problem).

The graph is a directed graph (nx.DiGraph). A designated root node must have a directed path to every terminal node. Edges only allow flow in the direction they are defined; reverse arcs are not added.

Parameters:

graph (DiGraph)
terminals (List)
weight (str)

__init__(graph, root, terminals, weight='weight', **kwargs)[source]¶

Parameters:

graph (DiGraph) – networkx DiGraph.
root – root node — the source of the arborescence.
terminals (List) – list of terminal nodes that must be reachable from root.
weight (str) – edge attribute for edge weights.

Prize-collecting and node-weighted problems¶

class steinerpy.PrizeCollectingProblem(graph, terminal_groups, node_prizes, penalty_cost=1000, penalty_budget=None, **kwargs)[source]¶

Bases: SteinerProblem

__init__(graph, terminal_groups, node_prizes, penalty_cost=1000, penalty_budget=None, **kwargs)[source]¶

Prize Collecting Steiner Problem - extends regular Steiner problem.

Parameters:

node_prizes – dict mapping node -> prize value
penalty_cost – cost per unconnected terminal
penalty_budget – maximum total penalty allowed (optional)

get_solution(time_limit=300, log_file='', solver='highs', pc_transform=None, exact=True, threads=None)[source]¶

Solve the prize-collecting problem.

By default uses the penalty/Big-M flow ILP (HiGHS only). Two opt-in fast paths route through the classic PCSTP/MWCSP -> SAP transformation and the existing dual-ascent + directed-cut machinery:

exact=False — heuristic-only mode: return the dual-ascent SAP primal with no ILP; the Solution.gap is a valid optimality gap (0.0 certifies provable optimality).
pc_transform=True — exact solve via the SAP transformation with dual-ascent lower bound, reduced-cost fixing, cut-seeding, warm-start and proven-optimal early-exit.

Both require the instance to be a classic forgo-prize PCSTP (or an MWCSP); otherwise a clear NotImplementedError is raised. solver selects "highs" (default) or "gurobi" for the transform path’s ILP.

Parameters:

time_limit (float)
log_file (str)
solver (str)
pc_transform (bool)
exact (bool)
threads (int)

Return type:

PrizeCollectingSolution

class steinerpy.NodeWeightedSteinerProblem(graph, terminal_groups, node_weights, weight='weight', **kwargs)[source]¶

Node-Weighted Steiner Tree Problem (NWST).

Converts the node-weighted graph to an edge-weighted graph by splitting each node v into v_in and v_out connected by an edge of cost = node_weights[v]. Then solves the standard Steiner Tree problem on the transformed graph.

Terminal node costs are always incurred (they are part of every solution) and are added as a constant to the reported objective value.

Parameters:

graph (Graph)
terminal_groups (List[List])
node_weights (Dict)
weight (str)

__init__(graph, terminal_groups, node_weights, weight='weight', **kwargs)[source]¶

Parameters:

graph (Graph) – networkx undirected graph.
terminal_groups (List[List]) – nested list of terminals.
node_weights (Dict) – dict mapping node -> node cost.
weight (str) – edge attribute name for weights.

Note: graph preprocessing is not supported for node-weighted problems because the node-splitting transformation produces a directed graph internally.

get_solution(time_limit=300, log_file='', solver='highs', threads=None)[source]¶

Solve and map solution back to the original node-weighted graph.

Parameters:

time_limit (float)
log_file (str)
solver (str)
threads (int)

Return type:

NodeWeightedSolution

class steinerpy.MaxWeightConnectedSubgraph(graph, node_weights, root=None, weight='weight', **kwargs)[source]¶

Bases: PrizeCollectingProblem

Maximum-Weight Connected Subgraph (MWCS).

Finds a connected subgraph maximising the sum of node weights. Nodes with positive weights are modelled as optional terminals with prizes; nodes with negative weights are treated as Steiner points that are included only when they are necessary connectors. A user-supplied (or automatically chosen) root node anchors the solution.

Parameters:

graph (Graph)
node_weights (Dict)
weight (str)

__init__(graph, node_weights, root=None, weight='weight', **kwargs)[source]¶

Parameters:

graph (Graph) – networkx undirected graph.
node_weights (Dict) – dict mapping node -> weight (positive or negative).
root – optional root node; defaults to the highest-weight node.
weight (str) – edge attribute name for edge weights.

class steinerpy.BudgetedMaxWeightConnectedSubgraph(graph, node_weights, node_costs, node_budget, root=None, weight='weight', **kwargs)[source]¶

Bases: MaxWeightConnectedSubgraph

Maximum-Weight Connected Subgraph with a vertex-cost Budget (MWCSPB), thesis Ch. 5.6.

Like MaxWeightConnectedSubgraph, but every chosen vertex consumes a vertex cost and the total cost of the chosen connected subgraph may not exceed a node_budget. Maximises the total node weight subject to that budget.

Solved by a rooted directed model with optional per-vertex connectivity and a node-cost budget constraint (the existing budget= kwarg is an edge-cost budget that maximises connected terminals — a different problem). Supports both the "highs" and "gurobi" backends. This variant does not use the SAP-transform / dual-ascent accelerators (same opt-out convention as the budget/degree variants).

Parameters:

graph (Graph)
node_weights (Dict)
node_costs (Dict)
node_budget (float)
weight (str)

__init__(graph, node_weights, node_costs, node_budget, root=None, weight='weight', **kwargs)[source]¶

Parameters:

graph (Graph) – networkx undirected graph.
node_weights (Dict) – dict node -> weight (positive or negative).
node_costs (Dict) – dict node -> non-negative vertex cost.
node_budget (float) – maximum total vertex cost of the chosen subgraph.
root – optional root; defaults to the highest-weight node.
weight (str) – edge attribute name (edges are not part of the objective).

get_solution(time_limit=300, log_file='', solver='highs', threads=None)[source]¶

Solve the prize-collecting problem.

By default uses the penalty/Big-M flow ILP (HiGHS only). Two opt-in fast paths route through the classic PCSTP/MWCSP -> SAP transformation and the existing dual-ascent + directed-cut machinery:

exact=False — heuristic-only mode: return the dual-ascent SAP primal with no ILP; the Solution.gap is a valid optimality gap (0.0 certifies provable optimality).
pc_transform=True — exact solve via the SAP transformation with dual-ascent lower bound, reduced-cost fixing, cut-seeding, warm-start and proven-optimal early-exit.

Parameters:

time_limit (float)
log_file (str)
solver (str)
threads (int)

Return type:

PrizeCollectingSolution

Further variants¶

class steinerpy.PartialTerminalSteinerProblem(graph, terminal_groups, partial_terminals, weight='weight', **kwargs)[source]¶

Bases: SteinerProblem

Partial Terminal Steiner Tree Problem (PTSTP), thesis Ch. 5.1.

A Steiner tree problem with the extra requirement that a designated subset of the terminals — the partial terminals — must be leaves of the solution tree.

Solved by the transformation to a plain Steiner tree problem (thesis Sec. 5.1):

remove every edge whose both endpoints are partial terminals, and
add a large constant M (the sum of all edge weights) to every edge incident to a partial terminal, so no optimal Steiner tree routes through one.

Each partial terminal is then a leaf in an optimal solution, so exactly one +M edge is incident to it; the constant is subtracted back out of the reported objective. No partial-terminal Steiner tree need exist — an infeasible instance raises RuntimeError.

Follows the thesis assumption of at least three terminals; with one or two terminals the problem is trivial and the leaf requirement is vacuous.

Parameters:

graph (Graph)
terminal_groups (List[List])
weight (str)

__init__(graph, terminal_groups, partial_terminals, weight='weight', **kwargs)[source]¶

Initialize the SteinerProblem (can be tree or forest).

Parameters:

graph (Graph) – networkx graph (Graph or DiGraph).
terminal_groups (List[List]) – nested list of terminals.
weight (str) – edge attribute specified by this string as the edge weight.

get_solution(*args, **kwargs)[source]¶

Get the solution of the Steiner Problem.

Optional modifiers set at construction time (max_degree, budget) are applied automatically regardless of which problem class is used.

Parameters:

time_limit – time limit in seconds.
log_file – path to the log file.
solver – which MIP solver to use – "highs" (default) or "gurobi". When "gurobi" is chosen the cut-based formulation is solved with Gurobi lazy-cut callbacks, which requires gurobipy and a valid Gurobi license to be installed.
exact – when True (default) solve to optimality. When False run heuristic-only mode: return the dual-ascent primal with no ILP — much faster, and the returned Solution.gap is a valid optimality gap (0.0 ⇒ provably optimal). Supported for plain Steiner tree/forest and directed problems only; raises NotImplementedError for budget/degree-constrained variants.

Returns:

Solution (or BudgetSolution when a budget is set).

Raises:

ValueError – if an unknown solver name is provided.
ImportError – if solver="gurobi" but gurobipy is not installed.

Return type:

Solution

class steinerpy.FullTerminalSteinerProblem(graph, terminal_groups, weight='weight', **kwargs)[source]¶

Bases: PartialTerminalSteinerProblem

Full Terminal Steiner Tree Problem (FTSTP), thesis Ch. 5.1 — the special case of PartialTerminalSteinerProblem in which every terminal must be a leaf.

Parameters:

graph (Graph)
terminal_groups (List[List])
weight (str)

__init__(graph, terminal_groups, weight='weight', **kwargs)[source]¶

Initialize the SteinerProblem (can be tree or forest).

Parameters:

graph (Graph) – networkx graph (Graph or DiGraph).
terminal_groups (List[List]) – nested list of terminals.
weight (str) – edge attribute specified by this string as the edge weight.

class steinerpy.GroupSteinerProblem(graph, groups, weight='weight', **kwargs)[source]¶

Bases: SteinerProblem

Group Steiner Tree Problem (GSTP), thesis Ch. 5.7.

Given vertex groups, find a minimum-cost tree that contains at least one vertex from each group. Solved by the Voss (1999) transformation to a plain Steiner tree problem: add one artificial super-terminal per group, connected by zero-cost edges to every vertex of that group, then solve the Steiner tree problem whose terminals are the super-terminals. The zero-cost connector edges are stripped from the reported solution (they contribute nothing to the objective).

Parameters:

graph (Graph)
groups (List[List])
weight (str)

__init__(graph, groups, weight='weight', **kwargs)[source]¶

Initialize the SteinerProblem (can be tree or forest).

Parameters:

graph (Graph) – networkx graph (Graph or DiGraph).
terminal_groups – nested list of terminals.
weight (str) – edge attribute specified by this string as the edge weight.
groups (List[List])

get_solution(*args, **kwargs)[source]¶

Get the solution of the Steiner Problem.

Optional modifiers set at construction time (max_degree, budget) are applied automatically regardless of which problem class is used.

Parameters:

time_limit – time limit in seconds.
log_file – path to the log file.
solver – which MIP solver to use – "highs" (default) or "gurobi". When "gurobi" is chosen the cut-based formulation is solved with Gurobi lazy-cut callbacks, which requires gurobipy and a valid Gurobi license to be installed.
exact – when True (default) solve to optimality. When False run heuristic-only mode: return the dual-ascent primal with no ILP — much faster, and the returned Solution.gap is a valid optimality gap (0.0 ⇒ provably optimal). Supported for plain Steiner tree/forest and directed problems only; raises NotImplementedError for budget/degree-constrained variants.

Returns:

Solution (or BudgetSolution when a budget is set).

Raises:

ValueError – if an unknown solver name is provided.
ImportError – if solver="gurobi" but gurobipy is not installed.

Return type:

Solution

class steinerpy.HopConstrainedSteinerProblem(graph, root, terminals, hop_limit, weight='weight', **kwargs)[source]¶

Bases: DirectedSteinerProblem

Hop-Constrained Directed Steiner Tree Problem (HCDSTP), thesis Ch. 5.8.

A Steiner arborescence in which the number of arcs (hops) is bounded by hop_limit and no terminal (other than the root) has outgoing arcs.

Built on DirectedSteinerProblem: the outgoing arcs of every non-root terminal are removed from the graph, and the directed-cut model adds the hop constraint sum(y1) <= hop_limit (see steinerpy.mathematical_model.add_hop_constraint()). The dual-ascent accelerator is skipped automatically because hop_limit is set.

Parameters:

graph (DiGraph)
terminals (List)
hop_limit (int)
weight (str)

__init__(graph, root, terminals, hop_limit, weight='weight', **kwargs)[source]¶

Parameters:

graph (DiGraph) – networkx DiGraph.
root – root node of the arborescence.
terminals (List) – terminal nodes that must be reachable from root.
hop_limit (int) – maximum number of arcs allowed in the arborescence.
weight (str) – edge attribute for arc weights.

class steinerpy.RectilinearSteinerProblem(points, weight='weight', **kwargs)[source]¶

Bases: SteinerProblem

Rectilinear Steiner Minimum Tree (RSMT), thesis Ch. 5.4.

Given points in the plane, find a minimum-total-length tree that uses only horizontal and vertical segments (the L1 / Manhattan metric), allowing extra Steiner points. Reduced exactly to a Steiner tree problem on the Hanan grid (Hanan 1966); the reported objective is the total rectilinear length. Practical for modest point counts (the grid has up to k^2 nodes for k points).

Nodes of the underlying graph are (x, y) coordinate tuples.

Parameters:: weight (str)

__init__(points, weight='weight', **kwargs)[source]¶

Initialize the SteinerProblem (can be tree or forest).

Parameters:

graph – networkx graph (Graph or DiGraph).
terminal_groups – nested list of terminals.
weight (str) – edge attribute specified by this string as the edge weight.

get_solution(*args, **kwargs)[source]¶

Get the solution of the Steiner Problem.

Optional modifiers set at construction time (max_degree, budget) are applied automatically regardless of which problem class is used.

Parameters:

time_limit – time limit in seconds.
log_file – path to the log file.
solver – which MIP solver to use – "highs" (default) or "gurobi". When "gurobi" is chosen the cut-based formulation is solved with Gurobi lazy-cut callbacks, which requires gurobipy and a valid Gurobi license to be installed.
exact – when True (default) solve to optimality. When False run heuristic-only mode: return the dual-ascent primal with no ILP — much faster, and the returned Solution.gap is a valid optimality gap (0.0 ⇒ provably optimal). Supported for plain Steiner tree/forest and directed problems only; raises NotImplementedError for budget/degree-constrained variants.

Returns:

Solution (or BudgetSolution when a budget is set).

Raises:

ValueError – if an unknown solver name is provided.
ImportError – if solver="gurobi" but gurobipy is not installed.

Return type:

RectilinearSolution

Solutions¶

class steinerpy.Solution(gap, runtime, objective, selected_edges, original_selected_edges=None, was_preprocessed=False)[source]¶

Parameters:

gap (float)
runtime (float)
objective (float)
selected_edges (List[Tuple])
original_selected_edges (List[Tuple])
was_preprocessed (bool)

property edges¶: Return the edges in the original graph.

class steinerpy.PrizeCollectingSolution(selected_nodes=None, penalties=None, total_prize=0, edge_cost=0, **kwargs)[source]¶

Bases: Solution

Parameters:

selected_nodes (List[str])
penalties (Dict)
total_prize (float)
edge_cost (float)

property net_value¶: Total prize collected minus edge costs and penalties.

class steinerpy.NodeWeightedSolution(selected_nodes=None, **kwargs)[source]¶

Bases: Solution

Solution for the Node-Weighted Steiner Tree Problem.

Parameters:: selected_nodes (List | None)

class steinerpy.BudgetSolution(connected_terminals=0, total_terminals=0, penalties=None, **kwargs)[source]¶

Bases: Solution

Solution for the Budget-Constrained Steiner Tree Problem.

Parameters:

connected_terminals (int)
total_terminals (int)
penalties (Dict | None)

class steinerpy.RectilinearSolution(segments=None, steiner_points=None, **kwargs)[source]¶

Bases: Solution

Solution for the Rectilinear Steiner Minimum Tree problem.

Parameters:

segments (List | None)
steiner_points (List | None)

Deprecated¶

These classes remain for backward compatibility; pass max_degree= or budget= to the base problem class instead (see Problem variants).

class steinerpy.DegreeConstrainedSteinerProblem(graph, terminal_groups, max_degree, **kwargs)[source]¶

Bases: SteinerProblem

Degree-Constrained Steiner Tree Problem.

Deprecated since version 0.2.0: Pass max_degree directly to SteinerProblem (or any other problem class) instead::

SteinerProblem(graph, terminal_groups, max_degree=2)

This class is kept for backward compatibility and will be removed in a future version.

Parameters:

graph (Graph)
terminal_groups (List[List])
max_degree (int)

class steinerpy.BudgetConstrainedSteinerProblem(graph, terminal_groups, budget, **kwargs)[source]¶

Bases: SteinerProblem

Budget-Constrained Steiner Tree Problem.

Deprecated since version 0.2.0: Pass budget directly to SteinerProblem (or any other problem class) instead::

SteinerProblem(graph, terminal_groups, budget=10.0)

This class is kept for backward compatibility and will be removed in a future version.

Parameters:

graph (Graph)
terminal_groups (List[List])
budget (float)