| Name | reconfillion JSON |
| Version |
1.0.1
JSON |
| download |
| home_page | None |
| Summary | Solving combinatorial reconfiguration problems. |
| upload_time | 2024-06-16 05:49:24 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | None |
| license | License ======= Reconfillion is distributed with the MIT License. :: Copyright (c) 2024, project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" Jun Kawahara and other contributors All rights reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| keywords |
graph algorithm
combinatorial reconfiguration
graphillion
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# Reconfillion - Python interface for combinatorial reconfiguration problems
Reconfillion was released as version 1.0.0 on April 22, 2024. The older version of reconfillion before that date exists on https://github.com/junkawahara/reconfillion-kari , but is not compatible with this version.
Reconfillion is a tool for solving combinatorial reconfiguration problems. It works with [graphillion](https://github.com/takemaru/graphillion), which means that combinatorial reconfiguration problems of graph classes that are supported by graphillion can be solved by reconfillion.
## Requirements
* [Graphillion version v1.7 or higher](https://github.com/takemaru/graphillion/) is needed.
## License
MIT License
## Quick install
You can install reconfillion via pip.
```
pip install reconfillion
```
## Tutorial
Let's consider to solve the spanning tree reconfiguration problem.
In reconfillion (and graphillion), an edge is represented by a tuple of two vertices, and a graph is represented by a list of edges.
```
# complete graph with 4 vertices [1, 2, 3, 4]
graph = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
```
We import graphillion and reconfillion, and make
GraphSet of all the spanning trees on the graph.
```
from graphillion import GraphSet
from reconfillion import reconf
GraphSet.set_universe(graph) # See the graphillion manual.
spanning_trees = GraphSet.trees(is_spanning = True)
```
Then, by doing the following method, we can obtain the reconfiguration sequence between s and t.
```
s = [(1, 2), (1, 3), (1, 4)] # start spanning tree
t = [(1, 4), (2, 4), (3, 4)] # goal spanning tree
# obtain a reconfiguration sequence between s and t under the token jumping model.
reconf_sequence = reconf.get_reconf_seq(s, t, spanning_trees, model = 'tj')
# obtained [[(1, 4), (2, 4), (3, 4)], [(1, 2), (1, 4), (2, 4)], [(1, 2), (1, 3), (1, 4)]]
```
## Note
This software (and graphillion) needs a lot of memory to solve problems with large-size instances.
## Authors
Reconfillion has been developed by Jun Kawahara and Hiroki Yamazaki.
## Acknowledgment
This project is/was partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20H05794, and JP23H04383.
Raw data
{
"_id": null,
"home_page": null,
"name": "reconfillion",
"maintainer": null,
"docs_url": null,
"requires_python": null,
"maintainer_email": null,
"keywords": "graph algorithm, combinatorial reconfiguration, graphillion",
"author": null,
"author_email": "Jun Kawahara <junkawahara@users.noreply.github.com>",
"download_url": "https://files.pythonhosted.org/packages/5c/2b/7a0bc452153ab45641de9d1940ba7f608a17a20006b118701af2ca0ca49c/reconfillion-1.0.1.tar.gz",
"platform": null,
"description": "# Reconfillion - Python interface for combinatorial reconfiguration problems\n\nReconfillion was released as version 1.0.0 on April 22, 2024. The older version of reconfillion before that date exists on https://github.com/junkawahara/reconfillion-kari , but is not compatible with this version.\n\nReconfillion is a tool for solving combinatorial reconfiguration problems. It works with [graphillion](https://github.com/takemaru/graphillion), which means that combinatorial reconfiguration problems of graph classes that are supported by graphillion can be solved by reconfillion.\n\n## Requirements\n\n* [Graphillion version v1.7 or higher](https://github.com/takemaru/graphillion/) is needed.\n\n## License\n\nMIT License\n\n## Quick install\n\nYou can install reconfillion via pip.\n\n```\npip install reconfillion\n```\n\n## Tutorial\n\nLet's consider to solve the spanning tree reconfiguration problem.\nIn reconfillion (and graphillion), an edge is represented by a tuple of two vertices, and a graph is represented by a list of edges.\n\n```\n# complete graph with 4 vertices [1, 2, 3, 4]\ngraph = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]\n```\n\nWe import graphillion and reconfillion, and make\nGraphSet of all the spanning trees on the graph.\n\n```\nfrom graphillion import GraphSet\nfrom reconfillion import reconf\n\nGraphSet.set_universe(graph) # See the graphillion manual.\nspanning_trees = GraphSet.trees(is_spanning = True)\n```\n\nThen, by doing the following method, we can obtain the reconfiguration sequence between s and t.\n\n```\ns = [(1, 2), (1, 3), (1, 4)] # start spanning tree\nt = [(1, 4), (2, 4), (3, 4)] # goal spanning tree\n\n# obtain a reconfiguration sequence between s and t under the token jumping model.\nreconf_sequence = reconf.get_reconf_seq(s, t, spanning_trees, model = 'tj')\n\n# obtained [[(1, 4), (2, 4), (3, 4)], [(1, 2), (1, 4), (2, 4)], [(1, 2), (1, 3), (1, 4)]]\n```\n\n## Note\n\nThis software (and graphillion) needs a lot of memory to solve problems with large-size instances.\n\n## Authors\n\nReconfillion has been developed by Jun Kawahara and Hiroki Yamazaki.\n\n## Acknowledgment\n\nThis project is/was partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20H05794, and JP23H04383.\n",
"bugtrack_url": null,
"license": "License ======= Reconfillion is distributed with the MIT License. :: Copyright (c) 2024, project \"Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration\" Jun Kawahara and other contributors All rights reserved. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the \"Software\"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ",
"summary": "Solving combinatorial reconfiguration problems.",
"version": "1.0.1",
"project_urls": {
"Homepage": "https://github.com/junkawahara/reconfillion"
},
"split_keywords": [
"graph algorithm",
" combinatorial reconfiguration",
" graphillion"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "fba53e59fd149615111f0a5479689f413c297a3f815fe1569c877644121580c1",
"md5": "7774e99d8c4491d42f04037b13e3ab82",
"sha256": "b52f38fecb6f60c51aef64dcee41e2edef773882ffc1164d056338347c99f218"
},
"downloads": -1,
"filename": "reconfillion-1.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "7774e99d8c4491d42f04037b13e3ab82",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 4668,
"upload_time": "2024-06-16T05:49:23",
"upload_time_iso_8601": "2024-06-16T05:49:23.103585Z",
"url": "https://files.pythonhosted.org/packages/fb/a5/3e59fd149615111f0a5479689f413c297a3f815fe1569c877644121580c1/reconfillion-1.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "5c2b7a0bc452153ab45641de9d1940ba7f608a17a20006b118701af2ca0ca49c",
"md5": "fba4bab086f35a01e06126c31928635e",
"sha256": "ca233fe252c353c6d306af26adfd7016dd697b6cc09068e5b344a7f550f2ab4c"
},
"downloads": -1,
"filename": "reconfillion-1.0.1.tar.gz",
"has_sig": false,
"md5_digest": "fba4bab086f35a01e06126c31928635e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 3675,
"upload_time": "2024-06-16T05:49:24",
"upload_time_iso_8601": "2024-06-16T05:49:24.431242Z",
"url": "https://files.pythonhosted.org/packages/5c/2b/7a0bc452153ab45641de9d1940ba7f608a17a20006b118701af2ca0ca49c/reconfillion-1.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-06-16 05:49:24",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "junkawahara",
"github_project": "reconfillion",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "reconfillion"
}
