All-paths PD (MAPPD)#

All-paths diversity measure implementation.

class phypanda.measure.all_paths.AllPathsDiversity#

Bases: object

All-paths diversity measure.

Examples

>>> import phypanda as pp
>>> # value = pp.compute_diversity(network, {"a", "b"}, measure=pp.all_paths)
compute_diversity(network: DirectedPhyNetwork, taxa: Set[str], **kwargs: Any) → float#

Compute all-paths diversity for a taxon set.

Parameters:

  • network (DirectedPhyNetwork) – Input phylogenetic network.

  • taxa (Set[str]) – Selected taxa.

  • **kwargs (Any) – Unused measure-specific options.

Returns:

All-paths diversity value.

Return type:

float

Examples

>>> import phypanda as pp
>>> # value = pp.compute_diversity(network, {"a", "b"}, measure=pp.all_paths)
solve_maximization(network: DirectedPhyNetwork, budget: int, costs: Mapping[str, int] | None = None, algorithm: str = 'nsw_fpt_budget', tree_extension: TreeExtension | None = None, **kwargs: Any) → tuple[float, Set[str]]#

Solve all-paths diversity maximization under budget constraints.

Parameters:

  • network (DirectedPhyNetwork) – Input network.

  • budget (int) – Integer budget.

  • costs (Mapping[str, int] | None, optional) – Taxon costs.

  • algorithm (str, optional) – Solver backend name. Default is "nsw_fpt_budget".

  • tree_extension (TreeExtension | None, optional) – Optional precomputed tree extension for compatible solvers. If None, the solver computes one using scanwidth defaults.

  • **kwargs (Any) – Solver-specific options forwarded to the selected backend (for example numba=False with algorithm="nsw_fpt_budget" to disable Numba in the child-merge DP).

Returns:

Objective value and selected taxa.

Return type:

tuple[float, Set[str]]

Examples

>>> import phypanda as pp
>>> # value, taxa = pp.solve_max_diversity(network, budget=5, measure=pp.all_paths)
>>> # value2, taxa2 = pp.solve_max_diversity(
... #     network, budget=5, algorithm="esw_fpt", tree_extension=None
... # )

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.solve_max_diversity(
... #     network, budget=5, measure=pp.all_paths, 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.