This Python package contains a few abstract base classes for tree data structures.
Trees are very common data structure that represents a hierarchy of common nodes.
This package defines abstract base classes for these data structure in order to make code reusable.
## Abstract base classes ##
```python
from abstracttree import to_mermaid
to_mermaid(AbstractTree)
```
```mermaid
graph TD;
AbstractTree[AbstractTree];
UpTree[UpTree];
Tree[Tree];
MutableTree[MutableTree];
DownTree[DownTree];
Tree[Tree];
MutableTree[MutableTree];
MutableDownTree[MutableDownTree];
MutableTree[MutableTree];
BinaryDownTree[BinaryDownTree]
BinaryTree[BinaryTree]
AbstractTree-->UpTree;
UpTree-->Tree;
Tree-->MutableTree;
AbstractTree-->DownTree;
DownTree-->Tree;
DownTree-->MutableDownTree;
MutableDownTree-->MutableTree;
DownTree-->BinaryDownTree
BinaryDownTree-->BinaryTree
Tree-->BinaryTree
```
Downtrees are trees that have links to their direct children.
Uptrees are trees that link to their parent.
A Tree has links in both directions.
| ABC | Inherits from | Abstract Methods | Mixin Methods |
|-------------------|-----------------------------|-----------------------------------|--------------------------------------------------------------------------------------------------------------------------------------|
| `AbstractTree` | | | `nid`, `eqv()` |
| `UpTree` | `AbstractTree` | `parent` | `root`, `is_root`, `ancestors`, `path` |
| `DownTree` | `AbstractTree` | `children` | `nodes`, `descendants`, `leaves`, `levels`, `is_leaf`, `transform()`, `nodes.preorder()`, `nodes.postorder()`, `nodes.levelorder()` |
| `Tree` | `UpTree`, `DownTree` | | `siblings` |
| `MutableDownTree` | `DownTree` | `add_child()`, `remove_child()` | `add_children()` |
| `MutableTree` | `Tree`, `MutableDownTree` | | `detach()` |
| `BinaryDownTree` | `DownTree` | `left_child`, `right_child` | `children`, `nodes.inorder()`, `descendants.inorder()` |
| `BinaryTree` | `BinaryDownTree`, `Tree` | | |
In your own code, you can inherit from these trees.
For example, if your tree only has links to children:
```python
import abstracttree
from abstracttree import print_tree
class MyTree(abstracttree.DownTree):
def __init__(self, value, children=()):
self.value = value
self._children = children
def __str__(self):
return "MyTree " + str(self.value)
@property
def children(self):
return self._children
tree = MyTree(1, children=[MyTree(2), MyTree(3)])
print_tree(tree)
# This generates the following output:
# MyTree 1
# ├─ MyTree 2
# └─ MyTree 3
```
## Adapter ##
In practice, not all existing tree data structures implement one of these abstract classes.
As a bridge, you can use `astree` to convert these trees to a `Tree` instance.
However, whenever possible, it's recommended to inherit from `Tree` directly for minimal overhead.
Examples:
```python
# Trees from built-ins and standard library
astree(int)
astree(ast.parse("1 + 1 == 2"))
astree(pathlib.Path("abstracttree"))
# Anything that has parent and children attributes (anytree / bigtree / littletree)
astree(anytree.Node())
# Nested list
astree([[1, 2, 3], [4, 5, 6]])
# Tree from json-data
data = {"name": "a",
"children": [
{"name": "b", "children": []},
{"name": "c", "children": []}
]}
astree(data, children=operator.itemgetter["children"])
# pyqt.QtWidget
astree(widget, children=lambda w: w.children(), parent = lambda w: w.parent())
# Tree from treelib
astree(tree.root, children=lambda nid: tree.children(nid), parent=lambda nid: tree.parent(nid))
# itertree
astree(tree, children=iter, parent=lambda t: t.parent)
# Infinite binary tree
inf_binary = astree(0, children=lambda n: (2*n + 1, 2*n + 2))
```
## Utility functions
Pretty printing
```python
tree = astree(seq, children=lambda x: [x[:-2], x[1:]] if x else [])
print_tree(tree)
print(to_string(tree))
# ['a', 'b', 'c', 'd']
# ├─ ['a', 'b']
# │ └─ ['b']
# └─ ['b', 'c', 'd']
# ├─ ['b']
# └─ ['c', 'd']
# └─ ['d']
```
Plotting with matplotlib
```python
import matplotlib.pyplot as plt
expr = ast.parse("y = x*x + 1")
plot_tree(expr)
plt.show()
```
Export to various formats
```python
to_dot(tree)
to_mermaid(tree)
to_latex(tree)
to_image(Path('.'), "filetree.png", how="dot")
to_image(AbstractTree, "class_hierarchy.svg", how="mermaid")
to_pillow(tree).show()
```
## Find distance between nodes
```python
import heapq
from abstracttree import HeapTree, Route
tree = HeapTree([5, 4, 3, 2, 1])
heapq.heapify(tree.heap)
left_child = tree.children[0]
right_child = tree.children[1]
route = Route(left_child, right_child)
print(f"{route.lca = }") # => HeapTree([1, 2, 3, 5, 4], 0)
print(f"{route.nodes.count() = }") # => 3
print(f"{route.edges.count() = }") # => 2
```
## A few concrete tree implementations
- [anytree](https://github.com/c0fec0de/anytree)
- [treelib](https://github.com/caesar0301/treelib)
- [bigtree](https://github.com/kayjan/bigtree)
- [itertree](https://github.com/BR1py/itertree)
- [dendropy](https://github.com/jeetsukumaran/DendroPy)
- [ete](https://github.com/etetoolkit/ete)
- [littletree](https://github.com/lverweijen/littletree) - also by me
## Tree visualisation
- [PrettyPrintTree](https://github.com/AharonSambol/PrettyPrintTree) - colored terminal output
Raw data
{
"_id": null,
"home_page": null,
"name": "abstracttree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "tree, datastructure, hierarchy, taxonomy, newick, graphviz, mermaid",
"author": null,
"author_email": "lverweijen <lauwerund@gmail.com>",
"download_url": null,
"platform": null,
"description": "This Python package contains a few abstract base classes for tree data structures.\r\nTrees are very common data structure that represents a hierarchy of common nodes.\r\nThis package defines abstract base classes for these data structure in order to make code reusable.\r\n\r\n## Abstract base classes ##\r\n\r\n```python\r\nfrom abstracttree import to_mermaid\r\n\r\nto_mermaid(AbstractTree)\r\n```\r\n\r\n```mermaid\r\ngraph TD;\r\nAbstractTree[AbstractTree];\r\nUpTree[UpTree];\r\nTree[Tree];\r\nMutableTree[MutableTree];\r\nDownTree[DownTree];\r\nTree[Tree];\r\nMutableTree[MutableTree];\r\nMutableDownTree[MutableDownTree];\r\nMutableTree[MutableTree];\r\nBinaryDownTree[BinaryDownTree]\r\nBinaryTree[BinaryTree]\r\nAbstractTree-->UpTree;\r\nUpTree-->Tree;\r\nTree-->MutableTree;\r\nAbstractTree-->DownTree;\r\nDownTree-->Tree;\r\nDownTree-->MutableDownTree;\r\nMutableDownTree-->MutableTree;\r\nDownTree-->BinaryDownTree\r\nBinaryDownTree-->BinaryTree\r\nTree-->BinaryTree\r\n```\r\n\r\nDowntrees are trees that have links to their direct children.\r\nUptrees are trees that link to their parent.\r\nA Tree has links in both directions.\r\n\r\n| ABC | Inherits from | Abstract Methods | Mixin Methods |\r\n|-------------------|-----------------------------|-----------------------------------|--------------------------------------------------------------------------------------------------------------------------------------|\r\n| `AbstractTree` | | | `nid`, `eqv()` |\r\n| `UpTree` | `AbstractTree` | `parent` | `root`, `is_root`, `ancestors`, `path` |\r\n| `DownTree` | `AbstractTree` | `children` | `nodes`, `descendants`, `leaves`, `levels`, `is_leaf`, `transform()`, `nodes.preorder()`, `nodes.postorder()`, `nodes.levelorder()` |\r\n| `Tree` | `UpTree`, `DownTree` | | `siblings` |\r\n| `MutableDownTree` | `DownTree` | `add_child()`, `remove_child()` | `add_children()` |\r\n| `MutableTree` | `Tree`, `MutableDownTree` | | `detach()` |\r\n| `BinaryDownTree` | `DownTree` | `left_child`, `right_child` | `children`, `nodes.inorder()`, `descendants.inorder()` |\r\n| `BinaryTree` | `BinaryDownTree`, `Tree` | | |\r\n\r\nIn your own code, you can inherit from these trees.\r\nFor example, if your tree only has links to children:\r\n\r\n```python\r\nimport abstracttree\r\nfrom abstracttree import print_tree\r\n\r\nclass MyTree(abstracttree.DownTree):\r\n def __init__(self, value, children=()):\r\n self.value = value\r\n self._children = children\r\n \r\n def __str__(self):\r\n return \"MyTree \" + str(self.value)\r\n\r\n @property\r\n def children(self):\r\n return self._children\r\n\r\ntree = MyTree(1, children=[MyTree(2), MyTree(3)])\r\nprint_tree(tree)\r\n\r\n# This generates the following output:\r\n# MyTree 1\r\n# \u251c\u2500 MyTree 2\r\n# \u2514\u2500 MyTree 3\r\n```\r\n\r\n## Adapter ##\r\n\r\nIn practice, not all existing tree data structures implement one of these abstract classes.\r\nAs a bridge, you can use `astree` to convert these trees to a `Tree` instance.\r\nHowever, whenever possible, it's recommended to inherit from `Tree` directly for minimal overhead.\r\n\r\nExamples:\r\n\r\n```python\r\n# Trees from built-ins and standard library\r\nastree(int)\r\nastree(ast.parse(\"1 + 1 == 2\"))\r\nastree(pathlib.Path(\"abstracttree\"))\r\n\r\n# Anything that has parent and children attributes (anytree / bigtree / littletree)\r\nastree(anytree.Node())\r\n\r\n# Nested list\r\nastree([[1, 2, 3], [4, 5, 6]])\r\n\r\n# Tree from json-data\r\ndata = {\"name\": \"a\",\r\n \"children\": [\r\n {\"name\": \"b\", \"children\": []},\r\n {\"name\": \"c\", \"children\": []}\r\n]}\r\nastree(data, children=operator.itemgetter[\"children\"])\r\n\r\n# pyqt.QtWidget\r\nastree(widget, children=lambda w: w.children(), parent = lambda w: w.parent())\r\n\r\n# Tree from treelib\r\nastree(tree.root, children=lambda nid: tree.children(nid), parent=lambda nid: tree.parent(nid))\r\n\r\n# itertree\r\nastree(tree, children=iter, parent=lambda t: t.parent)\r\n\r\n# Infinite binary tree\r\ninf_binary = astree(0, children=lambda n: (2*n + 1, 2*n + 2))\r\n```\r\n\r\n## Utility functions\r\n\r\nPretty printing\r\n```python\r\ntree = astree(seq, children=lambda x: [x[:-2], x[1:]] if x else [])\r\nprint_tree(tree)\r\nprint(to_string(tree))\r\n\r\n# ['a', 'b', 'c', 'd']\r\n# \u251c\u2500 ['a', 'b']\r\n# \u2502 \u2514\u2500 ['b']\r\n# \u2514\u2500 ['b', 'c', 'd']\r\n# \u251c\u2500 ['b']\r\n# \u2514\u2500 ['c', 'd']\r\n# \u2514\u2500 ['d']\r\n```\r\n\r\nPlotting with matplotlib\r\n```python\r\nimport matplotlib.pyplot as plt\r\n\r\nexpr = ast.parse(\"y = x*x + 1\")\r\nplot_tree(expr)\r\nplt.show()\r\n```\r\n\r\n\r\nExport to various formats\r\n```python\r\nto_dot(tree)\r\nto_mermaid(tree)\r\nto_latex(tree)\r\n\r\nto_image(Path('.'), \"filetree.png\", how=\"dot\")\r\nto_image(AbstractTree, \"class_hierarchy.svg\", how=\"mermaid\")\r\nto_pillow(tree).show()\r\n```\r\n\r\n## Find distance between nodes\r\n\r\n```python\r\nimport heapq\r\n\r\nfrom abstracttree import HeapTree, Route\r\n\r\ntree = HeapTree([5, 4, 3, 2, 1])\r\nheapq.heapify(tree.heap)\r\nleft_child = tree.children[0]\r\nright_child = tree.children[1]\r\n\r\nroute = Route(left_child, right_child)\r\nprint(f\"{route.lca = }\") # => HeapTree([1, 2, 3, 5, 4], 0)\r\nprint(f\"{route.nodes.count() = }\") # => 3\r\nprint(f\"{route.edges.count() = }\") # => 2\r\n```\r\n\r\n## A few concrete tree implementations\r\n\r\n- [anytree](https://github.com/c0fec0de/anytree)\r\n- [treelib](https://github.com/caesar0301/treelib)\r\n- [bigtree](https://github.com/kayjan/bigtree)\r\n- [itertree](https://github.com/BR1py/itertree)\r\n- [dendropy](https://github.com/jeetsukumaran/DendroPy)\r\n- [ete](https://github.com/etetoolkit/ete)\r\n- [littletree](https://github.com/lverweijen/littletree) - also by me\r\n\r\n## Tree visualisation\r\n\r\n- [PrettyPrintTree](https://github.com/AharonSambol/PrettyPrintTree) - colored terminal output\r\n",
"bugtrack_url": null,
"license": "Apache License 2.0",
"summary": "Abstract base classes for tree data structures",
"version": "0.0.5",
"project_urls": {
"Changelog": "https://github.com/lverweijen/abstracttree/blob/main/changes.md",
"Homepage": "https://github.com/lverweijen/abstracttree",
"Issues": "https://github.com/lverweijen/abstracttree/issues",
"Repository": "https://github.com/lverweijen/abstracttree"
},
"split_keywords": [
"tree",
" datastructure",
" hierarchy",
" taxonomy",
" newick",
" graphviz",
" mermaid"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "9d101993b81ddadd90c615656be7bb810c254a401f5c8ccd19a6785c987bc0be",
"md5": "ecac19bba992d9461826ab6378469988",
"sha256": "4275c027130438f20aa77a6f66ffae73012393e6d1fb5517eef7da51ccab3930"
},
"downloads": -1,
"filename": "abstracttree-0.0.5-py3-none-any.whl",
"has_sig": false,
"md5_digest": "ecac19bba992d9461826ab6378469988",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 22933,
"upload_time": "2024-04-01T19:43:01",
"upload_time_iso_8601": "2024-04-01T19:43:01.291577Z",
"url": "https://files.pythonhosted.org/packages/9d/10/1993b81ddadd90c615656be7bb810c254a401f5c8ccd19a6785c987bc0be/abstracttree-0.0.5-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-01 19:43:01",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "lverweijen",
"github_project": "abstracttree",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "abstracttree"
}
JSON
