All-paths solvers#

Public entry points for budgeted all-paths maximization. These are the functions registered on AllPathsDiversity (algorithm="nsw_fpt_budget" and algorithm="esw_fpt"). Implementation details live in the submodules nsw_fpt_budget and esw_fpt; they are not duplicated here to keep a single documentation target per function.

Solver backends for all-paths diversity maximization.

phypanda.measure.all_paths_solvers.solve_esw_fpt(network: DirectedPhyNetwork, budget: int, costs: Mapping[str, int] | None = None, tree_extension: TreeExtension | None = None, **kwargs: Any) → tuple[float, Set[str]]#

Solve unit-cost MAPPD exactly using edge-scanwidth FPT dynamic programming.

Parameters:

  • network (DirectedPhyNetwork) – Input phylogenetic network.

  • budget (int) – Number of taxa to select (unit-cost mode).

  • costs (Mapping[str, int] | None, optional) – Taxon costs. Only unit costs are currently supported.

  • tree_extension (TreeExtension | None, default=None) – Optional precomputed tree extension. If None, a tree extension is computed via scanwidth.edge_scanwidth().

  • **kwargs (Any) – Additional keyword arguments passed to edge_scanwidth when tree_extension is None.

Returns:

Optimal all-paths objective value and selected taxa labels.

Return type:

tuple[float, Set[str]]

Raises:

  • PhyloZooValueError – If budget is out of bounds or the network has parallel edges.

  • PhyloZooNotImplementedError – If non-unit costs are requested.

  • PhyloZooRuntimeError – If tree-extension computation fails.

Examples

>>> import phypanda as pp
>>> # value, taxa = pp.all_paths.solve_maximization(
... #     network, budget=5, algorithm="esw_fpt"
... # )
phypanda.measure.all_paths_solvers.solve_nsw_fpt_budget(network: DirectedPhyNetwork, budget: int, costs: Mapping[str, int] | None = None, tree_extension: TreeExtension | None = None, *, numba: bool = True, **kwargs: Any) → tuple[float, Set[str]]#

Solve budgeted all-paths maximization using node-scanwidth DP.

Parameters:

  • network (DirectedPhyNetwork) – Input phylogenetic network.

  • budget (int) – Integer budget B.

  • costs (Mapping[str, int] | None, optional) – Integer costs per taxon. If None or missing for some taxa, unit costs are used for those taxa.

  • tree_extension (TreeExtension | None, optional) – Optional precomputed tree extension. If None, one is computed via scanwidth.node_scanwidth().

  • numba (bool, default=True) – Use Numba-accelerated child-table merges inside the DP. Set to False to force the pure Python merge (useful for debugging).

  • **kwargs (Any) – Keyword arguments forwarded to scanwidth.node_scanwidth when a tree extension is computed.

Returns:

Objective value and selected taxa.

Return type:

tuple[float, Set[str]]

Notes

This routine computes (or accepts) a node-scanwidth tree extension and then runs a bottom-up DP on that tree extension. The child-combination subproblem at each internal node is handled by phypanda.utils._ChildMergeDP.