PhyNetPy Documentation

Library for the Development and Use of Phylogenetic Network Methods

GraphUtils Module v1.0.0

Network decomposition, distances, and structural edits: blobs, tree-of-blobs, displayed trees, cluster/mu/tripartition distances, hybrid-ancestry error, reticulation-aware comparison, and ASCII rendering.

Author:
Mark Kessler
Last Edit:
5/12/26
Source:
GraphUtils.py

Contents

Module Functions

get_all_clusters(net: Network, include_trivial: bool = False) -> set[frozenset[Node]]

Compile the set of clusters that make up this network. Ie: for a graph ((A, B)C, D); , set of all clusters is {(A,B), (A,B,C)}. A cluster is the set of leaves below some non-root node. Clusters of size 1 can optionally be included. Note that clusters are sets of :class:`~phynetpy.Network.Node` objects belonging to *this* network, so they cannot be compared across networks; use :func:`network_clusters` for that.

Parameter Type Description
net Network the network to operate on
include_trivial bool If set to True, includes clusters of size 1. Defaults to False.
Returns: set: A set of all clusters in this graph, each a frozenset of Nodes.
subnet_given_leaves(net: Network, leaf_set: list[Node]) -> Network

Compute the minimally sized subnetwork of a network such that the leaf set of the subnetwork is a subset of the original network's leaf set.

Parameter Type Description
net Network A network
leaf_set list[Node] A set of leaf nodes of the given network
Returns: Network: A new Network object with node and edge copies of the original.
get_displayed_trees(net: Network, unique: bool = True) -> list[Network]

