Metadata-Version: 2.4
Name: dtree-encoding
Version: 1.6.0
Summary: DTree: 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/DTree
Project-URL: Documentation, https://github.com/EnisOlgac/DTree/blob/main/docs/API.md
Project-URL: Changelog, https://github.com/EnisOlgac/DTree/blob/main/CHANGELOG.md
Project-URL: Paper, https://doi.org/10.5772/intechopen.1013408
Project-URL: 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.8
Description-Content-Type: text/markdown

# DTree for Python

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/DTree/blob/main/docs/API.md) and the [paper](https://doi.org/10.5772/intechopen.1013408)). No dependencies; Python 3.8+.

```
pip install dtree-encoding
```

The package is imported as `dtree`.

```python
from 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)` | `DTree(tree_id="P1")` |
| `Insert(parent, child)` | `insert(parent, child)` |
| `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` (the `DList` 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) |
| `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` |

## 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.)
- `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). A constructed node stays valid under insertions and is recomputed automatically after `delete`, `delete_subtree` or `cut_n_paste`. See [and/or queries on the topology](https://github.com/EnisOlgac/DTree/blob/main/docs/and-or-queries.md).
- Projection positions are fractions: a new node gets the mediant (a+c)/(b+d) of its neighbors, so normally no other node moves. Only rare alternating insertion patterns 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

```
python benchmarks/bench.py            # trees of 10,000 and 100,000 nodes
python benchmarks/bench.py --quick    # a few seconds
python benchmarks/bench.py --dynamic  # only insertions and queries alternating
python benchmarks/bench.py 1000000    # custom sizes
```

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, and dynamic updates (insertions and queries alternating). 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`.

## Provenance

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