Metadata-Version: 2.1
Name: KruskalHamiltonPrimal
Version: 0.0.1
Summary: Библиотека для работы с графами и алгоритмами, включая алгоритмы Крускала, Гамильтона и минимального остовного дерева
Home-page: https://github.com/Ksenia72/graph_algorithms
Author: Prosina_Chetvergova_Toychubecova
Author-email: prosinaksenia@gmail.com
Project-URL: GitHub, https://github.com/Ksenia72
Keywords: графы алгоритмы Крускала Краскала Гамильтона минимальное остовное дерево
Classifier: Programming Language :: Python :: 3.11
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.6
Description-Content-Type: text/markdown
Requires-Dist: matplotlib==3.9.2
Requires-Dist: networkx==3.4.2

# РњРёРЅРёРјР°Р»СЊРЅРѕРµ РћСЃС‚РѕРІРЅРѕРµ Р”РµСЂРµРІРѕ Рё Р“Р°РјРёР»СЊС‚РѕРЅРѕРІ Р¦РёРєР»

Р­С‚РѕС‚ РїСЂРѕРµРєС‚ СЂРµР°Р»РёР·СѓРµС‚ Р°Р»РіРѕСЂРёС‚РјС‹ РґР»СЏ РЅР°С…РѕР¶РґРµРЅРёСЏ РјРёРЅРёРјР°Р»СЊРЅРѕРіРѕ РѕСЃС‚РѕРІРЅРѕРіРѕ РґРµСЂРµРІР° (MST) Рё Р“Р°РјРёР»СЊС‚РѕРЅРѕРІР° С†РёРєР»Р° РІ РіСЂР°С„Р°С…. РћРЅ РІРєР»СЋС‡Р°РµС‚ РІ СЃРµР±СЏ С‚СЂРё РѕСЃРЅРѕРІРЅС‹С… РєР»Р°СЃСЃР°: `Kruskal`, `Hamilton` Рё `Primal_min`, РєР°Р¶РґС‹Р№ РёР· РєРѕС‚РѕСЂС‹С… РїСЂРµРґРѕСЃС‚Р°РІР»СЏРµС‚ СЂР°Р·Р»РёС‡РЅС‹Рµ РјРµС‚РѕРґС‹ РґР»СЏ СЂР°Р±РѕС‚С‹ СЃ РіСЂР°С„Р°РјРё.

## РЈСЃС‚Р°РЅРѕРІРєР°

Р”Р»СЏ СЂР°Р±РѕС‚С‹ СЃ РїСЂРѕРµРєС‚РѕРј РЅРµРѕР±С…РѕРґРёРјРѕ СѓСЃС‚Р°РЅРѕРІРёС‚СЊ СЃР»РµРґСѓСЋС‰РёРµ Р±РёР±Р»РёРѕС‚РµРєРё:

```bash
pip install networkx matplotlib
```

## РћРїРёСЃР°РЅРёРµ РєР»Р°СЃСЃРѕРІ

### 1. Kruskal

РљР»Р°СЃСЃ `Kruskal` СЂРµР°Р»РёР·СѓРµС‚ Р°Р»РіРѕСЂРёС‚Рј РљСЂР°СЃРєР°Р»Р° РґР»СЏ РЅР°С…РѕР¶РґРµРЅРёСЏ РјРёРЅРёРјР°Р»СЊРЅРѕРіРѕ РѕСЃС‚РѕРІРЅРѕРіРѕ РґРµСЂРµРІР°.

#### РљРѕРЅСЃС‚СЂСѓРєС‚РѕСЂ

```python
Kruskal(points, edges)
```

- `points`: РЎРїРёСЃРѕРє РєРѕРѕСЂРґРёРЅР°С‚ РІРµСЂС€РёРЅ РіСЂР°С„Р°.
- `edges`: РЎРїРёСЃРѕРє СЂС‘Р±РµСЂ РіСЂР°С„Р°, РіРґРµ РєР°Р¶РґРѕРµ СЂРµР±СЂРѕ РїСЂРµРґСЃС‚Р°РІР»РµРЅРѕ РІ РІРёРґРµ РєРѕСЂС‚РµР¶Р° (u, v, weight).