Enumerate the trees displayed by a phylogenetic network. A tree is displayed by a network when it can be obtained by keeping exactly one in-edge at every reticulation, deleting the rest, and then reducing what is left to a tree over the network's full leaf set: * nodes left without children are suppressed, repeatedly, since suppressing one can leave its parent childless; * chains of degree-2 nodes are contracted into single branches; * the reticulation flag is cleared, so :func:`is_tree` holds of every result. Every displayed tree has exactly the leaf set of 'net'. Removing in-edges of reticulations never disconnects a leaf, because each reticulation keeps one parent and no other node loses its only one. A network with k reticulations admits at most 2^k displayed trees, but often fewer distinct ones: when the choices at two reticulations discard each other's subtrees, different choices display the same tree. In ``(t2,((t4,t6),(((t3)#H1,(t1)#H2),((t5,#H1),#H2))));`` two of the four choices display ``(t2,((t4,t6),(t1,(t5,t3))));``, so the network displays three trees, not four.

Parameter Type Description
net Network A phylogenetic network.
unique bool If True (the default), return one Network per distinct topology. If False, return one per hybrid-edge choice, so that the length of the result is the product of the reticulations' in-degrees.
Returns: list[Network]: The displayed trees, as new Network objects. Order is deterministic: reticulations and their in-edges are enumerated by label, and duplicates are dropped in favour of the first occurrence.
get_all_subtrees(net: Network) -> list[Network]

Generate one tree per choice of hybrid edges to keep at the reticulations. Prefer :func:`get_displayed_trees`, which returns the *distinct* displayed trees. This function returns one tree per element of the product of the reticulations' in-edge sets, so the same topology can appear twice; see :func:`get_displayed_trees` for when that happens.

Parameter Type Description
net Network A network object
Returns: list[Network]: A list of network objects, each representing a tree that is derived from the original network.
dominant_tree(net: Network) -> Network

Generate the dominant tree from a given network by retaining only the reticulation edges with the highest inheritance probability and removing all other reticulation edges.

Parameter Type Description
net Network A network object
Returns: Network: A new network object representing the dominant tree derived from the original network.
reticulation_cycle_size(net: Network, retic: Node) -> int

Number of nodes on a reticulation's cycle, in the undirected graph. The cycle is ``retic`` plus the two ancestral paths from its parents up to their lowest common ancestor. A cycle of 3 means the two parents are parent and grandparent of each other, which no rooted triple can distinguish from a tree; such a reticulation is invisible to triplet pseudo-likelihood. ``2`` means parallel edges (both parents identical) and ``0`` means the node is not a proper two-parent reticulation.

Parameter Type Description
net Network Network containing ``retic``.
retic Node The reticulation node.
Returns: int: Cycle size, or 0 when ``retic`` has fewer than two parents or its parents share no ancestor.
count_reticulations(net: Network, min_cycle_size: Optional[int] = None) -> int

Count the number of reticulation nodes in a network.

Parameter Type Description
net Network A network object.
min_cycle_size int | None When given, count only reticulations whose cycle (see :func:`reticulation_cycle_size`) has at least this many nodes. ``4`` counts the reticulations a rooted-triple criterion can detect; a cycle of 3 or less is invisible to it.
Returns: int: Number of nodes flagged as reticulations, filtered by cycle size when ``min_cycle_size`` is given.
add_hybrid(net: Network, source: Edge, destination: Edge, t_src: float = None, t_dest: float = None) -> None

Add a hybrid (reticulation) edge between two existing edges, raising the network level by one. This is a structural edit, not a Metropolis-Hastings proposal: it mutates ``net`` in place and reports no Hastings ratio. Samplers should use the :class:`~.ModelMove.AddReticulation` move instead, which carries the reversible-jump proposal math. How it works (normal case, ``source != destination``):: BEFORE AFTER a x a x | | | | | | n1 -------> n2 (new hybrid edge) | | | | b y b y Two fresh internal nodes (n1, n2) are inserted by splitting the ``source`` and ``destination`` edges respectively. n2 is flagged as a reticulation node, and a directed edge n1 -> n2 is added. When ``source`` and ``destination`` are the *same* edge, two parallel edges with equal inheritance probabilities (gamma = 0.5) are created between two new internal nodes, modeling a whole-genome duplication ("bubble") event.

Parameter Type Description
net Network The network to modify in place.
source Edge The edge that will donate the new outgoing lineage.
destination Edge The edge that will receive the incoming hybrid lineage.
t_src float, optional Divergence time for the new source-side node. Defaults to None.
t_dest float, optional Divergence time for the new reticulation node. Defaults to None.
pairwise_leaf_distance(net: Network, use_branch_lengths: bool = True) -> dict[tuple[str, str], float]

Compute pairwise distances between leaves on the underlying undirected graph. If use_branch_lengths is True, sum edge lengths; otherwise, use unit weights.

Parameter Type Description
net Network A network object.
use_branch_lengths bool Whether to sum edge lengths.
Returns: dict[tuple[str, str], float]: Map from sorted (leaf_i, leaf_j) to distance.
bridges_and_articulations(net: Network) -> tuple[list[tuple[str, str]], list[str]]

Compute bridges and articulation points on the underlying undirected graph using Tarjan's algorithm.

Parameter Type Description
net Network A network object.
Returns: tuple[list[tuple[str, str]], list[str]]: A pair (bridges, articulations) where bridges are (u, v) tuples with u < v by node label, and articulations are node labels.
blobs(net: Network) -> list[set[Node]]

Return the biconnected components ("blobs") of the underlying undirected graph.

Parameter Type Description
net Network A network object.
Returns: list[set[Node]]: A list where each element is the node set of one biconnected component in the undirected view of the network.
tree_of_blobs(net: Network) -> list[Network]

Decompose a phylogenetic network into its biconnected components (blobs). Each blob is a maximal biconnected subgraph of the underlying undirected graph. Returns a list of Network objects, one per biconnected component, containing copies of the original nodes and directed edges. Node names are preserved but all objects are distinct from the original network.

Parameter Type Description
net Network A phylogenetic network.
Returns: list[Network]: One Network per biconnected component (blob).
level(net: Network) -> int

Compute the level of a phylogenetic network. The level is the maximum number of reticulation nodes contained in any biconnected component ("blob") of the underlying undirected graph. Returns 0 for trees.

Parameter Type Description
net Network Input network.
Returns: int: The network level.
count_displayed_trees(net: Network, exact: bool = False) -> int

Count the trees displayed by a network. By default this is the product, over reticulation nodes, of their inbound edge counts (typically 2), which counts hybrid-edge *choices* rather than trees. It is an upper bound: two choices display the same tree whenever each discards the other's subtree, so the number of distinct displayed trees can be strictly smaller. Pass ``exact=True`` to enumerate the displayed trees with :func:`get_displayed_trees` and count the distinct ones instead. That is exponentially more expensive, since it builds every tree.

Parameter Type Description
net Network A network object.
exact bool Count distinct displayed trees rather than hybrid-edge choices. Defaults to False.
Returns: int: The number of displayed trees, or of hybrid-edge choices.
is_tree(net: Network) -> bool

Check whether a network is a tree (i.e., has no reticulation nodes).

Parameter Type Description
net Network A network object.
Returns: bool: True if there are no reticulation nodes, False otherwise.
induced_subnetwork_by_taxa(net: Network, taxa: list[str]) -> Network

Construct the subnetwork induced by a set of leaf labels. The induced subnetwork is formed by taking the MRCA of the target leaves and retaining only those descendant branches that lead to at least one target leaf. Node/edge attributes (gamma, length) are copied where applicable.

Parameter Type Description
net Network A network object.
taxa list[str] List of leaf labels to induce on.
Returns: Network: The induced subnetwork as a new Network object.
Raises: NetworkError: If any leaf name is not found in the network.
is_isomorphic(net1: Network, net2: Network) -> bool

Returns True, if net1 and net2 are topologically identical networks. Even if branch lengths are different, or node labels are different, networks can be isomorphic. ie-- all trees with 3 taxa are isomorphic. quartet trees have only a few different variations. Networks of any size, have infinitely many possible topologies. (A,B)C; is isomorphic with (D,E)F; (A,B),(C,D); is not isomorphic with ((A,B)C, D);

Parameter Type Description
net1 Network A Network object
net2 Network Another Network object
Returns: bool: True if the networks are topologically isomorphic, False otherwise
network_clusters(net: Network) -> set[frozenset[str]]

The set of non-trivial leaf-label clusters induced by a network's nodes. Label-based rather than node-based, so clusters are comparable *across* networks -- which :func:`get_all_clusters` is not, since it returns sets of :class:`~phynetpy.Network.Node` objects belonging to one graph.

Parameter Type Description
net Network The network to summarise.
Returns: set[frozenset[str]]: One frozenset of leaf labels per non-trivial cluster: size 2 or more, excluding the full leaf set.
hardwired_cluster_distance(net1: Network, net2: Network, normalize: bool = False) -> Union[int, float]

Hardwired cluster distance between two phylogenetic networks. The hardwired cluster of a node v is the set of all leaf labels reachable from v by following every directed edge. The distance is the cardinality of the symmetric difference of the two hardwired cluster sets: d_HC(N1, N2) = |HC(N1) triangle HC(N2)| When *normalize* is True the result is divided by |HC(N1) | HC(N2)|, yielding a value in [0, 1]. Reference --------- Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.

Parameter Type Description
net1 First network.
net2 Second network.
normalize Return a value in [0, 1] instead of a raw count.
Returns: The hardwired cluster distance (int, or float when normalized).
softwired_cluster_distance(net1: Network, net2: Network, normalize: bool = False) -> Union[int, float]

Softwired cluster distance between two phylogenetic networks. The softwired cluster set of a network is the union of cluster sets across all of its displayed trees. The distance is the cardinality of the symmetric difference: d_SC(N1, N2) = |SC(N1) triangle SC(N2)| .. note:: This enumerates all 2^k displayed trees where k is the number of reticulations. For networks with many reticulations the cost is exponential. When *normalize* is True the result is divided by |SC(N1) | SC(N2)|, yielding a value in [0, 1]. Reference --------- Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.

Parameter Type Description
net1 First network.
net2 Second network.
normalize Return a value in [0, 1] instead of a raw count.
Returns: The softwired cluster distance (int, or float when normalized).
mu_distance(net1: Network, net2: Network) -> int

Mu-representation distance between two phylogenetic networks. For every node v in a network with leaf set X = {l_1, ..., l_n} the *mu-vector* is mu(v) = (m(v, l_1), ..., m(v, l_n)) where m(v, l_i) is the number of directed paths from v to leaf l_i. The *mu-representation* of a network is the multiset of mu-vectors over all nodes. The distance is the size of the multiset symmetric difference of the two mu-representations. This is a metric on the space of *reduced* phylogenetic networks (networks with no degree-2 tree nodes and no parallel edges). It is also referred to as the *topological distance for reduced networks*. For trees it reduces to the Robinson--Foulds distance. Both networks must share the same leaf label set. Reference --------- Cardona, Llabres, Rossello & Valiente. *Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric*. IEEE/ACM Trans. Comput. Biol. Bioinformatics **6** (2009), 46--61.

Parameter Type Description
net1 First network.
net2 Second network.
Returns: The mu-distance (non-negative integer).
Raises: NetworkError: If the two networks have different leaf label sets.
hybrid_ancestry(net: Network) -> frozenset[str]

The leaf labels that descend from at least one reticulation node. A taxon is of *hybrid ancestry* if some reticulation lies on a directed path from the root to it, i.e. it belongs to the hardwired cluster of some reticulation node. Since every leaf below a reticulation is reached along every edge, the set is independent of inheritance probabilities and of the root placement.

Parameter Type Description
net Network A phylogenetic network.
Returns: frozenset[str]: Labels of the leaves below any reticulation; empty for a tree.
hybrid_ancestry_error(estimated: Network, true_net: Network) -> float

Hybrid-ancestry balanced error (HAE) of an estimated network against the true network. Let B be the hybrid-ancestry set (see :func:`hybrid_ancestry`) of the estimate and A that of the truth. The false-positive rate is |B - A| / |B| and the false-negative rate |A - B| / |A|; HAE is their mean, in [0, 1]. Each rate is defined as 0 when its denominator is empty, so a tree estimated for a reticulate truth scores 0.5 and a tree estimated for a tree scores 0. Unlike :func:`mu_distance`, this measure is *asymmetric*: the argument order matters. The convention follows the HAE column of the NetCSEval evaluation scripts (``hae_datafinal.jl``), so values are comparable to that work.

Parameter Type Description
estimated Network The inferred network.
true_net Network The reference (true) network.
Returns: float: Balanced hybrid-ancestry error in [0, 1].
Raises: NetworkError: If the two networks have different leaf label sets.
tripartition_distance(net1: Network, net2: Network, normalize: bool = False) -> Union[int, float]

Tripartition-based distance between two phylogenetic networks. For each tree node u with exactly two children c_1, c_2 the tripartition is (desc(c_1), desc(c_2), X \ (desc(c_1) | desc(c_2))) where X is the full leaf set. The distance is the cardinality of the symmetric difference of the tripartition sets: d_T(N1, N2) = |T(N1) triangle T(N2)| Reticulation nodes (in-degree >= 2) are excluded from tripartition generation. When *normalize* is True the result is divided by |T(N1) | T(N2)|, yielding a value in [0, 1]. Reference --------- Moret *et al.*; Huson, Rupp & Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications* (2010), Chapter 7.

Parameter Type Description
net1 First network.
net2 Second network.
normalize Return a value in [0, 1] instead of a raw count.
Returns: The tripartition distance (int, or float when normalized).
displayed_tree_distance(net1: Network, net2: Network, normalize: bool = False) -> Union[int, float]

Tree-based distance between two phylogenetic networks. Each network's set of unique displayed-tree topologies (identified by cluster representation) is computed. The distance is the cardinality of the symmetric difference: d_DT(N1, N2) = |DT(N1) triangle DT(N2)| .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. When *normalize* is True the result is divided by |DT(N1) | DT(N2)|, yielding a value in [0, 1].

Parameter Type Description
net1 First network.
net2 Second network.
normalize Return a value in [0, 1] instead of a raw count.
Returns: The displayed-tree distance (int, or float when normalized).
robinson_foulds_distance(net1: Network, net2: Network, normalize: bool = False) -> Union[int, float]

Robinson--Foulds distance between two phylogenetic trees or networks. For rooted trees the RF distance equals the cardinality of the symmetric difference of the non-trivial cluster sets (clusters of size >= 2 and < n, where n is the number of leaves). For networks the function uses hardwired clusters, which is the natural generalization of RF to DAGs. Both inputs must share the same leaf label set. When *normalize* is True the result is divided by |C(N1)| + |C(N2)| (the maximum possible RF for the given cluster counts), yielding a value in [0, 1]. Reference --------- Robinson & Foulds. *Comparison of Phylogenetic Trees*. Mathematical Biosciences **53** (1981), 131--147. Cardona, Llabres, Rossello & Valiente. *Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric*. IEEE/ACM Trans. Comput. Biol. Bioinformatics **6** (2009), 46--61.

Parameter Type Description
net1 First tree / network.
net2 Second tree / network.
normalize Return a value in [0, 1] instead of a raw count.
Returns: The RF distance (int, or float when normalized).
Raises: NetworkError: If the two inputs have different leaf label sets.
average_path_distance(net1: Network, net2: Network, normalize: bool = False) -> float

Average Path Distance (APD) between two phylogenetic networks. For each network a pairwise leaf distance matrix is computed by averaging the path lengths across all displayed trees (uniform weighting). The APD is the L1 norm of the difference between the two matrices: APD(N1, N2) = sum_{i<j} |D_N1(l_i,l_j) - D_N2(l_i,l_j)| When *normalize* is True the sum is divided by the number of leaf pairs C(n, 2). Branch lengths on every edge are required. .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. Reference --------- Yakici, Ogilvie & Nakhleh. *Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into Account*. RECOMB-CG 2022, LNCS 13234, pp. 86--102.

Parameter Type Description
net1 First network.
net2 Second network.
normalize Divide by C(n, 2) to get a per-pair average.
Returns: The APD (float).
Raises: NetworkError: If the two networks have different leaf label sets.
weighted_average_path_distance(net1: Network, net2: Network, normalize: bool = False) -> float

Weighted Average Path Distance (WAPD) between two networks. Identical to :func:`average_path_distance` except that the average over displayed trees is weighted by each tree's probability (the product of the gamma values of the kept reticulation edges). WAPD(N1, N2) = sum_{i<j} |WD_N1(l_i,l_j) - WD_N2(l_i,l_j)| When *normalize* is True the sum is divided by the number of leaf pairs C(n, 2). Branch lengths and gamma values on every reticulation edge are required. .. note:: This enumerates all 2^k displayed trees per network. For networks with many reticulations the cost is exponential. Reference --------- Yakici, Ogilvie & Nakhleh. *Phylogenetic Network Dissimilarity Measures that Take Branch Lengths into Account*. RECOMB-CG 2022, LNCS 13234, pp. 86--102.

Parameter Type Description
net1 First network.
net2 Second network.
normalize Divide by C(n, 2) to get a per-pair average.
Returns: The WAPD (float).
Raises: NetworkError: If the two networks have different leaf label sets.
ascii(net: Network, show_edge_lengths: bool = False) -> str

Prints out an ascii art depiction of this Network object as a vertical tree/network with the root at the top and leaves at the bottom.

Parameter Type Description
net Network A Network
show_edge_lengths bool If True, display edge lengths. Defaults to False.
Returns: str: The ASCII art representation of the network Example: For newick string "((C,D)A, E)Root;", outputs:: Root / \ A E / \ C D
reticulation_signature(net: Network, node: Node) -> tuple

Leaf-set signature of one reticulation. The signature is ``(child_branches, parent_branches)``. ``child_branches`` is the list of leaf sets directly below the reticulation's child. ``parent_branches`` has one entry per parent: the leaf sets of that parent's other children (the sibling clades on that side). Parent order is the network's parent order and is not significant for equality; see :func:`same_reticulation`. This is the identity used to decide that two inferred subnetworks found the same hybridization. It is not a phylogenetic distance.

Parameter Type Description
net Network Network containing ``node``.
node Node A reticulation node (in-degree 2).
Returns: tuple: ``(child_branches, parent_branches)``, each a tuple of frozensets (parent side: a tuple of tuples of frozensets).
Raises: NetworkError: If ``node`` is not in ``net``.
same_reticulation(sig_a, sig_b) -> bool

Whether two reticulation signatures are the same event. Parents match up to order. A side matches when one of its sibling branches shares at least one leaf with a sibling branch on the other signature's corresponding side (overlap, not set equality). The child clade is ignored here; callers that need it read it off the signature.

Parameter Type Description
sig_a A signature from :func:`reticulation_signature`, or a record with a ``signature`` attribute or key.
sig_b The signature to compare against.
Returns: bool: True when the two parent pairs overlap in either order.
group_reticulations(records: list) -> list[list]

Group reticulation records that are the same event. The first record of a group is its representative. Later records join the group when :func:`same_reticulation` says they match that representative. Records are not reordered inside a group.

Parameter Type Description
records list Records that carry a ``signature`` (dict key or attribute), as returned alongside :func:`reticulation_signature`.
Returns: list[list]: One list per distinct event.
rooted_triples(net: Network) -> set[tuple[str, str, str]]

Rooted triples displayed by a tree or network. Each triple is ``(a, b, c)`` with ``a < b``, meaning the rooted triple ``(a, b | c)``: ``a`` and ``b`` are together in a clade that excludes ``c``. Every such triple is emitted once, at the node that is the MRCA of ``a`` and ``b``. A root polytomy displays no triple, because no pair is resolved. This is the set the displayed-tree picker counts. It is not :meth:`Network.rooted_triplet_distance`, which is a distance between two networks, and it is not an MSC pseudo-likelihood.

Parameter Type Description
net Network A rooted tree or network.
Returns: set[tuple[str, str, str]]: The displayed triples.

Navigation

Modules

This Page