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.
There are many different ways to represent them.
This package tries to provide a uniform interface, mixin methods and some utility functions without settling on a concrete tree implementation.
## Abstract base classes ##
```python
from abstracttree import DownTree, to_mermaid
to_mermaid(DownTree)
```
```mermaid
graph TD;
Tree[Tree];
MutableTree[MutableTree];
DownTree[DownTree];
Tree[Tree];
MutableTree[MutableTree];
MutableDownTree[MutableDownTree];
MutableTree[MutableTree];
BinaryDownTree[BinaryDownTree];
BinaryTree[BinaryTree];
Tree-->MutableTree;
DownTree-->Tree;
DownTree-->MutableDownTree;
MutableDownTree-->MutableTree;
DownTree-->BinaryDownTree;
BinaryDownTree-->BinaryTree;
Tree-->BinaryTree;
```
A `Downtree` needs to have links to its direct children, but doesn't require a link to its parent.
A `Tree` needs to have links to both its `children` and its `parent`.
| ABC | Inherits from | Abstract Methods | Mixin Methods |
|-------------------|---------------------------|---------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `DownTree` | | `children` | `nodes`, `nodes.preorder()`, `nodes.postorder()`, `nodes.levelorder()`, `descendants`, `leaves`, `levels`, `levels.zigzag()`, `is_leaf`, `transform()`, `nid`, `eqv()` |
| `Tree` | `DownTree` | `parent` | `root`, `is_root`, `ancestors`, `path`, `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 `AbstractTree.convert` 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
tree = Tree.convert(int)
tree = Tree.convert(ast.parse("1 + 1 == 2"))
tree = Tree.convert(pathlib.Path("abstracttree"))
# Anything that has parent and children attributes (anytree / bigtree / littletree)
tree = Tree.convert(anytree.Node('name'))
# Nested list
tree = Tree.convert([[1, 2, 3], [4, 5, 6]])
```
Or use `astree` if you need a custom function for `parent` or `children`:
```python
# 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_reportlab(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)
route = Route(tree.left_child, tree.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\nThere are many different ways to represent them.\r\nThis package tries to provide a uniform interface, mixin methods and some utility functions without settling on a concrete tree implementation.\r\n\r\n## Abstract base classes ##\r\n\r\n```python\r\nfrom abstracttree import DownTree, to_mermaid\r\n\r\nto_mermaid(DownTree)\r\n```\r\n\r\n```mermaid\r\ngraph TD;\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\nTree-->MutableTree;\r\nDownTree-->Tree;\r\nDownTree-->MutableDownTree;\r\nMutableDownTree-->MutableTree;\r\nDownTree-->BinaryDownTree;\r\nBinaryDownTree-->BinaryTree;\r\nTree-->BinaryTree;\r\n```\r\n\r\nA `Downtree` needs to have links to its direct children, but doesn't require a link to its parent.\r\nA `Tree` needs to have links to both its `children` and its `parent`.\r\n\r\n| ABC | Inherits from | Abstract Methods | Mixin Methods |\r\n|-------------------|---------------------------|---------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\r\n| `DownTree` | | `children` | `nodes`, `nodes.preorder()`, `nodes.postorder()`, `nodes.levelorder()`, `descendants`, `leaves`, `levels`, `levels.zigzag()`, `is_leaf`, `transform()`, `nid`, `eqv()` |\r\n| `Tree` | `DownTree` | `parent` | `root`, `is_root`, `ancestors`, `path`, `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 `AbstractTree.convert` 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\ntree = Tree.convert(int)\r\ntree = Tree.convert(ast.parse(\"1 + 1 == 2\"))\r\ntree = Tree.convert(pathlib.Path(\"abstracttree\"))\r\n\r\n# Anything that has parent and children attributes (anytree / bigtree / littletree)\r\ntree = Tree.convert(anytree.Node('name'))\r\n\r\n# Nested list\r\ntree = Tree.convert([[1, 2, 3], [4, 5, 6]])\r\n```\r\n\r\nOr use `astree` if you need a custom function for `parent` or `children`:\r\n\r\n```python\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\nto_reportlab(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\nroute = Route(tree.left_child, tree.right_child)\r\n\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.1.4",
"project_urls": {
"Changelog": "https://lverweijen.github.io/AbstractTree/CHANGES.html",
"Documentation": "https://lverweijen.github.io/AbstractTree/",
"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": "40b8de5146b367f698c00f5d5749ee1efcac1981cc879e8ecc724b30f1706e49",
"md5": "577d6d098283a76022aaab228e7620b8",
"sha256": "c50abd2ac0c6b1d09ecb9fa3fbe9b9b627be2e48b9e31f3f0cfba1b483bd0df1"
},
"downloads": -1,
"filename": "abstracttree-0.1.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "577d6d098283a76022aaab228e7620b8",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 23140,
"upload_time": "2024-12-20T16:48:13",
"upload_time_iso_8601": "2024-12-20T16:48:13.381143Z",
"url": "https://files.pythonhosted.org/packages/40/b8/de5146b367f698c00f5d5749ee1efcac1981cc879e8ecc724b30f1706e49/abstracttree-0.1.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-20 16:48:13",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "lverweijen",
"github_project": "abstracttree",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "abstracttree"
}
JSON
