# Zdd Algorithms
Zdd algorithms is a Python library that implements the zdd algorithms that are described on the [wikipedia page](https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram). With some additional functions for creating a zdd from a set, a set from a zdd and a function to create an image of the zdd.
## Installation
Use the package manager [pip](https://pip.pypa.io/en/stable/) to install zdd_algorithms.
```bash
pip install zdd-algorithms
```
## Zero-suppressed decision diagram
Zdd are a special kind of binary decision diagram that represents a set of sets.
<p align="center">
<img src="https://raw.githubusercontent.com/Thilo-J/zdd_algorithms/e4185fbbc28a4c59e93c847044b9b9964523dd19/13_23_12.png" alt="zdd"/>
</p>
This Zdd represents the set {{1,3},{2,3},{1,2}} \
Every node has a exactly 2 outgoing edges LO and HI. The LO edge is usally represented by a dotted line and the HI edge with a solid line.
The easiest way to get the set from a visual zdd by hand is to take every path from the root node to the {ø} node(⊤ is also often used as a label for this node).\
Every path represents a set and all paths combined is the set of sets that the Zdd represents.
In this example there are 3 paths from the root node to {ø}. \
If a node has a LO edge in the path that nodes value is ignored. All the other values together represents a set \
3 → 2 → {ø} This path represents the set {3,2} \
3 ⇢ 2 → 1 → {ø} This path represents the set {1,2} \
3 → 2 ⇢ 1 → {ø} This path represents the set {1,3} \
Therefor this zdd represents the set {{1,3},{2,3},{1,2}}
## Usage
Since we cannot have a set of sets in python we use set of frozensets when converting a zdd to the set representation and vice versa
```python
import zdd_algorithms as zdd
# Creates a set of frozensets
set1 = {
frozenset({1,3}),
frozenset({2,3})
}
# Create zdd from the set. This zdd represent now the set {{1,3},{2,3}}
zdd1 = zdd.to_zdd(set1)
set2 = {
frozenset({1,2})
}
zdd2 = zdd.to_zdd(set2)
# Create an union of two zdds
union = zdd.union(zdd1, zdd2)
# Create .PNG image of the zdd. This needs graphviz to be installed!
zdd.create_image(union)
```
<p align="center">
<img src="https://raw.githubusercontent.com/Thilo-J/zdd_algorithms/e4185fbbc28a4c59e93c847044b9b9964523dd19/13_23_12.png" alt="zdd"/>
</p>
## Contributing
Pull requests are welcome. For major changes, please open an issue first
to discuss what you would like to change.
## License
[MIT](https://choosealicense.com/licenses/mit/)
Raw data
{
"_id": null,
"home_page": "https://github.com/Thilo-J/zdd_algorithms",
"name": "zdd-algorithms",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "python,zdd,bdd,zsdd,zero-suppressed,decision diagram",
"author": "Thilo Langensteiner",
"author_email": "<thilo.j.la@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/57/86/bf288e0afac17116eaae490118f2b47bb619b2f1f5e2a5e42c8c8356ff4f/zdd_algorithms-0.1.5.tar.gz",
"platform": null,
"description": "# Zdd Algorithms\n\nZdd algorithms is a Python library that implements the zdd algorithms that are described on the [wikipedia page](https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram). With some additional functions for creating a zdd from a set, a set from a zdd and a function to create an image of the zdd.\n\n## Installation\n\nUse the package manager [pip](https://pip.pypa.io/en/stable/) to install zdd_algorithms.\n\n```bash\npip install zdd-algorithms\n```\n\n## Zero-suppressed decision diagram\n\nZdd are a special kind of binary decision diagram that represents a set of sets.\n\n<p align=\"center\">\n <img src=\"https://raw.githubusercontent.com/Thilo-J/zdd_algorithms/e4185fbbc28a4c59e93c847044b9b9964523dd19/13_23_12.png\" alt=\"zdd\"/>\n</p>\n\nThis Zdd represents the set {{1,3},{2,3},{1,2}} \\\nEvery node has a exactly 2 outgoing edges LO and HI. The LO edge is usally represented by a dotted line and the HI edge with a solid line.\nThe easiest way to get the set from a visual zdd by hand is to take every path from the root node to the {\u00f8} node(\u22a4 is also often used as a label for this node).\\\nEvery path represents a set and all paths combined is the set of sets that the Zdd represents.\nIn this example there are 3 paths from the root node to {\u00f8}. \\\nIf a node has a LO edge in the path that nodes value is ignored. All the other values together represents a set \\\n3 \u2192 2 \u2192 {\u00f8} This path represents the set {3,2} \\\n3 \u21e2 2 \u2192 1 \u2192 {\u00f8} This path represents the set {1,2} \\\n3 \u2192 2 \u21e2 1 \u2192 {\u00f8} This path represents the set {1,3} \\\nTherefor this zdd represents the set {{1,3},{2,3},{1,2}}\n\n## Usage\n\nSince we cannot have a set of sets in python we use set of frozensets when converting a zdd to the set representation and vice versa\n\n```python\nimport zdd_algorithms as zdd\n\n# Creates a set of frozensets\nset1 = {\n frozenset({1,3}),\n frozenset({2,3})\n}\n# Create zdd from the set. This zdd represent now the set {{1,3},{2,3}}\nzdd1 = zdd.to_zdd(set1)\n\nset2 = {\n frozenset({1,2})\n}\nzdd2 = zdd.to_zdd(set2)\n\n# Create an union of two zdds\nunion = zdd.union(zdd1, zdd2)\n\n# Create .PNG image of the zdd. This needs graphviz to be installed! \nzdd.create_image(union)\n```\n\n<p align=\"center\">\n <img src=\"https://raw.githubusercontent.com/Thilo-J/zdd_algorithms/e4185fbbc28a4c59e93c847044b9b9964523dd19/13_23_12.png\" alt=\"zdd\"/>\n</p>\n\n## Contributing\n\nPull requests are welcome. For major changes, please open an issue first\nto discuss what you would like to change.\n\n## License\n\n[MIT](https://choosealicense.com/licenses/mit/)",
"bugtrack_url": null,
"license": "",
"summary": "Implements the zdd algorithms that are on the wiki page",
"version": "0.1.5",
"project_urls": {
"GitHub": "https://github.com/Thilo-J/zdd_algorithms",
"Homepage": "https://github.com/Thilo-J/zdd_algorithms"
},
"split_keywords": [
"python",
"zdd",
"bdd",
"zsdd",
"zero-suppressed",
"decision diagram"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "5786bf288e0afac17116eaae490118f2b47bb619b2f1f5e2a5e42c8c8356ff4f",
"md5": "3674e8498378b2b34ad0cd481b018027",
"sha256": "d8963f109dd50c61b5507830d1d44b0ab1455eab68431017059d6a223ce44848"
},
"downloads": -1,
"filename": "zdd_algorithms-0.1.5.tar.gz",
"has_sig": false,
"md5_digest": "3674e8498378b2b34ad0cd481b018027",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 5637,
"upload_time": "2023-10-22T09:08:56",
"upload_time_iso_8601": "2023-10-22T09:08:56.154693Z",
"url": "https://files.pythonhosted.org/packages/57/86/bf288e0afac17116eaae490118f2b47bb619b2f1f5e2a5e42c8c8356ff4f/zdd_algorithms-0.1.5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-10-22 09:08:56",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Thilo-J",
"github_project": "zdd_algorithms",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "zdd-algorithms"
}
JSON
