Metadata-Version: 2.4
Name: triordinal-dtree
Version: 2.1.0
Summary: DTree (part of Triordinal): incremental encoding of the topology of directed trees by two projections (Q1, Q2): O(1) reachability, and/or queries on the topology of the tree, dynamic (incremental) updates
Author-email: Enis Olgac <enis@digraphs.info>
License: MIT
Project-URL: Homepage, https://github.com/EnisOlgac/Triordinal
Project-URL: Documentation, https://github.com/EnisOlgac/Triordinal/blob/main/docs/API.md
Project-URL: Changelog, https://github.com/EnisOlgac/Triordinal/blob/main/CHANGELOG.md
Project-URL: Paper, https://doi.org/10.5772/intechopen.1013408
Project-URL: DTree archive, https://doi.org/10.5281/zenodo.23395710
Keywords: directed tree,tree topology,reachability,and/or queries,incremental encoding,dynamic tree,graph theory,data structure
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.9
Description-Content-Type: text/markdown
Requires-Dist: triordinal-dlist<3,>=2.1.0

# DTree for Python (triordinal-dtree)

Python implementation of `DTree`, the incremental encoding of the topology of directed trees by two projections Q1 and Q2 (see the [API reference](https://github.com/EnisOlgac/Triordinal/blob/main/docs/API.md) and the [paper](https://doi.org/10.5772/intechopen.1013408)). Python 3.9+.

```
pip install triordinal-dtree
```

The package is imported as `triordinal.dtree` (`from triordinal.dtree import DTree`). It continues `dtree-encoding` (imported as `dtree`), whose last versions point here. It depends only on `triordinal-dlist`, the shared list with rational positions.

```python
from triordinal.dtree import DTree

t = DTree("P1")
t.insert("A", "B")
t.insert("B", "C")

t.can_reach("A", "C")    # True
t.path_to_root("C")      # ['C', 'B', 'A']
t.q1, t.q2               # (['A', 'B', 'C'], ['A', 'B', 'C'])

t.insert("A", "D")
t.cut_n_paste("C", "D")  # move subtree C under D
t.delete("B")            # B's children (none left) move up to A
t.delete_subtree("D")    # removes D and C
```

Load one of the example files (`parent: child1; child2` per line):

```python
t = DTree.from_file("Test.csx")   # e.g. examples/Test.csx from the repository
```

## API (C# name → Python name)

| C# (docs) | Python |
|---|---|
| `DTree(id, strict)` | `DTree(tree_id="P1", strict=False)` (strict: queries raise for unknown nodes) |
| `Insert(parent, child)` | `insert(parent, child)` (last child) |
| `InsertAfter`, `InsertBefore` | `insert_after(sibling, child)`, `insert_before(sibling, child)` |
| `AddLine` | `add_line(line)` (`p: c`, `s > c`, `s < c`; also in `from_file`) |
| `Contains(node)` | `contains(node)` / `node in t` |
| `GetParent(node)` | `get_parent(node)` (`None` for the root) |
| `CutNPaste(u, p)` | `cut_n_paste(subtree_root, new_parent)` |
| `Delete(node)` | `delete(node)`—children move up to the parent |
| — | `delete_subtree(node)`—removes the node and all descendants |
| `Q1`, `Q2` | `Q1`, `Q2` (read-only views of the projections, for list-level checks); `q1`, `q2` (plain lists, without the `[` `]` markers) |
| `Source`, `Sink` | `source`, `sink` |
| `CanReach`, `CanNotReach` | `can_reach`, `can_not_reach` |
| `IsRoot`, `IsLeaf` | `is_root`, `is_leaf` |
| `IsAncestor`, `IsDescendant` | `is_ancestor`, `is_descendant` |
| `SameSubtree`, `SubtreeSize` | `same_subtree`, `subtree_size` (plus `subtree`) |
| `Depth` | `depth` (root = 0) |
| `PathToRoot`, `RootToPath` | `path_to_root`, `root_to_path` (plus `path(u, v)`) |
| `GetNode`, `TryGetNode`, `DNode` | `get_node`, `try_get_node`, `DNode` (node handles; `insert` returns one) |
| `SubtreeLast` | `subtree_last` (last node of a subtree in Q1) |
| `NextInQ1` | `next_in_q1` (next node in Q1, the display order; `None` at the end) |
| `VMin`, `VMax`, `UMin`, `UMax` (of nodes) | `vmin`, `vmax`, `umin`, `umax` |
| `ReachesAll`, `MayReachSome`, `ReachesSome` | `reaches_all`, `may_reach_some`, `reaches_some` |
| `ReachedByAll`, `MayBeReachedBySome`, `ReachedBySome` | `reached_by_all`, `may_be_reached_by_some`, `reached_by_some` |
| `Add`, `Discard`, `Contains` (of a constructed node) | `add`, `discard`, `node in s` |
| `UMin.Covering` | `covering` (topmost member that reaches a node; `None` if none) |

## Semantics

- Every method accepts a node name or a node handle (`DNode`). `insert` returns the handle of the new node, `get_node(name)` gives the handle of an existing one. A handle refers directly to the node's positions in Q1 and Q2, so `can_reach` on handles is two position comparisons without any lookup by name. Handles of deleted nodes, or of another tree, are rejected (KeyError) or reported as unreachable.

- `can_reach(u, v)` is irreflexive: no node reaches itself, so `can_reach(u, u)` is `False`. (The C# prototype is reflexive.)
- A name that is not in the tree, or a handle of a removed node, reaches nothing and is reached by nothing: `can_reach` answers `False`. With `DTree(strict=True)`, `can_reach`, `can_not_reach`, `is_ancestor`, `is_descendant`, `is_root` and the queries of constructed nodes raise `KeyError` instead, so a misspelled name does not hide behind a "not reachable"; `contains` and `same_subtree` never raise.
- Every operation checks its arguments before it changes anything: an operation that raises leaves the tree as it was. Node names are non-empty strings other than the markers `[` and `]`.
- `Q1` and `Q2` are read-only views: they list the nodes and offer the checks of `DList` (`is_left_of`, `precedes`, `index`, `next`, `prev`, ...), but the tree changes only through `DTree` methods.
- `is_ancestor(u, v)` equals `can_reach(u, v)` and is likewise proper.
- `delete(v)` re-attaches v's children to v's parent, in v's place among its siblings.
- `delete_subtree(v)` removes v with all its descendants and returns them in Q1 order.
- `cut_n_paste(u, p)` moves the subtree rooted at u under p as p's last child; p must not lie inside u's subtree.
- And/or queries on the topology: the constructed nodes `vmin(S)`, `vmax(S)` (S as target) and `umin(S)`, `umax(S)` (S as source) take the minimum or maximum of each index over S, separately in Q1 and Q2. `reaches_all` and `reached_by_all` are exact O(1) tests; `may_reach_some` and `may_be_reached_by_some` are only filters, and `reaches_some` and `reached_by_some` are exact in O(log k). Members are added with `add` and removed with `discard`. A constructed node stays valid under insertions and is recomputed automatically after `delete`, `delete_subtree` or `cut_n_paste`. Its members are nodes, not names: a member that was deleted stays out of the set, even if a new node with the same name is inserted later. See [and/or queries on the topology](https://github.com/EnisOlgac/Triordinal/blob/main/docs/and-or-queries.md).
- A node with children has a closing cell in each list, directly after the last cell of its subtree. A new child goes directly before its parent's closing cell in Q1 and directly after the parent in Q2, so every insertion, deletion and move finds its place in both lists without a search. Closing cells are not nodes and are not shown by `Q1` and `Q2`.
- Projection positions are fractions: a new node gets the mediant (a+c)/(b+d) of its neighbors, so normally no other node moves. Insertion patterns that nest new cells ever deeper into one gap—alternating insertions, and deep chains, whose nodes nest into the gap between their parent and its closing cell—trigger a local renumbering. Tree depth and width are unbounded. `t.Q1.index(v)` returns a position as a `Fraction`.

## Tests

```
python -m unittest discover -s tests
```

Every operation is checked against a brute-force parent/children model on random trees, including random sequences of deletes and moves.

## Benchmarks

The benchmarks come with the package, so you can measure on your own machine:

```
python -m triordinal.dtree.bench            # trees of 10,000 and 100,000 nodes
python -m triordinal.dtree.bench --quick    # a few seconds
python -m triordinal.dtree.bench --dynamic  # only the dynamic updates and the tree view
python -m triordinal.dtree.bench --review   # only the patterns from the review of 1.8.0
python -m triordinal.dtree.bench --note "idle machine"   # remark for the report
python -m triordinal.dtree.bench 1000000    # custom sizes
```

In a clone of the repository, `python python/benchmarks/bench.py` runs the same code from the sources.

The script prints Markdown tables: build time and renumbering counts per tree shape (random, chain, star at the root, star at an inner node, alternating worst case), list growth at either end, and timings for `can_reach`, `depth`, `delete`, `cut_n_paste` and `delete_subtree`, and comparisons with a classical parent walk: reachability by tree depth, and/or queries with constructed nodes, dynamic updates (insertions with 1 or 10 queries each, and static pre/post numbers at depths 100 and 1,000), and a tree view with expand/collapse; finally the complexity patterns from Onur Safi's review of DTree 1.8.0 and the memory per node. Each dynamic measurement is the best of three runs. Each `DList` keeps the counters `renumber_count` and `renumber_moved`, so the same figures are available in your own code via `t.Q1` and `t.Q2`.

Every run also writes its tables as a Markdown report to `benchmarks/python/`—in the current directory, or at the repository root when run inside a clone— named after date and time (for example `2026-10-17_14-18.md`), with a header giving the DTree and Python versions, the operating system and the processor; `--no-save` skips it. The C# benchmarks (`dotnet run --project csharp/Triordinal.DTree.Tests -c Release -- bench`) write theirs to `benchmarks/csharp/`.

## Provenance

Design and API: Enis Olgac. This Python port was written with Claude (Anthropic) from the C# original and the API reference.
