Runs the InPhyNet algorithm on the given distance matrix and constraint networks where the entries in namelist correspond to indices in D.

calculateAGID(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Distance for all pairs of taxa across all networks in Ns.

Returns

1. AGID matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

Converts the tree/network net into a SimpleGraph to leverage already implemented pathfinding algorithms.

Arguments

• includeminoredges (default=true): if true, the entire network is translated to a graph. Otherwise, only tree-like edges (other than those in alwaysinclude) are retained.
• alwaysinclude (default=nothing): edges that should always be included in the graph, regardless of the value of includeminoredges
• withweights (default=false): return a set of weights corresponding to branch lengths as well
• removeredundantedgecost (default=false): if true, finds all the nodes that would be removed via removeredundantedges! and sets their weights in W to 0

Heuristic for determining whether the set of networks ns are compatible.

calculateAGIC(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Counts for all pairs of taxa across all networks in Ns. If allow_missing_pairs is false, an error will be thrown if there are pairs of taxa that never appear in Ns together. Otherwise, entries for taxa that never appear together will be set to default_missing_value.

Returns

1. AGIC matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

calculateAGID(Ns::AbstractVector{HybridNetwork})

Calculates the Average Gene tree Internode Distance for all pairs of taxa across all networks in Ns.

Returns

1. AGID matrix
2. names of taxa corresponding to rows/columns in the AGID matrix

Calculates pairwise_metric on each pair of networks in Ns. Called by calculateAGIC and calculateAGID. pairwise_metric must be a function that takes a HybridNetwork as its first positional input, must accept the named argument namelist, and must return a 2-Tuple of (A, B), where A is the pairwise metric applied to all pairs of taxa in the supplied network, and B is the namelist used or generated by the fxn.

Slightly adjusted implementation of the decomposition algorithm from SATe-I that takes a maximum and a minimum subset size.

Checks validity of a single input constraint networks. Checks include:

1. All nodes have exactly 3 edges except the root (unless the network is a single taxa)
2. Reticulations do not lead directly into other reticulations

Checks validity of input constraints. So far, the only check is to make sure that all nodes have exactly 3 edges except for the root.

Deals with all the overhead of connecting two nodes with an edge. Returns the edge used to connect the nodes.

Helper function for when an edge (notinpath_edge) appears on but not within a merge path. Finds and returns: 1. Whether the edge should be logged with direction "to" or "from" 2. Whether the edge should be associated with subnetedgei or subnetedgej

Helper function that finds a path in net from nodei to nodej. If that path has 2 or more reticulations in it, the cost to include a hybrid in the path is incrementally increased until only 1 reticulation is in the path.

findoptQ(D::Matrix{Float64}, idxpairs::Vector{Tuple{<:Integer, <:Integer}})

Finds the minimizer (i, j) among all pairs (i, j) in idxpairs for Q, a matrix computed from D.

findsiblingpairs(net::HybridNetwork)

Finds sibling pairings for all the leaves in a single network. These pairs are valid for net but may not be valid when the other constraint networks are also considered. Returns a vector of tuples of nodes corresponding to siblings.

findvalidpairs(constraints::Vector{HybridNetwork}, constraint_sibling_pairs, namelist::AbstractVector{<:AbstractString})

Finds all valid sibling pairs among the constraint networks.

Helper function to remove redundant edges (e.g. A –> (internal node) –> (internal node)) that arise from one case of the function mergeconstraintnodes!.

Redundant nodes in this case will always have only two edges while not being the root.

Helper function used at one point in mergeconstraintnodes!. Gets all of the descendants of node that do not have any children and are not in path

Gets all the leaf nodes underneath edge edge.

Finds a branch in tre that, when pruned on, splits the tree roughly in half.

Helper function - returns true if the node node is connected directly to the root of net, or if the path connecting node to net's root is multiple redundant edges (e.g. returns true for A in the net: "((((((A))))), (B,C));")

Runs the InPhyNet algorithm on the given distance matrix and constraint networks where the entries in namelist correspond to indices in D.

internodecount(N::HybridNetwork; namelist::Union{Nothing,<:AbstractVector{String}}=nothing)

Calculates internode counts between all pairs of taxa in network N. WARNING: treats N as unrooted

internodedistance(N::HybridNetwork; namelist::Union{Nothing,<:AbstractVector{String}}=nothing)

Calculates internode distance between all pairs of taxa in network N.

Helper function

Gets the MRCA of nodei and nodej along their major tree.

majorinternodecount(N::HybridNetwork)

Calculates major internode counts between all pairs of taxa in the major displayed tree of network N. If N is a tree, then internode counts are as expected for a tree.

majorinternodedistance(N::HybridNetwork)

Calculates internode distances between all pairs of taxa in the major displayed tree of network N. If N is a tree, then internode distances are as expected for a tree.

Merges two unrooted SubNets into a single unrooted SubNet Returns the merged subnet AND the edges in the merged net corresponding to where reticulations will be placed if there are corresponding reticulations discovered in the constraints.

IMPORTANT: this function should NOT make copies of edges or nodes, object references are stored and used in the main merging algorithm

Updates net to include the reticulations that we've kept track of along the way in our algo but haven't placed yet.

Returns a list of networks where each entry is a copy of net pruned to include only the taxa named in each subset contained in subsets. subsets can also be an individual vector of strings instead of a nested vector (see examples below).

Example

net = readnewick("((t1,t2),(t3,t4));")
prune_network(net, [["t1", "t2"], ["t3", "t4"]])
> 2-element Vector{HybridNetwork}: (t1, t2); and (t3, t4);

prune_network(net, ["t1", "t2", "t3"])

Helper function that removes redundant edges in the graph that exist when some hybrids are pruned from the graph.

If any constraints are unrooted, picks a root node from any node directly under the root (somewhat randomly).

Performs subset decomposition as outlines in SATe-I on inittree. Returns vector of vector of names, e.g. [["a", "b"], ["c", "d", "e"]]

Splits tre into two trees at its longest branch.

Updates constraint networks after (i, j) with names (nodenamei, nodenamej) have been merged. Also updates reticmap to keep track of any reticulations that get removed in this process.

By convention we keep nodenamei and replace node names with nodenamej

Helper function for manipulating graph adjacency lists.