# Lazy Tree
[](https://cloud.drone.io/mvcisback/pyLazyTree)
[](https://codecov.io/gh/mvcisback/pyLazyTree)
[](https://badge.fury.io/py/lazytree)
[](https://opensource.org/licenses/MIT)
<!-- markdown-toc start - Don't edit this section. Run M-x markdown-toc-generate-toc again -->
**Table of Contents**
- [Installation](#installation)
- [Usage](#usage)
<!-- markdown-toc end -->
# Installation
If you just need to use `lazytree`, you can just run:
`$ pip install lazytree`
For developers, note that this project uses the
[poetry](https://poetry.eustace.io/) python package/dependency
management tool. Please familarize yourself with it and then
run:
`$ poetry install`
# Usage
A `LazyTree` is a triple, `(root, child_map, view)` where `root : A`
and a child map, `child_map`, which maps `a` to a (finite) list of
children `child_map : A -> List[A]` define the tree's structure and
`view : A -> B` defines what the tree represents. The default view is
the identity map, `lambda x: x`.
This structure is useful for modeling infinite (or really large) trees
where only a finite number of nodes need to be accessed. For example,
the following Binary tree represents the recursive subdivision of the
interval [0, 1].
```python
from lazytree import LazyTree
def split(itvl):
lo, hi = itvl
mid = lo + (hi - lo)/2
return (lo, mid), (mid, hi)
tree = LazyTree(
root=(0, 1), # Initial Itvl
child_map=split # Itvl -> [Itvl]
)
```
Conceptually a `LazyTree` object can be thought of as containing the pieces of data.
1. The `root` of the tree.
2. The data represented by the `root`, accessed via the `view` method.
3. The child subtrees - computed using `child_map` and accessed through the `.children` attribute.
For example, in our interval example, each node corresponds to an interval of `(0, 1)` and has two child subtrees.
```python
# View the current root.
assert tree.view() == tree.root
subtrees = tree.children
assert len(subtrees) == 2
```
Often, for each node in a tree, one is interested in computing a particular function. This can be done using the `map` and `view` methods. For example, below `map` each interval in the tree to it's size. This results in a new `LazyTree` object.
```python
tree2 = tree.map(lambda itvl: itvl[1] - itvl[0]) # Change view to itvl size.
assert tree2.view() == 1
# Access the root's subtrees
subtrees = tree2.children
assert len(subtrees) == 2
assert subtrees[0].root == (0, 0.5)
assert subtrees[0].view() == 0.5
```
Travesals of a `LazyTree` object are also implemented. For example,
```python
# Breadth First Search through tree.
## Note: calls .view() before returning.
itvls = tree.bfs() # returns a generator.
sizes = tree2.bfs() # returns a generator.
assert next(itvls) == (0, 1)
assert next(sizes) == 1
assert next(itvls) == (0, 0.5)
assert next(sizes) == 0.5
assert next(itvls) == (0.5, 1)
assert next(sizes) == 0.5
# Cost guided traversal.
## Note: Smaller means higher priority.
sizes = tree2.cost_guided_refinement(cost=lambda x: x)
assert next(sizes) == 1 # (0, 1)
assert next(sizes) == 0.5 # (0, 0.5)
assert next(sizes) == 0.25 # (0, 0.25)
# Iterative Deepening Depth First Traversal
sizes = tree2.iddfs(max_depth=3) # returns a generator.
assert list(sizes) == [1, 0.5, 0.5, 0.25, 0.25, 0.25, 0.25, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125]
# Note, you can reset the current view.
tree3 = tree2.with_identity_view()
assert tree3.view() == tree.view()
```
Finally, one can "prune" away subtrees by labeling them as leaf nodes using the `prune` method. If you are sure that the resulting tree is finite (either due to pruning or the provided `child_map`) then one can compute the leaves of the tree.
```python
# Prune subtrees with a root of size less than 0.1.
tree4 = tree2.prune(isleaf=lambda s: s < 0.2)
sizes = tree.bfs()
assert all(s > 0.001 for s in sizes) # Note that sizes is now finite.
# Compute leafs of tree. Careful! Could be infinite!
assert all(s == 0.125 for s in tree4.leaves())
assert len(list(tree4.leaves())) == 8
```
Raw data
{
"_id": null,
"home_page": "https://github.com/mvcisback/pyLazyTree",
"name": "lazytree",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6,<4.0",
"maintainer_email": "",
"keywords": "",
"author": "Marcell Vazquez-Chanlatte",
"author_email": "marcell.vc@eecs.berkeley.edu",
"download_url": "https://files.pythonhosted.org/packages/41/9c/f45816d4c4da03eb12d4da72aa8e5d682ba755d113c45de445639f157cad/lazytree-0.3.4.tar.gz",
"platform": null,
"description": "# Lazy Tree\n\n[](https://cloud.drone.io/mvcisback/pyLazyTree)\n[](https://codecov.io/gh/mvcisback/pyLazyTree)\n[](https://badge.fury.io/py/lazytree)\n[](https://opensource.org/licenses/MIT)\n\n<!-- markdown-toc start - Don't edit this section. Run M-x markdown-toc-generate-toc again -->\n**Table of Contents**\n\n- [Installation](#installation)\n- [Usage](#usage)\n\n<!-- markdown-toc end -->\n\n\n# Installation\n\nIf you just need to use `lazytree`, you can just run:\n\n`$ pip install lazytree`\n\nFor developers, note that this project uses the\n[poetry](https://poetry.eustace.io/) python package/dependency\nmanagement tool. Please familarize yourself with it and then\nrun:\n\n`$ poetry install`\n\n# Usage\n\nA `LazyTree` is a triple, `(root, child_map, view)` where `root : A`\nand a child map, `child_map`, which maps `a` to a (finite) list of\nchildren `child_map : A -> List[A]` define the tree's structure and\n`view : A -> B` defines what the tree represents. The default view is\nthe identity map, `lambda x: x`.\n\nThis structure is useful for modeling infinite (or really large) trees\nwhere only a finite number of nodes need to be accessed. For example,\nthe following Binary tree represents the recursive subdivision of the\ninterval [0, 1].\n\n```python\nfrom lazytree import LazyTree\n\ndef split(itvl):\n lo, hi = itvl\n mid = lo + (hi - lo)/2\n return (lo, mid), (mid, hi)\n\ntree = LazyTree(\n root=(0, 1), # Initial Itvl\n child_map=split # Itvl -> [Itvl]\n)\n```\n\nConceptually a `LazyTree` object can be thought of as containing the pieces of data.\n\n1. The `root` of the tree.\n2. The data represented by the `root`, accessed via the `view` method.\n3. The child subtrees - computed using `child_map` and accessed through the `.children` attribute.\n\nFor example, in our interval example, each node corresponds to an interval of `(0, 1)` and has two child subtrees.\n\n```python\n# View the current root.\nassert tree.view() == tree.root\n\nsubtrees = tree.children\nassert len(subtrees) == 2\n```\n\nOften, for each node in a tree, one is interested in computing a particular function. This can be done using the `map` and `view` methods. For example, below `map` each interval in the tree to it's size. This results in a new `LazyTree` object.\n\n```python\ntree2 = tree.map(lambda itvl: itvl[1] - itvl[0]) # Change view to itvl size.\nassert tree2.view() == 1\n\n# Access the root's subtrees\nsubtrees = tree2.children\nassert len(subtrees) == 2\nassert subtrees[0].root == (0, 0.5)\nassert subtrees[0].view() == 0.5\n```\n\nTravesals of a `LazyTree` object are also implemented. For example,\n\n```python\n# Breadth First Search through tree.\n## Note: calls .view() before returning. \nitvls = tree.bfs() # returns a generator.\nsizes = tree2.bfs() # returns a generator.\n\nassert next(itvls) == (0, 1)\nassert next(sizes) == 1\n\nassert next(itvls) == (0, 0.5)\nassert next(sizes) == 0.5\n\nassert next(itvls) == (0.5, 1)\nassert next(sizes) == 0.5\n\n# Cost guided traversal.\n## Note: Smaller means higher priority.\nsizes = tree2.cost_guided_refinement(cost=lambda x: x)\nassert next(sizes) == 1 # (0, 1)\nassert next(sizes) == 0.5 # (0, 0.5)\nassert next(sizes) == 0.25 # (0, 0.25)\n\n# Iterative Deepening Depth First Traversal\nsizes = tree2.iddfs(max_depth=3) # returns a generator.\nassert list(sizes) == [1, 0.5, 0.5, 0.25, 0.25, 0.25, 0.25, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.125]\n\n# Note, you can reset the current view.\ntree3 = tree2.with_identity_view()\nassert tree3.view() == tree.view()\n```\n\nFinally, one can \"prune\" away subtrees by labeling them as leaf nodes using the `prune` method. If you are sure that the resulting tree is finite (either due to pruning or the provided `child_map`) then one can compute the leaves of the tree.\n\n```python\n# Prune subtrees with a root of size less than 0.1.\ntree4 = tree2.prune(isleaf=lambda s: s < 0.2)\nsizes = tree.bfs()\nassert all(s > 0.001 for s in sizes) # Note that sizes is now finite.\n\n\n\n# Compute leafs of tree. Careful! Could be infinite!\nassert all(s == 0.125 for s in tree4.leaves())\nassert len(list(tree4.leaves())) == 8\n```\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Python library for manipulating infinite trees.",
"version": "0.3.4",
"project_urls": {
"Homepage": "https://github.com/mvcisback/pyLazyTree",
"Repository": "https://github.com/mvcisback/pyLazyTree"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "42878d989292d3202019c134d75e2808ee069c7729b78750ac76cf2e36f9f968",
"md5": "04ba8bfaa0b32ced4aa19b878c5e6d50",
"sha256": "a3d9ee2a0d70dda85ddb8807624e8b28848ce5eb7391fe058b0ce4c01a01f0da"
},
"downloads": -1,
"filename": "lazytree-0.3.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "04ba8bfaa0b32ced4aa19b878c5e6d50",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6,<4.0",
"size": 5641,
"upload_time": "2024-01-23T07:07:22",
"upload_time_iso_8601": "2024-01-23T07:07:22.553376Z",
"url": "https://files.pythonhosted.org/packages/42/87/8d989292d3202019c134d75e2808ee069c7729b78750ac76cf2e36f9f968/lazytree-0.3.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "419cf45816d4c4da03eb12d4da72aa8e5d682ba755d113c45de445639f157cad",
"md5": "293d8f8b70a37fc63dfcc66bcd615937",
"sha256": "8998673043d4be464913eea59f18f3e9cd5e996ce8042ba97433ff38165b397b"
},
"downloads": -1,
"filename": "lazytree-0.3.4.tar.gz",
"has_sig": false,
"md5_digest": "293d8f8b70a37fc63dfcc66bcd615937",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6,<4.0",
"size": 4712,
"upload_time": "2024-01-23T07:07:23",
"upload_time_iso_8601": "2024-01-23T07:07:23.783669Z",
"url": "https://files.pythonhosted.org/packages/41/9c/f45816d4c4da03eb12d4da72aa8e5d682ba755d113c45de445639f157cad/lazytree-0.3.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-23 07:07:23",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "mvcisback",
"github_project": "pyLazyTree",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "lazytree"
}
JSON
