# allforgraphs Library #
## What is this? ##
allforgraphs – это библиотека для работы с графами и построением матриц. Она включает в себя два модуля: алгоритмы для задач с графами и методы генерации матриц.
## Quick Guide ##
### Структура библиотеки ###
allforgraphs состоит из двух модулей:
1. algorithms - Модуль для работы с алгоритмами графа.
2. matrices - Модуль для работы с матрицами, связанными с графами.
## Installation ##
Чтобы начать работу с allforgraphs, установите её через pip:
```pip install allforgraphs```
## Using ##
После установки библиотеку можно импортировать с помощью:
``` python
from allforgraphs import *
```
## Modules Overview ##
### Algorithms Module ###
#### Функция find_shortest_path(edges_input, start_node, end_node) позволяет находить кратчайший путь между двумя узлами в ориентированном графе, используя алгоритм Дейкстры. #####
Параметры:
1. edges_input: список рёбер графа, где каждое ребро представлено кортежем (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
2. start_node: узел, от которого начинается поиск кратчайшего пути.
3. end_node: узел, до которого необходимо найти путь.
Возвращает:
Кортеж, содержащий кратчайшее расстояние и сам путь в виде списка узлов.
Пример использования:
``` python
from allforgraphs.algorithms.dr import find_shortest_path
edges_input = [
(11, 3, 1), (5, 4, 3), (8, 5, 4), (12, 6, 5), (3, 8, 6),
(14, 8, 20), (7, 19, 20), (2, 19, 7), (9, 2, 7), (4, 1, 2),
(10, 7, 32), (6, 32, 31), (15, 32, 34), (13, 31, 7),
(1, 34, 31), (8, 19, 21), (11, 21, 20), (7, 29, 8),
(2, 29, 30), (5, 33, 29), (14, 8, 30), (6, 30, 33),
(12, 31, 22), (3, 24, 22), (9, 22, 25), (5, 26, 24),
(7, 25, 26), (13, 26, 23), (1, 23, 30), (4, 26, 27),
(8, 27, 28), (2, 23, 28), (10, 11, 12), (15, 13, 14),
(12, 16, 15), (6, 18, 17)
]
start_node = 34
end_node = 8
distance, path = find_shortest_path(edges_input, start_node, end_node)
print(f"Кратчайшее расстояние от {start_node} до {end_node}: {distance}")
print(f"Путь: {' -> '.join(map(str, path))}")
```
#### Функция kruskal_maximum_tree(edges_input) реализует алгоритм Краскала для нахождения максимального охватывающего дерева в графе ####
Параметры:
1. edges_input: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
Возвращает:
Кортеж, содержащий список рёбер максимального покрывающего дерева и его общий вес.
Пример использования:
``` python
from allforgraphs.algorithms.kr_max import kruskal_maximum_tree
edges_input = [
(9, 0, 1), (12, 0, 2), (10, 1, 2), (15, 1, 3),
(5, 2, 3), (20, 2, 4), (25, 3, 4), (30, 4, 5)
]
max_tree_edges, max_tree_weight = kruskal_maximum_tree(edges_input)
print('Максимальное покрывающее дерево:')
for edge in max_tree_edges:
print(f'Вес: {edge[0]}, Вершины: ({edge[1]}, {edge[2]})')
print('Общий вес максимального покрывающего дерева:', max_tree_weight)
```
#### Функция kruskal_minimum_tree(edges_input) реализует алгоритм Краскала для нахождения минимального охватывающего дерева в графе. ####
Параметры:
1. edges_input: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
Возвращает:
Кортеж, содержащий список рёбер минимального покрывающего дерева и его общий вес.
Пример использования:
``` python
from allforgraphs.algorithms.kr_min import kruskal_minimum_tree
edges_input = [
(11, 3, 1), (5, 4, 3), (8, 5, 4), (12, 6, 5), (3, 8, 6),
(14, 8, 20), (7, 19, 20), (2, 19, 7), (9, 2, 7), (4, 1, 2),
(10, 7, 32), (6, 32, 31), (15, 32, 34), (13, 31, 7), (1, 34, 31),
(8, 19, 21), (11, 21, 20), (7, 29, 8), (2, 29, 30), (5, 33, 29),
(14, 8, 30), (6, 30, 33), (12, 31, 22), (3, 24, 22), (9, 22, 25),
(5, 26, 24), (7, 25, 26), (13, 26, 23), (1, 23, 30), (4, 26, 27),
(8, 27, 28), (2, 23, 28), (10, 11, 12), (15, 13, 14), (12, 16, 15),
(6, 18, 17)
]
min_tree_edges, min_tree_weight = kruskal_minimum_tree(edges_input)
print('Минимальное покрывающее дерево:')
for edge in min_tree_edges:
print(f'Вес: {edge[0]}, Вершины: ({edge[1]}, {edge[2]})')
print('Общий вес минимального покрывающего дерева:', min_tree_weight)
```
#### Метод prima_maximum_covering_tree реализует алгоритм Прима для построения максимального покрывающего дерева на основе заданного графа. ####
Класс Graph_1 используется для представления графа, который инициализируется списком рёбер. Каждый элемент рёбер представляет собой кортеж, содержащий вес ребра и узлы, которые оно соединяет.
Параметры: Не имеет параметров, так как использует внутреннее состояние объекта Graph, включающее список рёбер, узлы и другие переменные.
Возвращает:
1. total_weight: Общий вес максимального покрывающего дерева (целое число).
2. tree_ribs: Список рёбер, входящих в максимальное покрывающее дерево. Каждый элемент списка представляет собой кортеж (узел1, узел2, вес).
Пример использования:
``` python
from allforgraphs.algorithms.prima_max import prima_maximum_covering_tree
E = [
(18, 1, 2), (14, 2, 3), (23, 4, 5), (12, 5, 6),
(16, 1, 6), (28, 6, 8), (24, 8, 9), (3, 9, 10)
]
graph = Graph_1(E)
total_weight, max_tree_ribs = graph.prima_maximum_covering_tree()
print("Общий вес максимального покрывающего дерева:", total_weight)
print("Рёбра максимального покрывающего дерева:")
for u, v, weight in max_tree_ribs:
print(f"Вес: {weight}, Ребро: ({u}, {v})")
```
#### Метод prima_minimum_covering_tree реализует алгоритм Прима для построения минимального покрывающего дерева. ####
Класс Graph используется для представления графа, который инициализируется списком рёбер. Каждый элемент рёбер представляет собой кортеж, содержащий вес ребра и узлы, которые оно соединяет.
Параметры: Не имеет параметров, так как использует внутреннее состояние объекта Graph_2, включающее список рёбер, узлы и другие переменные.
Возвращает:
1. total_weight: Общий вес минимального покрывающего дерева (целое число).
2. min_tree_ribs: Список рёбер, входящих в минимальное покрывающее дерево, заданный в формате (узел1, узел2, вес)
Пример использования:
``` python
from allforgraphs.algorithms.prima_min import prima_minimum_covering_tree
E = [
(1, 1, 3), (1, 2, 6), (2, 2, 4),
(3, 1, 5), (4, 3, 4), (5, 4, 5),
(6, 3, 5), (7, 1, 2), (7, 4, 6)
]
graph = Graph_2(E)
total_weight, min_tree_ribs = graph.prima_minimum_covering_tree()
print("Общий вес минимального покрывающего дерева:", total_weight)
print("Рёбра минимального покрывающего дерева:")
for u, v, weight in min_tree_ribs:
print(f"Вес: {weight}, Ребро: ({u}, {v})")
```
#### Функция find_eulerian_cycle находит Эйлеров цикл в неориентированном графе, заданном списком рёбер. ####
Параметры:
1. edges: Список рёбер графа, где каждое ребро представлено как кортеж (узел1, узел2).
2. start_vertex: Узел, с которого начинается поиск Эйлерова цикла.
Возвращает:
1. path: Список вершин, представляющий Эйлеров цикл. Если Эйлеров цикл отсутствует, возвращается пустой список.
Пример использования:
``` python
from allforgraphs.algorithms.euler_gr import find_eulerian_cycle
edges = [
(1, 2), (1, 5), (1, 7), (1, 4), (2, 3),
(2, 5), (2, 6), (4, 5), (5, 6), (5, 7),
(5, 8), (6, 7), (7, 8), (6, 8), (6, 9),
(6, 3), (8, 9)
]
start_vertex = 5
cycle = find_eulerian_cycle(edges, start_vertex)
print("Эйлеров цикл:", cycle)
```
### Matrices Module ###
##### Функция build_incidence_matrix(edges) строит матрицу инцидентности для графа, заданного списком рёбер. ####
Параметры:
1. edges: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
Возвращает:
Матрицу инцидентности в виде списка списков. Если список рёбер пуст, возвращает None.
Пример использования:
``` python
from allforgraphs.matrices.matr_sm import build_incidence_matrix
edges = [
(5, 1, 2),
(0, 1, 3),
(4, 2, 3),
(3, 3, 4),
(2, 4, 1),
(0, 2, 4)
]
incidence_matrix = build_incidence_matrix(edges)
if incidence_matrix:
print("Матрица инцидентности:")
print(incidence_matrix)
else:
print("Список рёбер пуст.")
```
#### Функция build_adjacency_matrix(edges) строит матрицу смежности для графа, заданного списком рёбер. ####
Параметры:
1. edges: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
Возвращает:
Матрицу смежности в виде списка списков. Если список рёбер пуст или не содержит рёбер с ненулевым весом, возвращает None.
Пример использования:
``` python
from allforgraphs.matrices.matr_sm import build_adjacency_matrix
edges = [
(5, 1, 2),
(0, 1, 3),
(4, 2, 3),
(3, 3, 4),
(2, 4, 1),
(0, 2, 4)
]
adjacency_matrix = build_adjacency_matrix(edges)
if adjacency_matrix:
print("Матрица смежности:")
print(adjacency_matrix)
else:
print("Список рёбер пуст.")
```
#### Функция build_weight_matrix(edges) строит матрицу весов для графа, заданного списком рёбер. ####
Параметры:
1. edges: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
Возвращает:
Матрицу весов в виде списка списков. Если список рёбер пуст, возвращает None. Веса, отсутствующие в графе, инициализируются значением бесконечности (inf). Для диаметрических рёбер диагональные элементы устанавливаются в 0.
Пример использования:
``` python
from allforgraphs.matrices.matr_sm import build_weight_matrix
edges = [
(5, 1, 2),
(10, 1, 3),
(0, 2, 3),
(7, 3, 4),
(2, 4, 1),
(3, 2, 4)
]
weight_matrix = build_weight_matrix(edges)
if weight_matrix:
print("Матрица весов:")
print(weight_matrix)
else:
print("Список рёбер пуст.")
```
#### Функция transitive_closure(edges, num_vertices) вычисляет матрицу транзитивного замыкания для графа, заданного списком рёбер. ####
Параметры:
1. edges: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
2. num_vertices: общее количество вершин в графе.
Возвращает:
Матрицу транзитивного замыкания в виде списка списков, где значение 1 указывает на наличие пути между вершинами, а 0 — на отсутствие пути.
Пример использования:
``` python
from allforgraphs.matrices.matr_sm import transitive_closure
edges_input = [
(5, 1, 2), (4, 2, 4), (4, 2, 3), (7, 3, 1)
]
num_vertices = max(max(i, j) for _, i, j in edges_input)
closure_matrix = transitive_closure(edges_input, num_vertices)
print("Матрица транзитивного замыкания:")
for row in closure_matrix:
print(" ".join(map(str, row)))
```
#### Функция floyd_warshall(edges, num_vertices) реализует алгоритм Флойда-Уоршелла для нахождения кратчайших расстояний между всеми парами вершин в графе. ####
Параметры:
1. edges: список рёбер графа в формате (weight, node1, node2), где weight — это вес ребра, а node1 и node2 — вершины, соединённые этим ребром.
2. num_vertices: общее количество вершин в графе.
Возвращает:
Матрицу расстояний в виде списка списков, где значение на позиции [i][j] представляет кратчайшее расстояние от вершины i до вершины j. Если путь отсутствует, значение будет равно float('inf').
Пример использования:
``` python
from allforgraphs.matrices.matr_sm import floyd_warshall
edges_input = [
(2, 1, 2), (1, 2, 3), (6, 2, 3), (1, 3, 1), (5, 1, 3)
]
num_vertices = max(max(i, j) for _, i, j in edges_input)
shortest_paths_matrix = floyd_warshall(edges_input, num_vertices)
print("Матрица кратчайших расстояний:")
for row in shortest_paths_matrix:
print(" ".join(map(lambda x: f"{x:5}" if x != float('inf') else " INF", row)))
```
## Developers ##
Авторы библиотеки: Бызова Мария, Верниковская Екатерина, Ольга Калашникова.
GitHub Бызовой Марии: [link](https://github.com/mobyzova)
GitHub Верниковской Екатерины: [link](https://github.com/Katerok27153)
GitHub Калашниковой Ольги: [link](https://github.com/lacrimell)
Raw data
{
"_id": null,
"home_page": "https://github.com/Katerok27153/allforgraphs.git",
"name": "allforgraphs",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": null,
"keywords": "files speedfiles",
"author": "katya,maria,olga",
"author_email": "1132236136@pfur.ru",
"download_url": "https://files.pythonhosted.org/packages/a5/19/5ba348df1add27f5fe308855632dbf0843a18dbeb911c5e9aed5d82f34e3/allforgraphs-1.0.1.tar.gz",
"platform": null,
"description": "# allforgraphs Library #\n\n## What is this? ##\nallforgraphs \u2013 \u044d\u0442\u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435\u043c \u043c\u0430\u0442\u0440\u0438\u0446. \u041e\u043d\u0430 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u0432 \u0441\u0435\u0431\u044f \u0434\u0432\u0430 \u043c\u043e\u0434\u0443\u043b\u044f: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447 \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043c\u0430\u0442\u0440\u0438\u0446.\n\n## Quick Guide ##\n### \u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 ###\n\nallforgraphs \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043c\u043e\u0434\u0443\u043b\u0435\u0439:\n\n1. algorithms - \u041c\u043e\u0434\u0443\u043b\u044c \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430.\n2. matrices - \u041c\u043e\u0434\u0443\u043b\u044c \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c\u0438, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u043c\u0438 \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438.\n\n## Installation ## \n\n\u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0447\u0430\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0443 \u0441 allforgraphs, \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0435 \u0435\u0451 \u0447\u0435\u0440\u0435\u0437 pip:\n\n```pip install allforgraphs```\n\n\n## Using ##\n\n\u041f\u043e\u0441\u043b\u0435 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 \u043c\u043e\u0436\u043d\u043e \u0438\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e:\n\n``` python\nfrom allforgraphs import *\n```\n\n## Modules Overview ##\n\n### Algorithms Module ###\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f find_shortest_path(edges_input, start_node, end_node) \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0443\u0437\u043b\u0430\u043c\u0438 \u0432 \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b. #####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges_input: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043e \u043a\u043e\u0440\u0442\u0435\u0436\u0435\u043c (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n2. start_node: \u0443\u0437\u0435\u043b, \u043e\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0438\u0441\u043a \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438.\n3. end_node: \u0443\u0437\u0435\u043b, \u0434\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u043f\u0443\u0442\u044c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041a\u043e\u0440\u0442\u0435\u0436, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0441\u0430\u043c \u043f\u0443\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0443\u0437\u043b\u043e\u0432.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.dr import find_shortest_path\n\nedges_input = [\n (11, 3, 1), (5, 4, 3), (8, 5, 4), (12, 6, 5), (3, 8, 6), \n (14, 8, 20), (7, 19, 20), (2, 19, 7), (9, 2, 7), (4, 1, 2),\n (10, 7, 32), (6, 32, 31), (15, 32, 34), (13, 31, 7), \n (1, 34, 31), (8, 19, 21), (11, 21, 20), (7, 29, 8), \n (2, 29, 30), (5, 33, 29), (14, 8, 30), (6, 30, 33), \n (12, 31, 22), (3, 24, 22), (9, 22, 25), (5, 26, 24), \n (7, 25, 26), (13, 26, 23), (1, 23, 30), (4, 26, 27), \n (8, 27, 28), (2, 23, 28), (10, 11, 12), (15, 13, 14), \n (12, 16, 15), (6, 18, 17)\n]\nstart_node = 34\nend_node = 8\n\ndistance, path = find_shortest_path(edges_input, start_node, end_node)\nprint(f\"\u041a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 {start_node} \u0434\u043e {end_node}: {distance}\")\nprint(f\"\u041f\u0443\u0442\u044c: {' -> '.join(map(str, path))}\")\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f kruskal_maximum_tree(edges_input) \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041a\u0440\u0430\u0441\u043a\u0430\u043b\u0430 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435 ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges_input: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041a\u043e\u0440\u0442\u0435\u0436, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0435\u0433\u043e \u043e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.kr_max import kruskal_maximum_tree\n\nedges_input = [\n (9, 0, 1), (12, 0, 2), (10, 1, 2), (15, 1, 3),\n (5, 2, 3), (20, 2, 4), (25, 3, 4), (30, 4, 5)\n]\n\nmax_tree_edges, max_tree_weight = kruskal_maximum_tree(edges_input)\n\nprint('\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:')\nfor edge in max_tree_edges:\n print(f'\u0412\u0435\u0441: {edge[0]}, \u0412\u0435\u0440\u0448\u0438\u043d\u044b: ({edge[1]}, {edge[2]})')\n\nprint('\u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:', max_tree_weight)\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f kruskal_minimum_tree(edges_input) \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041a\u0440\u0430\u0441\u043a\u0430\u043b\u0430 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges_input: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041a\u043e\u0440\u0442\u0435\u0436, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0435\u0433\u043e \u043e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.kr_min import kruskal_minimum_tree\n\nedges_input = [\n (11, 3, 1), (5, 4, 3), (8, 5, 4), (12, 6, 5), (3, 8, 6),\n (14, 8, 20), (7, 19, 20), (2, 19, 7), (9, 2, 7), (4, 1, 2),\n (10, 7, 32), (6, 32, 31), (15, 32, 34), (13, 31, 7), (1, 34, 31),\n (8, 19, 21), (11, 21, 20), (7, 29, 8), (2, 29, 30), (5, 33, 29),\n (14, 8, 30), (6, 30, 33), (12, 31, 22), (3, 24, 22), (9, 22, 25),\n (5, 26, 24), (7, 25, 26), (13, 26, 23), (1, 23, 30), (4, 26, 27),\n (8, 27, 28), (2, 23, 28), (10, 11, 12), (15, 13, 14), (12, 16, 15),\n (6, 18, 17)\n]\n\nmin_tree_edges, min_tree_weight = kruskal_minimum_tree(edges_input)\n\nprint('\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:')\nfor edge in min_tree_edges:\n print(f'\u0412\u0435\u0441: {edge[0]}, \u0412\u0435\u0440\u0448\u0438\u043d\u044b: ({edge[1]}, {edge[2]})')\n\nprint('\u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:', min_tree_weight)\n```\n\n#### \u041c\u0435\u0442\u043e\u0434 prima_maximum_covering_tree \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430. ####\n\n\u041a\u043b\u0430\u0441\u0441 Graph_1 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0440\u0451\u0431\u0435\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043a\u043e\u0440\u0442\u0435\u0436, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u0438 \u0443\u0437\u043b\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043d\u043e \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u0442.\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b: \u041d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432, \u0442\u0430\u043a \u043a\u0430\u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 Graph, \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0435\u0435 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440, \u0443\u0437\u043b\u044b \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\n1. total_weight: \u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 (\u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e). \n2. tree_ribs: \u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0434\u0435\u0440\u0435\u0432\u043e. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441\u043f\u0438\u0441\u043a\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043a\u043e\u0440\u0442\u0435\u0436 (\u0443\u0437\u0435\u043b1, \u0443\u0437\u0435\u043b2, \u0432\u0435\u0441).\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.prima_max import prima_maximum_covering_tree\n\nE = [\n (18, 1, 2), (14, 2, 3), (23, 4, 5), (12, 5, 6),\n (16, 1, 6), (28, 6, 8), (24, 8, 9), (3, 9, 10)\n ]\n \n graph = Graph_1(E)\n total_weight, max_tree_ribs = graph.prima_maximum_covering_tree()\n\n print(\"\u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:\", total_weight)\n print(\"\u0420\u0451\u0431\u0440\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:\")\n for u, v, weight in max_tree_ribs:\n print(f\"\u0412\u0435\u0441: {weight}, \u0420\u0435\u0431\u0440\u043e: ({u}, {v})\")\n```\n\n#### \u041c\u0435\u0442\u043e\u0434 prima_minimum_covering_tree \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041f\u0440\u0438\u043c\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. ####\n\n\u041a\u043b\u0430\u0441\u0441 Graph \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0440\u0451\u0431\u0435\u0440 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043a\u043e\u0440\u0442\u0435\u0436, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u0438 \u0443\u0437\u043b\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043d\u043e \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u0442.\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b: \u041d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432, \u0442\u0430\u043a \u043a\u0430\u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 Graph_2, \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0435\u0435 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440, \u0443\u0437\u043b\u044b \u0438 \u0434\u0440\u0443\u0433\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442: \n1. total_weight: \u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 (\u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e).\n2. min_tree_ribs: \u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0439 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (\u0443\u0437\u0435\u043b1, \u0443\u0437\u0435\u043b2, \u0432\u0435\u0441)\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.prima_min import prima_minimum_covering_tree\n\nE = [\n (1, 1, 3), (1, 2, 6), (2, 2, 4),\n (3, 1, 5), (4, 3, 4), (5, 4, 5),\n (6, 3, 5), (7, 1, 2), (7, 4, 6)\n ]\n \n graph = Graph_2(E)\n total_weight, min_tree_ribs = graph.prima_minimum_covering_tree()\n\n print(\"\u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:\", total_weight)\n print(\"\u0420\u0451\u0431\u0440\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430:\")\n for u, v, weight in min_tree_ribs:\n print(f\"\u0412\u0435\u0441: {weight}, \u0420\u0435\u0431\u0440\u043e: ({u}, {v})\")\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f find_eulerian_cycle \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u042d\u0439\u043b\u0435\u0440\u043e\u0432 \u0446\u0438\u043a\u043b \u0432 \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435, \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043e \u043a\u0430\u043a \u043a\u043e\u0440\u0442\u0435\u0436 (\u0443\u0437\u0435\u043b1, \u0443\u0437\u0435\u043b2).\n2. start_vertex: \u0423\u0437\u0435\u043b, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u0438\u0441\u043a \u042d\u0439\u043b\u0435\u0440\u043e\u0432\u0430 \u0446\u0438\u043a\u043b\u0430.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\n1. path: \u0421\u043f\u0438\u0441\u043e\u043a \u0432\u0435\u0440\u0448\u0438\u043d, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u042d\u0439\u043b\u0435\u0440\u043e\u0432 \u0446\u0438\u043a\u043b. \u0415\u0441\u043b\u0438 \u042d\u0439\u043b\u0435\u0440\u043e\u0432 \u0446\u0438\u043a\u043b \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043f\u0443\u0441\u0442\u043e\u0439 \u0441\u043f\u0438\u0441\u043e\u043a.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.algorithms.euler_gr import find_eulerian_cycle\n\n edges = [\n (1, 2), (1, 5), (1, 7), (1, 4), (2, 3),\n (2, 5), (2, 6), (4, 5), (5, 6), (5, 7),\n (5, 8), (6, 7), (7, 8), (6, 8), (6, 9),\n (6, 3), (8, 9)\n ]\n\n start_vertex = 5\n\n cycle = find_eulerian_cycle(edges, start_vertex)\n print(\"\u042d\u0439\u043b\u0435\u0440\u043e\u0432 \u0446\u0438\u043a\u043b:\", cycle)\n```\n\n### Matrices Module ###\n\n##### \u0424\u0443\u043d\u043a\u0446\u0438\u044f build_incidence_matrix(edges) \u0441\u0442\u0440\u043e\u0438\u0442 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0438\u043d\u0446\u0438\u0434\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430, \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041c\u0430\u0442\u0440\u0438\u0446\u0443 \u0438\u043d\u0446\u0438\u0434\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441\u043f\u0438\u0441\u043a\u043e\u0432. \u0415\u0441\u043b\u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 None.\n\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f:\n\n``` python\nfrom allforgraphs.matrices.matr_sm import build_incidence_matrix\n\nedges = [\n (5, 1, 2),\n (0, 1, 3),\n (4, 2, 3),\n (3, 3, 4),\n (2, 4, 1),\n (0, 2, 4)\n]\n\nincidence_matrix = build_incidence_matrix(edges)\n\nif incidence_matrix:\n print(\"\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0438\u043d\u0446\u0438\u0434\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u0438:\")\n print(incidence_matrix)\nelse:\n print(\"\u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442.\")\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f build_adjacency_matrix(edges) \u0441\u0442\u0440\u043e\u0438\u0442 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430, \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441\u043f\u0438\u0441\u043a\u043e\u0432. \u0415\u0441\u043b\u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442 \u0438\u043b\u0438 \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0440\u0451\u0431\u0435\u0440 \u0441 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u043c \u0432\u0435\u0441\u043e\u043c, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 None.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.matrices.matr_sm import build_adjacency_matrix\n\nedges = [\n (5, 1, 2),\n (0, 1, 3),\n (4, 2, 3),\n (3, 3, 4),\n (2, 4, 1),\n (0, 2, 4)\n]\n\nadjacency_matrix = build_adjacency_matrix(edges)\n\nif adjacency_matrix:\n print(\"\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438:\")\n print(adjacency_matrix)\nelse:\n print(\"\u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442.\")\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f build_weight_matrix(edges) \u0441\u0442\u0440\u043e\u0438\u0442 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0432\u0435\u0441\u043e\u0432 \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430, \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041c\u0430\u0442\u0440\u0438\u0446\u0443 \u0432\u0435\u0441\u043e\u0432 \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441\u043f\u0438\u0441\u043a\u043e\u0432. \u0415\u0441\u043b\u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442, \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 None. \u0412\u0435\u0441\u0430, \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0432 \u0433\u0440\u0430\u0444\u0435, \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u0438 (inf). \u0414\u043b\u044f \u0434\u0438\u0430\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0440\u0451\u0431\u0435\u0440 \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432 0.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.matrices.matr_sm import build_weight_matrix\n\nedges = [\n (5, 1, 2),\n (10, 1, 3),\n (0, 2, 3),\n (7, 3, 4),\n (2, 4, 1),\n (3, 2, 4)\n]\n\nweight_matrix = build_weight_matrix(edges)\n\nif weight_matrix:\n print(\"\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0432\u0435\u0441\u043e\u0432:\")\n print(weight_matrix)\nelse:\n print(\"\u0421\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u043f\u0443\u0441\u0442.\")\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f transitive_closure(edges, num_vertices) \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0442\u0440\u0430\u043d\u0437\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u044b\u043a\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430, \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0440\u0451\u0431\u0435\u0440. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n2. num_vertices: \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0432 \u0433\u0440\u0430\u0444\u0435.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041c\u0430\u0442\u0440\u0438\u0446\u0443 \u0442\u0440\u0430\u043d\u0437\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u044b\u043a\u0430\u043d\u0438\u044f \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u0433\u0434\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 1 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438, \u0430 0 \u2014 \u043d\u0430 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u043f\u0443\u0442\u0438.\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.matrices.matr_sm import transitive_closure\n\nedges_input = [\n (5, 1, 2), (4, 2, 4), (4, 2, 3), (7, 3, 1)\n]\n\nnum_vertices = max(max(i, j) for _, i, j in edges_input)\n\nclosure_matrix = transitive_closure(edges_input, num_vertices)\n\nprint(\"\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u0442\u0440\u0430\u043d\u0437\u0438\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u044b\u043a\u0430\u043d\u0438\u044f:\")\nfor row in closure_matrix:\n print(\" \".join(map(str, row)))\n```\n\n#### \u0424\u0443\u043d\u043a\u0446\u0438\u044f floyd_warshall(edges, num_vertices) \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0424\u043b\u043e\u0439\u0434\u0430-\u0423\u043e\u0440\u0448\u0435\u043b\u043b\u0430 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0432\u0441\u0435\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0438 \u0432\u0435\u0440\u0448\u0438\u043d \u0432 \u0433\u0440\u0430\u0444\u0435. ####\n\n\u041f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b:\n\n1. edges: \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 (weight, node1, node2), \u0433\u0434\u0435 weight \u2014 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430, \u0430 node1 \u0438 node2 \u2014 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0441\u043e\u0435\u0434\u0438\u043d\u0451\u043d\u043d\u044b\u0435 \u044d\u0442\u0438\u043c \u0440\u0435\u0431\u0440\u043e\u043c.\n2. num_vertices: \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0432 \u0433\u0440\u0430\u0444\u0435.\n\n\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442:\n\u041c\u0430\u0442\u0440\u0438\u0446\u0443 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0432 \u0432\u0438\u0434\u0435 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441\u043f\u0438\u0441\u043a\u043e\u0432, \u0433\u0434\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 [i][j] \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b i \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b j. \u0415\u0441\u043b\u0438 \u043f\u0443\u0442\u044c \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e float('inf').\n\n\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f: \n\n``` python\nfrom allforgraphs.matrices.matr_sm import floyd_warshall\n\nedges_input = [\n (2, 1, 2), (1, 2, 3), (6, 2, 3), (1, 3, 1), (5, 1, 3)\n]\n\nnum_vertices = max(max(i, j) for _, i, j in edges_input)\nshortest_paths_matrix = floyd_warshall(edges_input, num_vertices)\n\nprint(\"\u041c\u0430\u0442\u0440\u0438\u0446\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439:\")\nfor row in shortest_paths_matrix:\n print(\" \".join(map(lambda x: f\"{x:5}\" if x != float('inf') else \" INF\", row)))\n```\n\n## Developers ##\n\n\u0410\u0432\u0442\u043e\u0440\u044b \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438: \u0411\u044b\u0437\u043e\u0432\u0430 \u041c\u0430\u0440\u0438\u044f, \u0412\u0435\u0440\u043d\u0438\u043a\u043e\u0432\u0441\u043a\u0430\u044f \u0415\u043a\u0430\u0442\u0435\u0440\u0438\u043d\u0430, \u041e\u043b\u044c\u0433\u0430 \u041a\u0430\u043b\u0430\u0448\u043d\u0438\u043a\u043e\u0432\u0430. \n\nGitHub \u0411\u044b\u0437\u043e\u0432\u043e\u0439 \u041c\u0430\u0440\u0438\u0438: [link](https://github.com/mobyzova)\n\nGitHub \u0412\u0435\u0440\u043d\u0438\u043a\u043e\u0432\u0441\u043a\u043e\u0439 \u0415\u043a\u0430\u0442\u0435\u0440\u0438\u043d\u044b: [link](https://github.com/Katerok27153)\n\nGitHub \u041a\u0430\u043b\u0430\u0448\u043d\u0438\u043a\u043e\u0432\u043e\u0439 \u041e\u043b\u044c\u0433\u0438: [link](https://github.com/lacrimell)\n",
"bugtrack_url": null,
"license": null,
"summary": "Library for graphs.",
"version": "1.0.1",
"project_urls": {
"GitHub": "https://github.com/Katerok27153/allforgraphs.git",
"Homepage": "https://github.com/Katerok27153/allforgraphs.git"
},
"split_keywords": [
"files",
"speedfiles"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "428a0b85a34d44ab6ee93a39cee84c4910a9475c9bb84be543ed08d32d1f5236",
"md5": "74ca8d18b38b911c272c0ea7bf1df06f",
"sha256": "2a35feed4cd0643fba418d9d3744c2adef596623a65692bae7a9ae3693df627b"
},
"downloads": -1,
"filename": "allforgraphs-1.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "74ca8d18b38b911c272c0ea7bf1df06f",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6",
"size": 18377,
"upload_time": "2024-12-19T17:38:28",
"upload_time_iso_8601": "2024-12-19T17:38:28.084132Z",
"url": "https://files.pythonhosted.org/packages/42/8a/0b85a34d44ab6ee93a39cee84c4910a9475c9bb84be543ed08d32d1f5236/allforgraphs-1.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a5195ba348df1add27f5fe308855632dbf0843a18dbeb911c5e9aed5d82f34e3",
"md5": "d855f269bdf1315b449c7cb6d2d53f05",
"sha256": "f9310885b96183a9df27d6aee7ca0aa015d4e18d91e8d577f47849454af8f044"
},
"downloads": -1,
"filename": "allforgraphs-1.0.1.tar.gz",
"has_sig": false,
"md5_digest": "d855f269bdf1315b449c7cb6d2d53f05",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 17499,
"upload_time": "2024-12-19T17:38:29",
"upload_time_iso_8601": "2024-12-19T17:38:29.569686Z",
"url": "https://files.pythonhosted.org/packages/a5/19/5ba348df1add27f5fe308855632dbf0843a18dbeb911c5e9aed5d82f34e3/allforgraphs-1.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-12-19 17:38:29",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Katerok27153",
"github_project": "allforgraphs",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "allforgraphs"
}
JSON
