Metadata-Version: 2.4
Name: tralda
Version: 2.1.0
Summary: A library for tree data structures and algorithms
Author-email: David Schaller <38377210+david-schaller@users.noreply.github.com>
License-Expression: MIT
Project-URL: Repository, https://github.com/david-schaller/tralda.git
Project-URL: Issues, https://github.com/david-schaller/tralda/issues
Keywords: tree,graph,datastructure,LCA,last common ancestor,least common ancestor,supertree,BuildST,triple,dynamic,connectivity,BST,balanced binary search tree,AVL,red-black tree,HDT datastructure,cograph
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx>=3.4.2
Requires-Dist: numpy>=2.2.6
Provides-Extra: matplotlib
Requires-Dist: matplotlib>=3.10.8; extra == "matplotlib"
Provides-Extra: plotly
Requires-Dist: plotly>=6.7.0; extra == "plotly"
Requires-Dist: kaleido>=1.0.0; extra == "plotly"
Provides-Extra: viz
Requires-Dist: tralda[matplotlib,plotly]; extra == "viz"
Dynamic: license-file

# tralda

[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![pypi version](https://img.shields.io/pypi/v/tralda)](https://pypi.org/project/tralda/)
[![Python](https://img.shields.io/pypi/pyversions/tralda)](https://pypi.org/project/tralda/)
[![PyPI downloads](https://img.shields.io/pypi/dm/tralda)](https://pypi.org/project/tralda/)
[![DOI](https://img.shields.io/badge/DOI-10.1186/s13015--021--00202--8-blue)](https://doi.org/10.1186/s13015-021-00202-8)
[![CI](https://github.com/david-schaller/tralda/actions/workflows/ci.yml/badge.svg)](https://github.com/david-schaller/tralda/actions/workflows/ci.yml)

A Python library for **tr**ee **al**gorithms and **da**ta structures.

## Installation and usage

The package requires Python 3.10 or higher.
The `tralda` package is available on [PyPI](https://pypi.org/project/tralda/):

```bash
pip install tralda
```

See also the page [Installation](https://david-schaller.github.io/tralda/installation/) in the
documentation.

The [tralda documentation](https://david-schaller.github.io/tralda/) contains a user guide with
example code as well as the [API reference](https://david-schaller.github.io/tralda/api/trees/).

If you want to contribute to the project, please see the
[contributing guidelines](https://david-schaller.github.io/tralda/contributing/).
Please report any bugs and questions in the
[Issues](https://github.com/david-schaller/tralda/issues) section.

## Overview

`tralda` provides a collection of efficient algorithms and data structures centered around rooted
trees, with a focus on phylogenetics and combinatorial algorithms. It is designed to serve as a
building block for research software in computational biology and related fields.

**Tree data structure** — The `Tree` and `TreeNode` classes in `tralda.datastructures` offer a
flexible rooted-tree representation with support for traversals (preorder, postorder, level-order),
subtree operations, tree generation, and utilities such as topology comparison and hierarchy
extraction.

**Lowest common ancestor (LCA)** — An $O(n)$-time/space preprocessing structure for
$O(1)$ LCA queries, based on the algorithm by Bender et al. (2005).
Available as `LCA` in `tralda.datastructures`.

**Supertree computation** — The `tralda.supertree` subpackage implements several algorithms for
constructing supertrees and consensus trees from a set of (partial) input trees:
- **BUILD** (Aho et al. 1981) — classic triple-based supertree construction.
- **BuildST** (Deng & Fernández-Baca 2016) — fast compatibility testing and supertree construction
  for rooted phylogenetic trees.
- **LinCR** (Schaller et al. 2021) — linear-time algorithm for the minimal common
  refinement of rooted phylogenetic trees on a common leaf set.
- **Loose consensus tree** (Jansson et al. 2016) — linear-time construction of the loose
  consensus tree for trees with the same leaf set.

**Balanced binary search trees** — `tralda.datastructures.bst` provides AVL trees and red-black
trees (ordered sets and dictionaries) with $O(\log n)$ insertion, deletion, and lookup, as well as
efficient split and join operations.

**Dynamic graph connectivity** — The `HDTGraph` class in `tralda.datastructures.hdtgraph`
implements the poly-logarithmic dynamic graph structure described by Holm et al. (2001), supporting
edge insertions and deletions with $O(\log^2 n)$ amortized cost while answering connectivity
queries in $O(\log n)$.

**Cograph detection and editing** — `tralda.cograph` offers linear-time cograph recognition
(Corneil et al. 1985) with cotree construction, as well as a heuristic for cograph editing
(Crespelle 2021) that modifies a graph with a near-minimum number of edge insertions/deletions to
make it a cograph.

## Visualization

`tralda.visualization` renders `Tree` objects as static (matplotlib) or interactive (Plotly)
figures, with horizontal, vertical, and circular layouts and a flexible per-node styling API.
Optional extra: `pip install tralda[viz]`.

<details>
<summary>Click to expand the code example</summary>

```python
from tralda.datastructures import LCA, Tree
from tralda.visualization import plot_tree
from tralda.visualization.style import NodeStyle, TreeStyle

T = Tree.parse_newick(
    "((((Human:6,Chimpanzee:6)HC:2,Gorilla:8)HCG:9,Orangutan:17)Hominidae:3,"
    "(Gibbon:17,Siamang:17)Hylobatidae:3)Hominoidea;"
)

# Compute and highlight the last common ancestor of Human and Gorilla.
lca = LCA(T)
lca_node = lca("Human", "Gorilla")

tree_style = TreeStyle(
    leaf_symbol="circle",
    node_overrides={lca_node: NodeStyle(symbol="star", symbol_size=13, symbol_color="gold")},
)

fig, ax = plot_tree(T, tree_style=tree_style)
```
</details>

![Ape phylogeny with leaf symbols and a highlighted LCA](docs/guide/images/viz-readme-example.png)

See the [visualization user guide](https://david-schaller.github.io/tralda/guide/visualization/)
for the full styling API and more examples.

## Citation and references

If you use `tralda` in your project or code from it, please consider citing:

> Schaller, D., Hellmuth, M., Stadler, P.F. (2021)
> A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common
> leaf set. *Algorithms for Molecular Biology* 16, 23 (2021).
> https://doi.org/10.1186/s13015-021-00202-8

Additional references to algorithms that were implemented are given in the source code.
