# spanning_forest_builder
Библиотека для построения ориентированных лесов минимального веса.
**Алгоритм основан на статьях:**\
[springer.com](https://link.springer.com/article/10.1007/s10958-023-06666-w)\
[Записки научных семинаров ПОМИ](http://ftp.pdmi.ras.ru/pub/publicat/znsl/v497/p005.pdf)
## Примеры
### Построить дерево с помощью алгоритма Чу-Ли-Эдмонда
```Python
# Импортируем библиотеку
import spanning_forest_builder as sfb
# Создаем массивы вершин и дуг
# Массив дуг состоит из кортежей (вершина1, вершина2, вес)
nodes = [0, 1, 2, 3, 4]
edges = [(0, 1, 1),
(1, 3, 5),
(2, 1, 4),
(3, 4, 2),
(4, 3, 3),
(4, 0, 5),
(0, 4, 3.5)]
# Строим дерево и рисуем его
# Создаёт директорию image с рисунками графов
sfb.build_tree_Edmonds(nodes, edges)
```
Если дополнительно указать параметр disp=True, то графы также будут выведены на экран
```Python
sfb.build_tree_Edmonds(nodes, edges, disp=True)
```
### Построить все леса
```Python
# Импортируем библиотеку
import spanning_forest_builder as sfb
# Создаем массивы вершин и дуг
# Массив дуг состоит из кортежей (вершина1, вершина2, вес)
nodes = [0, 1, 2, 3, 4]
edges = [(0, 1, 1),
(1, 3, 5),
(2, 1, 4),
(3, 4, 2),
(4, 3, 3),
(4, 0, 5),
(0, 4, 3.5)]
# Строим леса из k деревьев и рисуем их
# Создаёт директорию image с рисунками графов
sfb.build_all_forests(nodes, edges)
```
Если дополнительно указать параметр disp=True, то графы также будут выведены на экран
```Python
sfb.build_all_forests(nodes, edges, disp=True)
```
### Пoлучить дуги дерева в виде массива корежей
```Python
# Импортируем библиотеку
import spanning_forest_builder as sfb
# Создаем массивы вершин и дуг
# Массив дуг состоит из кортежей (вершина1, вершина2, вес)
nodes = [0, 1, 2, 3, 4]
edges = [(0, 1, 1),
(1, 3, 5),
(2, 1, 4),
(3, 4, 2),
(4, 3, 3),
(4, 0, 5),
(0, 4, 3.5)]
# Получаем требуемый массив
result = sfb.build_tree(nodes, edges)
```
### Пoлучить дуги леса из k деревьев в виде массива корежей
```Python
# Импортируем библиотеку
import spanning_forest_builder as sfb
# Создаем массивы вершин и дуг
# Массив дуг состоит из кортежей (вершина1, вершина2, вес)
nodes = [0, 1, 2, 3, 4]
edges = [(0, 1, 1),
(1, 3, 5),
(2, 1, 4),
(3, 4, 2),
(4, 3, 3),
(4, 0, 5),
(0, 4, 3.5)]
# Задаём число деревьев в лесу
k = 3
# Получаем массив массивов
forests = sfb.build_forest(nodes, edges, k)
result = forests[-1]
```
Raw data
{
"_id": null,
"home_page": "",
"name": "spanning-forest-builder",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "spanning forest,spanning tree",
"author": "",
"author_email": "Igor Safronov <I_SIN_I@mail.ru>",
"download_url": "https://files.pythonhosted.org/packages/a8/e7/fede58af803923a3942eb2981d220bfb8688bee0216dd2db410575baa4d2/spanning_forest_builder-0.0.1.tar.gz",
"platform": null,
"description": "# spanning_forest_builder\r\n\u0411\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043b\u0435\u0441\u043e\u0432 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0435\u0441\u0430.\r\n\r\n**\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0441\u0442\u0430\u0442\u044c\u044f\u0445:**\\\r\n[springer.com](https://link.springer.com/article/10.1007/s10958-023-06666-w)\\\r\n[\u0417\u0430\u043f\u0438\u0441\u043a\u0438 \u043d\u0430\u0443\u0447\u043d\u044b\u0445 \u0441\u0435\u043c\u0438\u043d\u0430\u0440\u043e\u0432 \u041f\u041e\u041c\u0418](http://ftp.pdmi.ras.ru/pub/publicat/znsl/v497/p005.pdf)\r\n\r\n## \u041f\u0440\u0438\u043c\u0435\u0440\u044b\r\n\r\n### \u041f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0427\u0443-\u041b\u0438-\u042d\u0434\u043c\u043e\u043d\u0434\u0430\r\n```Python\r\n# \u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443\r\nimport spanning_forest_builder as sfb\r\n\r\n# \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433\r\n# \u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u0443\u0433 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043a\u043e\u0440\u0442\u0435\u0436\u0435\u0439 (\u0432\u0435\u0440\u0448\u0438\u043d\u04301, \u0432\u0435\u0440\u0448\u0438\u043d\u04302, \u0432\u0435\u0441)\r\nnodes = [0, 1, 2, 3, 4]\r\nedges = [(0, 1, 1),\r\n (1, 3, 5),\r\n (2, 1, 4),\r\n (3, 4, 2),\r\n (4, 3, 3),\r\n (4, 0, 5),\r\n (0, 4, 3.5)]\r\n\r\n# \u0421\u0442\u0440\u043e\u0438\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u0438 \u0440\u0438\u0441\u0443\u0435\u043c \u0435\u0433\u043e\r\n# \u0421\u043e\u0437\u0434\u0430\u0451\u0442 \u0434\u0438\u0440\u0435\u043a\u0442\u043e\u0440\u0438\u044e image \u0441 \u0440\u0438\u0441\u0443\u043d\u043a\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u043e\u0432\r\nsfb.build_tree_Edmonds(nodes, edges)\r\n```\r\n\u0415\u0441\u043b\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 disp=True, \u0442\u043e \u0433\u0440\u0430\u0444\u044b \u0442\u0430\u043a\u0436\u0435 \u0431\u0443\u0434\u0443\u0442 \u0432\u044b\u0432\u0435\u0434\u0435\u043d\u044b \u043d\u0430 \u044d\u043a\u0440\u0430\u043d\r\n```Python\r\nsfb.build_tree_Edmonds(nodes, edges, disp=True)\r\n```\r\n\r\n### \u041f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0432\u0441\u0435 \u043b\u0435\u0441\u0430\r\n```Python\r\n# \u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443\r\nimport spanning_forest_builder as sfb\r\n\r\n# \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433\r\n# \u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u0443\u0433 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043a\u043e\u0440\u0442\u0435\u0436\u0435\u0439 (\u0432\u0435\u0440\u0448\u0438\u043d\u04301, \u0432\u0435\u0440\u0448\u0438\u043d\u04302, \u0432\u0435\u0441)\r\nnodes = [0, 1, 2, 3, 4]\r\nedges = [(0, 1, 1),\r\n (1, 3, 5),\r\n (2, 1, 4),\r\n (3, 4, 2),\r\n (4, 3, 3),\r\n (4, 0, 5),\r\n (0, 4, 3.5)]\r\n\r\n# \u0421\u0442\u0440\u043e\u0438\u043c \u043b\u0435\u0441\u0430 \u0438\u0437 k \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0438 \u0440\u0438\u0441\u0443\u0435\u043c \u0438\u0445\r\n# \u0421\u043e\u0437\u0434\u0430\u0451\u0442 \u0434\u0438\u0440\u0435\u043a\u0442\u043e\u0440\u0438\u044e image \u0441 \u0440\u0438\u0441\u0443\u043d\u043a\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u043e\u0432\r\nsfb.build_all_forests(nodes, edges)\r\n```\r\n\u0415\u0441\u043b\u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 disp=True, \u0442\u043e \u0433\u0440\u0430\u0444\u044b \u0442\u0430\u043a\u0436\u0435 \u0431\u0443\u0434\u0443\u0442 \u0432\u044b\u0432\u0435\u0434\u0435\u043d\u044b \u043d\u0430 \u044d\u043a\u0440\u0430\u043d\r\n```Python\r\nsfb.build_all_forests(nodes, edges, disp=True)\r\n```\r\n\r\n### \u041fo\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u0443\u0433\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043a\u043e\u0440\u0435\u0436\u0435\u0439\r\n```Python\r\n# \u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443\r\nimport spanning_forest_builder as sfb\r\n\r\n# \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433\r\n# \u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u0443\u0433 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043a\u043e\u0440\u0442\u0435\u0436\u0435\u0439 (\u0432\u0435\u0440\u0448\u0438\u043d\u04301, \u0432\u0435\u0440\u0448\u0438\u043d\u04302, \u0432\u0435\u0441)\r\nnodes = [0, 1, 2, 3, 4]\r\nedges = [(0, 1, 1),\r\n (1, 3, 5),\r\n (2, 1, 4),\r\n (3, 4, 2),\r\n (4, 3, 3),\r\n (4, 0, 5),\r\n (0, 4, 3.5)]\r\n\r\n# \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432\r\nresult = sfb.build_tree(nodes, edges)\r\n```\r\n\r\n### \u041fo\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u0443\u0433\u0438 \u043b\u0435\u0441\u0430 \u0438\u0437 k \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0432 \u0432\u0438\u0434\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043a\u043e\u0440\u0435\u0436\u0435\u0439\r\n```Python\r\n# \u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443\r\nimport spanning_forest_builder as sfb\r\n\r\n# \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0434\u0443\u0433\r\n# \u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u0443\u0433 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043a\u043e\u0440\u0442\u0435\u0436\u0435\u0439 (\u0432\u0435\u0440\u0448\u0438\u043d\u04301, \u0432\u0435\u0440\u0448\u0438\u043d\u04302, \u0432\u0435\u0441)\r\nnodes = [0, 1, 2, 3, 4]\r\nedges = [(0, 1, 1),\r\n (1, 3, 5),\r\n (2, 1, 4),\r\n (3, 4, 2),\r\n (4, 3, 3),\r\n (4, 0, 5),\r\n (0, 4, 3.5)]\r\n\t\t \r\n# \u0417\u0430\u0434\u0430\u0451\u043c \u0447\u0438\u0441\u043b\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u0432 \u043b\u0435\u0441\u0443\r\nk = 3\r\n\r\n# \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432\r\nforests = sfb.build_forest(nodes, edges, k)\r\nresult = forests[-1]\r\n```\r\n",
"bugtrack_url": null,
"license": "",
"summary": "Build a spanning forest",
"version": "0.0.1",
"project_urls": null,
"split_keywords": [
"spanning forest",
"spanning tree"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "77b6c65110f37a79d43f899740d20d14232aca2237f9d219749cc3b6bfc5ab45",
"md5": "c64ae0694a9f296da5ad2af038454996",
"sha256": "f7327939b896d975fae8a5163caf3b67914cd06eee808eccd12c80ae70e1dc66"
},
"downloads": -1,
"filename": "spanning_forest_builder-0.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c64ae0694a9f296da5ad2af038454996",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 9839,
"upload_time": "2024-01-25T09:43:22",
"upload_time_iso_8601": "2024-01-25T09:43:22.878179Z",
"url": "https://files.pythonhosted.org/packages/77/b6/c65110f37a79d43f899740d20d14232aca2237f9d219749cc3b6bfc5ab45/spanning_forest_builder-0.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a8e7fede58af803923a3942eb2981d220bfb8688bee0216dd2db410575baa4d2",
"md5": "8dedffa53dd7492e7e84dfcabe918035",
"sha256": "ff4b0120e946e9c195d01e85f92afe52a89e94d27a35970c2293e68c4d40656f"
},
"downloads": -1,
"filename": "spanning_forest_builder-0.0.1.tar.gz",
"has_sig": false,
"md5_digest": "8dedffa53dd7492e7e84dfcabe918035",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 8713,
"upload_time": "2024-01-25T09:43:24",
"upload_time_iso_8601": "2024-01-25T09:43:24.602183Z",
"url": "https://files.pythonhosted.org/packages/a8/e7/fede58af803923a3942eb2981d220bfb8688bee0216dd2db410575baa4d2/spanning_forest_builder-0.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-25 09:43:24",
"github": false,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"lcname": "spanning-forest-builder"
}
JSON