#### РњРµС‚РѕРґС‹

- `draw_only(k)`: РћС‚РѕР±СЂР°Р¶Р°РµС‚ РіСЂР°С„ Рё РµРіРѕ СЂС‘Р±СЂР°.
- `view(min_edges, max_edges, k)`: РћС‚РѕР±СЂР°Р¶Р°РµС‚ РіСЂР°С„ СЃ РјРёРЅРёРјР°Р»СЊРЅС‹Рј Рё РјР°РєСЃРёРјР°Р»СЊРЅС‹Рј РїРѕРєСЂС‹РІР°СЋС‰РёРј РґРµСЂРµРІРѕРј.
- `kruskals_algorithm(edges)`: Р РµР°Р»РёР·СѓРµС‚ Р°Р»РіРѕСЂРёС‚Рј РљСЂР°СЃРєР°Р»Р° РґР»СЏ РЅР°С…РѕР¶РґРµРЅРёСЏ MST.
- `sort_edges_min()`: РЎРѕСЂС‚РёСЂСѓРµС‚ СЂС‘Р±СЂР° РїРѕ РІРѕР·СЂР°СЃС‚Р°РЅРёСЋ РІРµСЃР°.
- `sort_edges_max()`: РЎРѕСЂС‚РёСЂСѓРµС‚ СЂС‘Р±СЂР° РїРѕ СѓР±С‹РІР°РЅРёСЋ РІРµСЃР°.
- `result_weight(edges)`: Р’С‹С‡РёСЃР»СЏРµС‚ Рё РІС‹РІРѕРґРёС‚ СЃСѓРјРјР°СЂРЅС‹Р№ РІРµСЃ РґРµСЂРµРІР°.

### 2. Hamilton

РљР»Р°СЃСЃ `Hamilton` СЂРµР°Р»РёР·СѓРµС‚ Р°Р»РіРѕСЂРёС‚Рј РґР»СЏ РЅР°С…РѕР¶РґРµРЅРёСЏ Р“Р°РјРёР»СЊС‚РѕРЅРѕРІР° С†РёРєР»Р°.

#### РљРѕРЅСЃС‚СЂСѓРєС‚РѕСЂ

```python
Hamilton(points, edges)
```

- `points`: РЎРїРёСЃРѕРє РєРѕРѕСЂРґРёРЅР°С‚ РІРµСЂС€РёРЅ РіСЂР°С„Р°.
- `edges`: РЎРїРёСЃРѕРє СЂС‘Р±РµСЂ РіСЂР°С„Р° РІ РІРёРґРµ РїР°СЂ РёРЅРґРµРєСЃРѕРІ РІРµСЂС€РёРЅ.

#### РњРµС‚РѕРґС‹

- `cycle_exist(cycle)`: РџСЂРѕРІРµСЂСЏРµС‚ РЅР°Р»РёС‡РёРµ Р“Р°РјРёР»СЊС‚РѕРЅРѕРІР° С†РёРєР»Р° Рё РІС‹РІРѕРґРёС‚ РµРіРѕ.
- `draw()`: Р’РёР·СѓР°Р»РёР·РёСЂСѓРµС‚ РіСЂР°С„.
- `aviable()`: Р’С‹РІРѕРґРёС‚ РґРѕСЃС‚СѓРїРЅС‹Рµ РІРµСЂС€РёРЅС‹.
- `hamiltonian_cycle(start)`: РќР°С…РѕРґРёС‚ Р“Р°РјРёР»СЊС‚РѕРЅРѕРІ С†РёРєР», РЅР°С‡РёРЅР°СЏ СЃ Р·Р°РґР°РЅРЅРѕР№ РІРµСЂС€РёРЅС‹.
- `draw_graph(path=None)`: РћС‚РѕР±СЂР°Р¶Р°РµС‚ РіСЂР°С„ СЃ РІС‹РґРµР»РµРЅРЅС‹Рј Р“Р°РјРёР»СЊС‚РѕРЅРѕРІС‹Рј С†РёРєР»РѕРј.

