AlgoTree
========
.. image:: https://img.shields.io/pypi/v/AlgoTree.svg
:target: https://pypi.org/project/AlgoTree/
.. image:: https://img.shields.io/pypi/l/AlgoTree.svg
:target: https://pypi.org/project/AlgoTree/
```AlgoTree``` is a Python package for working with tree structures, including
FlatForest and TreeNode representations.
Introduction
------------
Welcome to the documentation for the ```AlgoTree``` package. This package provides a
suite of utilities for working with tree-like data structures in Python. It
supports various tree representations, including:
- ``FlatForest`` and ``FlatForestNode`` for working with flat forest and tree structures
- ``TreeNode`` for recursive tree structures
- Conversion utilities to convert between different tree representations
- Utility functions for common tree operations
It also comes with a command-line tool ``jt`` that exposes most of the functionality:
- Can be used to create, manipulate, query, and visualize trees
- It's like ``jq`` but for trees
- Uses piping and redirection to make it easy to compose commands
Getting Started
---------------
To install the ``AlgoTree`` package, you can use pip:
.. code-block:: shell
pip install AlgoTree
Once installed, you can start using the various tree structures and utilities
provided by the package. Here is a quick example to get you started:
.. code-block:: python
from AlgoTree.flat_forest_node import FlatForestNode
from AlgoTree.pretty_tree import pretty_tree
root = FlatForestNode(name="root", data=0)
node1 = FlatForestNode(name="node1", parent=root, data=1)
node2 = FlatForestNode(name="node2", parent=root, data=2)
node3 = FlatForestNode(name="node3", parent=node2, data=3)
node4 = FlatForestNode(name="node4", parent=node3, data=4)
pretty_tree(root)
This produces the output::
root
├── node1
└── node2
└── node3
└── node4
This code creates a simple tree with a root node and two child nodes. It then
pretty-prints the tree.
The ``AlgoTree`` package provides a wide range of tree structures and utilities
to help you work with tree-like data structures in Python. You can explore the
documentation to learn more about the available features and how to use them.
Features
--------
- Flexible tree structures with ``FlatForest``, ``FlatForestNode``, and ``TreeNode``
- Utility functions for common tree operations such as traversal, searching, and manipulation
- Conversion utilities to easily convert between different tree representations
- Integration with visualization tools to visualize tree structures
Node-Centric API
----------------
We implement two tree data structures:
- ``FlatForest`` for working with flat tree structures with
"pointers" to parent nodes. It uses a proxy object ``FlatForestNode`` to
provide a node-centric API.
- ``TreeNode`` for recursive tree structures, in which each node is a dictionary
with an optional list of child nodes.
Each representation has its own strengths and weaknesses. The key design point
for ``FlatForest`` and ``TreeNode`` is that they are both also ``dict`` objects, i.e.,
they provide a *view* of dictionaries as tree-like structures, as long as the
dictionaries are structured in a certain way. We document that structure
elsewhere.
Each tree data structure models the *concept* of a tree node so that the
underlying implementations can be decoupled from any algorithms
or operations that we may want to perform on the tree.
The tree node concept is defined as follows:
- **children** property
Represents a list of child nodes for the current node that can be
accessed and modified[1_].
- **parent** property
Represents the parent node of the current node that can be accessed
and modified[2_].
Suppose we have the subtree ``G`` at node ``G``::
B (root)
├── D
└── E (parent)
└── G (current node)
Then, ``G.parent`` should refer node ``E``. ``G.root.parent`` should be None
since ``root`` is the root node of subtree ``G`` and the root node has no parent.
This is true even if subtree ``G`` is a subtree view of a larger tree.
If we set ``G.parent = D``, then the tree structure changes to::
B (root)
├── D
│ └── G (current node)
└── E
This also changes the view of the sub-tree, since we changed the
underlying tree structure. However, the same nodes are still accessible
from the sub-tree.
If we had set ``G.parent = X`` where ``X`` is not in the subtree ``G``, then
we would have an invalid subtree view even if is is a well-defined
operation on the underlying tree structure. It is undefined
behavior to set a parent that is not in the subtree, but leave it
up to each implementation to decide how to handle such cases.
- **node(name: str) -> NodeType** method.
Returns a node in the current subtree that the
current node belongs to. The returned node should be the node with the
given name, if it exists. If the node does not exist, it should raise
a ``KeyError``.
The node-centric view of the returned node should be consistent with the
view of the current node, i.e., if the current node belongs to a specific sub-tree
rooted at some other node, the returned node should also belong to the
same sub-tree (i.e., with the same root), just pointing to the new node,
but it should be possible to use ``parent`` and ``children`` to go up and down
the sub-tree to reach the same nodes. Any node that is an ancestor of the
root of the sub-tree remains inaccessible.
Example: Suppose we have the sub-tree ``t`` rooted at ``A`` and the current node
is ``B``::
A (root)
├── B (current node)
│ ├── D
│ └── E
| └── G
└── C
└── F
If we get node ``F``, ``t.node(F)``, then the sub-tree ``t`` remains the same,
but the current node is now ``F``::
A (root)
├── B
│ ├── D
│ └── E
| └── G
└── C
└── F (current node)
- **subtree(name: Optional[str] = None) -> NodeType** method.
This is an optional method that may not be implemented by all tree
structures. ``FlatForestNode`` implements this method, but ``TreeNode`` does
not.
Returns a view of another sub-tree rooted at ``node`` where ``node`` is
contained in the original sub-tree view. If ``node`` is ``None``, the method
will return the sub-tree rooted at the current node.
As a view, the subtree represents a way of looking at the tree structure
from a different perspective. If you modify the sub-tree, you are also
modifying the underlying tree structure. The sub-tree should be a
consistent view of the tree, i.e., it should be possible to use ``parent``
and ``children`` to navigate between the nodes in the sub-tree and the
nodes in the original tree.
``subtree`` is a *partial function* over the the nodes in the sub-tree,
which means it is only well-defined when ``node`` is a descendant of
the root of the sub-tree. We do not specify how to deal with the case
when this condition is not met, but one approach would be to raise an
exception.
Example: Suppose we have the sub-tree `t` rooted at `A` and the current node
is `C`::
A (root)
├── B
│ ├── D
│ └── E
| └── G
└── C (current node)
└── F
The subtree `t.subtree(B)` returns a new subtree::
B (root, current node)
├── D
└── E
└── G
- **root** property
An immutable property that represents the root node of the (sub)tree.
Suppose we have the subtree ``G`` at node ``G``::
B (root)
├── D
└── E
└── G (current node)
Then, `G.root` should refer node `B`.
- **payload** property
Returns the payload of the current node. The payload
is the data associated with the node but not with the structure of the
tree, e.g., it does not include the ``parent`` or ``children`` of the node.
- **name** property
Returns the name of the current node. The name is
an identifier for the node within the tree. It is not necessarily unique,
and nor is it necessarily even a meaningful identifier, e.g., a random
UUID.
In ``TreeNode``, for instance, if the name is not set, a UUID is generated.
.. [1] Modifying this property may change the **parent** property of other nodes.
.. [2] Modifying this property may change the **children** property of other nodes.
Raw data
{
"_id": null,
"home_page": "https://github.com/queelius/AlgoTree",
"name": "AlgoTree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": null,
"keywords": null,
"author": "Alex Towell",
"author_email": "lex@metafunctor.com",
"download_url": "https://files.pythonhosted.org/packages/49/8f/94e5edb355e9c6bed4bd8a1d23b4065e292d089d21bd1bab4d72b334e173/AlgoTree-0.7.3.tar.gz",
"platform": null,
"description": "AlgoTree\n========\n\n.. image:: https://img.shields.io/pypi/v/AlgoTree.svg\n :target: https://pypi.org/project/AlgoTree/\n\n.. image:: https://img.shields.io/pypi/l/AlgoTree.svg\n :target: https://pypi.org/project/AlgoTree/\n\n```AlgoTree``` is a Python package for working with tree structures, including\nFlatForest and TreeNode representations.\n\n\nIntroduction\n------------\n\nWelcome to the documentation for the ```AlgoTree``` package. This package provides a\nsuite of utilities for working with tree-like data structures in Python. It\nsupports various tree representations, including:\n\n- ``FlatForest`` and ``FlatForestNode`` for working with flat forest and tree structures\n- ``TreeNode`` for recursive tree structures\n- Conversion utilities to convert between different tree representations\n- Utility functions for common tree operations\n\nIt also comes with a command-line tool ``jt`` that exposes most of the functionality:\n\n- Can be used to create, manipulate, query, and visualize trees\n- It's like ``jq`` but for trees\n- Uses piping and redirection to make it easy to compose commands\n\nGetting Started\n---------------\n\nTo install the ``AlgoTree`` package, you can use pip:\n\n.. code-block:: shell\n\n pip install AlgoTree\n\nOnce installed, you can start using the various tree structures and utilities\nprovided by the package. Here is a quick example to get you started:\n\n.. code-block:: python\n\n from AlgoTree.flat_forest_node import FlatForestNode\n from AlgoTree.pretty_tree import pretty_tree\n root = FlatForestNode(name=\"root\", data=0)\n node1 = FlatForestNode(name=\"node1\", parent=root, data=1)\n node2 = FlatForestNode(name=\"node2\", parent=root, data=2)\n node3 = FlatForestNode(name=\"node3\", parent=node2, data=3)\n node4 = FlatForestNode(name=\"node4\", parent=node3, data=4)\n\n pretty_tree(root)\n\nThis produces the output::\n\n root\n \u251c\u2500\u2500 node1\n \u2514\u2500\u2500 node2\n \u2514\u2500\u2500 node3\n \u2514\u2500\u2500 node4\n\nThis code creates a simple tree with a root node and two child nodes. It then\npretty-prints the tree.\n\nThe ``AlgoTree`` package provides a wide range of tree structures and utilities\nto help you work with tree-like data structures in Python. You can explore the\ndocumentation to learn more about the available features and how to use them.\n\nFeatures\n--------\n\n- Flexible tree structures with ``FlatForest``, ``FlatForestNode``, and ``TreeNode``\n- Utility functions for common tree operations such as traversal, searching, and manipulation\n- Conversion utilities to easily convert between different tree representations\n- Integration with visualization tools to visualize tree structures\n\n\nNode-Centric API\n----------------\n\nWe implement two tree data structures:\n\n- ``FlatForest`` for working with flat tree structures with\n \"pointers\" to parent nodes. It uses a proxy object ``FlatForestNode`` to\n provide a node-centric API.\n- ``TreeNode`` for recursive tree structures, in which each node is a dictionary\n with an optional list of child nodes.\n\nEach representation has its own strengths and weaknesses. The key design point\nfor ``FlatForest`` and ``TreeNode`` is that they are both also ``dict`` objects, i.e.,\nthey provide a *view* of dictionaries as tree-like structures, as long as the\ndictionaries are structured in a certain way. We document that structure\nelsewhere.\n\nEach tree data structure models the *concept* of a tree node so that the\nunderlying implementations can be decoupled from any algorithms\nor operations that we may want to perform on the tree.\n\nThe tree node concept is defined as follows:\n\n- **children** property\n\n Represents a list of child nodes for the current node that can be\n accessed and modified[1_].\n\n- **parent** property\n\n Represents the parent node of the current node that can be accessed\n and modified[2_]. \n \n Suppose we have the subtree ``G`` at node ``G``::\n\n B (root)\n \u251c\u2500\u2500 D\n \u2514\u2500\u2500 E (parent)\n \u2514\u2500\u2500 G (current node)\n\n Then, ``G.parent`` should refer node ``E``. ``G.root.parent`` should be None\n since ``root`` is the root node of subtree ``G`` and the root node has no parent.\n This is true even if subtree ``G`` is a subtree view of a larger tree.\n\n If we set ``G.parent = D``, then the tree structure changes to::\n\n B (root)\n \u251c\u2500\u2500 D\n \u2502 \u2514\u2500\u2500 G (current node)\n \u2514\u2500\u2500 E\n \n This also changes the view of the sub-tree, since we changed the\n underlying tree structure. However, the same nodes are still accessible\n from the sub-tree.\n\n If we had set ``G.parent = X`` where ``X`` is not in the subtree ``G``, then\n we would have an invalid subtree view even if is is a well-defined\n operation on the underlying tree structure. It is undefined\n behavior to set a parent that is not in the subtree, but leave it\n up to each implementation to decide how to handle such cases.\n\n- **node(name: str) -> NodeType** method.\n\n Returns a node in the current subtree that the\n current node belongs to. The returned node should be the node with the\n given name, if it exists. If the node does not exist, it should raise\n a ``KeyError``.\n\n The node-centric view of the returned node should be consistent with the\n view of the current node, i.e., if the current node belongs to a specific sub-tree\n rooted at some other node, the returned node should also belong to the\n same sub-tree (i.e., with the same root), just pointing to the new node,\n but it should be possible to use ``parent`` and ``children`` to go up and down\n the sub-tree to reach the same nodes. Any node that is an ancestor of the\n root of the sub-tree remains inaccessible.\n\n Example: Suppose we have the sub-tree ``t`` rooted at ``A`` and the current node\n is ``B``::\n\n A (root)\n \u251c\u2500\u2500 B (current node)\n \u2502 \u251c\u2500\u2500 D\n \u2502 \u2514\u2500\u2500 E\n | \u2514\u2500\u2500 G\n \u2514\u2500\u2500 C\n \u2514\u2500\u2500 F\n \n If we get node ``F``, ``t.node(F)``, then the sub-tree ``t`` remains the same,\n but the current node is now ``F``::\n \n A (root)\n \u251c\u2500\u2500 B\n \u2502 \u251c\u2500\u2500 D\n \u2502 \u2514\u2500\u2500 E\n | \u2514\u2500\u2500 G\n \u2514\u2500\u2500 C\n \u2514\u2500\u2500 F (current node)\n\n- **subtree(name: Optional[str] = None) -> NodeType** method.\n\n This is an optional method that may not be implemented by all tree\n structures. ``FlatForestNode`` implements this method, but ``TreeNode`` does\n not.\n\n Returns a view of another sub-tree rooted at ``node`` where ``node`` is\n contained in the original sub-tree view. If ``node`` is ``None``, the method\n will return the sub-tree rooted at the current node.\n\n As a view, the subtree represents a way of looking at the tree structure\n from a different perspective. If you modify the sub-tree, you are also\n modifying the underlying tree structure. The sub-tree should be a\n consistent view of the tree, i.e., it should be possible to use ``parent``\n and ``children`` to navigate between the nodes in the sub-tree and the\n nodes in the original tree.\n \n ``subtree`` is a *partial function* over the the nodes in the sub-tree,\n which means it is only well-defined when ``node`` is a descendant of\n the root of the sub-tree. We do not specify how to deal with the case\n when this condition is not met, but one approach would be to raise an\n exception.\n\n Example: Suppose we have the sub-tree `t` rooted at `A` and the current node\n is `C`::\n\n A (root)\n \u251c\u2500\u2500 B\n \u2502 \u251c\u2500\u2500 D\n \u2502 \u2514\u2500\u2500 E\n | \u2514\u2500\u2500 G\n \u2514\u2500\u2500 C (current node)\n \u2514\u2500\u2500 F\n\n The subtree `t.subtree(B)` returns a new subtree::\n\n B (root, current node)\n \u251c\u2500\u2500 D\n \u2514\u2500\u2500 E\n \u2514\u2500\u2500 G\n\n- **root** property\n\n An immutable property that represents the root node of the (sub)tree.\n \n Suppose we have the subtree ``G`` at node ``G``::\n\n B (root)\n \u251c\u2500\u2500 D\n \u2514\u2500\u2500 E\n \u2514\u2500\u2500 G (current node)\n\n Then, `G.root` should refer node `B`.\n\n- **payload** property\n\n Returns the payload of the current node. The payload\n is the data associated with the node but not with the structure of the\n tree, e.g., it does not include the ``parent`` or ``children`` of the node.\n\n- **name** property\n\n Returns the name of the current node. The name is\n an identifier for the node within the tree. It is not necessarily unique,\n and nor is it necessarily even a meaningful identifier, e.g., a random\n UUID.\n \n In ``TreeNode``, for instance, if the name is not set, a UUID is generated.\n\n.. [1] Modifying this property may change the **parent** property of other nodes.\n\n.. [2] Modifying this property may change the **children** property of other nodes.\n",
"bugtrack_url": null,
"license": null,
"summary": "A algorithmic tookit for working with trees in Python",
"version": "0.7.3",
"project_urls": {
"Documentation": "https://queelius.github.io/AlgoTree/",
"Homepage": "https://github.com/queelius/AlgoTree",
"Issue Tracker": "https://github.com/queelius/AlgoTree/issues",
"Source Code": "https://github.com/queelius/AlgoTree"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "4261e56c56b075a1c9995e93ec31cdbdaacd893fb88629b0b90e9e8cd4c24f88",
"md5": "9e28924ba07d06f34fee94d8f1550985",
"sha256": "4eec22dbf89d32689b8b2c456901a165eee1c007b95f5dc1f5b94423c1cc0352"
},
"downloads": -1,
"filename": "AlgoTree-0.7.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "9e28924ba07d06f34fee94d8f1550985",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6",
"size": 49843,
"upload_time": "2024-10-31T01:21:19",
"upload_time_iso_8601": "2024-10-31T01:21:19.548919Z",
"url": "https://files.pythonhosted.org/packages/42/61/e56c56b075a1c9995e93ec31cdbdaacd893fb88629b0b90e9e8cd4c24f88/AlgoTree-0.7.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "498f94e5edb355e9c6bed4bd8a1d23b4065e292d089d21bd1bab4d72b334e173",
"md5": "e53724f3c8cf40dbf1d1c1d14357333b",
"sha256": "349eee21a57c5f40f157be218788f944a723047b35b7945a56058219b383287d"
},
"downloads": -1,
"filename": "AlgoTree-0.7.3.tar.gz",
"has_sig": false,
"md5_digest": "e53724f3c8cf40dbf1d1c1d14357333b",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 37679,
"upload_time": "2024-10-31T01:21:20",
"upload_time_iso_8601": "2024-10-31T01:21:20.859762Z",
"url": "https://files.pythonhosted.org/packages/49/8f/94e5edb355e9c6bed4bd8a1d23b4065e292d089d21bd1bab4d72b334e173/AlgoTree-0.7.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-10-31 01:21:20",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "queelius",
"github_project": "AlgoTree",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [],
"lcname": "algotree"
}
JSON
