Задания

Выполнила Ахманова Элина

Граф

graph.py

tests_graph.py

Реализовать класс для работы с графом. 
Требования:
* Конструкторы (не менее 3-х)
* Методы: добавляющие вершину, добавляющие ребро (дугу), удаляющие вершину,удаляющие ребро (дугу)
* Должны поддерживаться как ориентированные, так и неориентированные графы. Заранее предусмотрите возможность \
 добавления меток и\или весов для дуг. Поддержка мультиграфа не требуется.

Работа с графом: список смежности

galgo.py

tests_galgo.py

Список смежности Ia

1. Для каждой вершины графа подсчитать её степень.

Список смежности Iб: несколько графов

1. Вывести список смежности графа, являющегося дополнением данного графа.

Обходы графа

Обходы графа II

20. Проверить, является ли граф деревом, или лесом, или не является ни тем ни другим.
21. Проверить, можно ли из графа удалить какую-либо вершину так, чтобы получилось дерево.

Построение минимального остовного дерева

Каркас III

Прим

Взвешенный граф

Веса IV а (Дейкстра)

17. Вывести кратчайшие пути для всех пар вершин.

Веса IV b (Форд-Беллман, Флойд)

22. Найти k кратчайших путей между вершинами u и v.

Веса IV с (Форд-Беллман, Флойд)

8. Определить множество вершин орграфа, расстояние от которых до заданной вершины не более N.

Потоки

Алгоритм Форда-Фаркенсона

Нахлждение наибольшего возможного потока

Творческое задание

Для творческого задания была выбрана прикладная задача: 
В сервисе для автоматизации работы (Jenkins) восстановить путь до процесса, \
 который может находиться в разных директориях. 
Для выполнения задания использовалась локальная версия Jenkins в контейнере Docker.
Jenkins имеет реализацию Jenkins API -- REST сервиса. Чтобы получить, например, директории первого уровня вложения, \
напишем:

http://127.0.0.1:8080/job/test_prod/job/test_prod_serv_1/job/test_prod_serv_2/api/json

Получим json-файл. Построим по нему обратный граф и создадим методы:
* get_all_paths - получить все пути к процессам
* get_cur_path  - получить путь до конкретного процесса