### 3. Primal_min

РљР»Р°СЃСЃ `Primal_min` СЂРµР°Р»РёР·СѓРµС‚ Р°Р»РіРѕСЂРёС‚Рј РџСЂРёРјР° РґР»СЏ РЅР°С…РѕР¶РґРµРЅРёСЏ РјРёРЅРёРјР°Р»СЊРЅРѕРіРѕ РѕСЃС‚РѕРІРЅРѕРіРѕ РґРµСЂРµРІР°.

#### РљРѕРЅСЃС‚СЂСѓРєС‚РѕСЂ

```python
Primal_min(graph)
```

- `graph`: Р“СЂР°С„ РІ РІРёРґРµ СЃР»РѕРІР°СЂСЏ, РіРґРµ РєР»СЋС‡Рё вЂ” СЌС‚Рѕ РІРµСЂС€РёРЅС‹, Р° Р·РЅР°С‡РµРЅРёСЏ вЂ” СЃРїРёСЃРєРё СЂС‘Р±РµСЂ СЃ РІРµСЃР°РјРё.

#### РњРµС‚РѕРґС‹

- `run(begin)`: Р—Р°РїСѓСЃРєР°РµС‚ Р°Р»РіРѕСЂРёС‚Рј РџСЂРёРјР°, РЅР°С‡РёРЅР°СЏ СЃ Р·Р°РґР°РЅРЅРѕР№ РІРµСЂС€РёРЅС‹.
- `min_tree()`: Р’С‹РІРѕРґРёС‚ РјРёРЅРёРјР°Р»СЊРЅРѕРµ РїРѕРєСЂС‹РІР°СЋС‰РµРµ РґРµСЂРµРІРѕ Рё РµРіРѕ СЃСѓРјРјР°СЂРЅС‹Р№ РІРµСЃ.

## РџСЂРёРјРµСЂ РёСЃРїРѕР»СЊР·РѕРІР°РЅРёСЏ

```python
# РџСЂРёРјРµСЂ СЃРѕР·РґР°РЅРёСЏ РіСЂР°С„Р° Рё РЅР°С…РѕР¶РґРµРЅРёСЏ РјРёРЅРёРјР°Р»СЊРЅРѕРіРѕ РѕСЃС‚РѕРІРЅРѕРіРѕ РґРµСЂРµРІР°
points = [(0, 0), (1, 1), (2, 0), (1, -1)]
edges = [(0, 1, 1.5), (0, 2, 1.0), (1, 3, 2.0), (2, 3, 1.0)]

kruskal = Kruskal(points, edges)
sorted_edges = kruskal.sort_edges_min()
mst = kruskal.alg_Kraskala(sorted_edges)
kruskal.view(mst, sorted_edges, 3)

# РџСЂРёРјРµСЂ РЅР°С…РѕР¶РґРµРЅРёСЏ Р“Р°РјРёР»СЊС‚РѕРЅРѕРІР° С†РёРєР»Р°
hamilton = Hamilton(points, edges)
cycle = hamilton.hamiltonian_cycle(0)
hamilton.cycle_exist(cycle)
hamilton.draw_graph(cycle)
```

## Р›РёС†РµРЅР·РёСЏ

Р­С‚РѕС‚ РїСЂРѕРµРєС‚ Р»РёС†РµРЅР·РёСЂРѕРІР°РЅ РїРѕРґ MIT License. РџРѕР¶Р°Р»СѓР№СЃС‚Р°, РѕР·РЅР°РєРѕРјСЊС‚РµСЃСЊ СЃ С„Р°Р№Р»РѕРј LICENSE РґР»СЏ РїРѕР»СѓС‡РµРЅРёСЏ РґРѕРїРѕР»РЅРёС‚РµР»СЊРЅРѕР№ РёРЅС„РѕСЂРјР°С†РёРё.
```
