dijkstra-for-robots 1.0.3

Система навигации робота по глобальной карте.

Библиотека для работы с графами

Этот код представляет собой класс для работы с графами, использующий библиотеки NetworkX и Matplotlib. Он позволяет создавать графы на основе координат вершин и связей между ними, вычислять расстояния между вершинами, находить кратчайший путь между двумя заданными вершинами с помощью алгоритма Дейкстры и отрисовывать графы с учетом кратчайшего пути.

Установка

Для работы с этим кодом вам нужно установить Python 3 и следующие библиотеки:

• NetworkX: pip install networkx
• Matplotlib: pip install matplotlib

p.s. вы также можете установить все сразу - pip install dijkstra-for-robots, если вы это сделаете, можете переходить к концу

Использование

Для использования этого кода вам нужно импортировать класс Graph из файла main.py:

from main import Graph

Затем вам нужно создать объект класса Graph, передав ему координаты вершин и связи между ними в виде списков кортежей:

coordinates = [
    (1, 1.5),
    (4, 1.5), (15, 1.5),
    (15, 6.5), (12, 6.5),
    (8, 6.5), (4, 6.5),
    (1, 6.5), (1, 16),
    (6, 16), (7, 13),
    (9, 13), (12, 14),
    (16, 14), (16, 18),
    (12, 18), (9, 18),
    (9, 19.5), (8, 19.5),
    (8, 22), (6, 20),
    (4, 20), (4, 22),
    (10, 22), (10, 24),
    (16, 24), (15, 24)
]

connections = {
    (1, 1.5): [(4, 1.5)],
    (4, 1.5): [(15, 1.5), (4, 6.5)],
    (15, 1.5): [(15, 6.5)],
    (15, 6.5): [(12, 6.5)],
    (12, 6.5): [(8, 6.5)],
    (8, 6.5): [(7, 13), (4, 6.5), (9, 13)],
    (7, 13): [(9, 13)],
    (9, 13): [(9, 18)],
    (9, 18): [(9, 19.5), (12, 18)],
    (9, 19.5): [(8, 19.5)],
    (8, 19.5): [(8, 22)],
    (8, 22): [(10, 22)],
    (10, 22): [(10, 24)],
    (10, 24): [(15, 24)],
    (12, 18): [(16, 18)],
    (16, 18): [(16, 24)],
    (16, 24): [(15, 24)],
    (7, 13): [(6, 16)],
    (6, 16): [(6, 20)],
    (6, 20): [(4, 20)],
    (4, 20): [(4, 22)],
    (4, 22): [(8, 22)],
    (4, 6.5): [(1, 6.5)],
    (1, 6.5): [(1, 16)],
    (1, 16): [(6, 16)],
    (12, 14): [(16, 14), (12, 18)],
    (16, 14): [(16, 18)],
}
graph = Graph(coordinates, connections)

Для нахождения кратчайшего пути между двумя вершинами, вам нужно вызвать метод dijkstra_algorithm, передав ему координаты начальной и конечной вершины. Этот метод вернет список координат, составляющих кратчайший путь, и выведет его длину и последовательность на экран.

shortest_path = graph.dijkstra_algorithm((1, 1.5), (15, 24))

Для отрисовки графа с учетом кратчайшего пути, вам нужно вызвать метод draw_graph, передав ему список координат кратчайшего пути. Этот метод создаст графическое окно, в котором вы увидите граф с метками вершин и ребер, а также выделенный кратчайший путь.

graph.draw_graph(shortest_path)

Вы также можете использовать другие методы класса Graph, такие как:

• get_distances: возвращает список расстояний между всеми вершинами в графе.
• get_nodes: возвращает список всех вершин графа.
• get_outgoing_edges: возвращает список вершин, с которыми у заданной вершины есть связь.
• value: возвращает длину между двумя вершинами.
• calculate_distance: вычисляет расстояние между двумя координатами точек.

Пример

Вот пример использования этого кода для создания и отрисовки графа, а также нахождения кратчайшего пути между двумя вершинами:

"""Пример использования"""
# импорт самого класса
from main import Graph
# сами координаты
coordinates = [
    (1, 1.5),
    (4, 1.5), (15, 1.5),
    (15, 6.5), (12, 6.5),
    (8, 6.5), (4, 6.5),
    (1, 6.5), (1, 16),
    (6, 16), (7, 13),
    (9, 13), (12, 14),
    (16, 14), (16, 18),
    (12, 18), (9, 18),
    (9, 19.5), (8, 19.5),
    (8, 22), (6, 20),
    (4, 20), (4, 22),
    (10, 22), (10, 24),
    (16, 24), (15, 24)
]

# пути куда можно пойти
connections = {
    (1, 1.5): [(4, 1.5)],
    (4, 1.5): [(15, 1.5), (4, 6.5)],
    (15, 1.5): [(15, 6.5)],
    (15, 6.5): [(12, 6.5)],
    (12, 6.5): [(8, 6.5)],
    (8, 6.5): [(7, 13), (4, 6.5), (9, 13)],
    (7, 13): [(9, 13)],
    (9, 13): [(9, 18)],
    (9, 18): [(9, 19.5), (12, 18)],
    (9, 19.5): [(8, 19.5)],
    (8, 19.5): [(8, 22)],
    (8, 22): [(10, 22)],
    (10, 22): [(10, 24)],
    (10, 24): [(15, 24)],
    (12, 18): [(16, 18)],
    (16, 18): [(16, 24)],
    (16, 24): [(15, 24)],
    (7, 13): [(6, 16)],
    (6, 16): [(6, 20)],
    (6, 20): [(4, 20)],
    (4, 20): [(4, 22)],
    (4, 22): [(8, 22)],
    (4, 6.5): [(1, 6.5)],
    (1, 6.5): [(1, 16)],
    (1, 16): [(6, 16)],
    (12, 14): [(16, 14), (12, 18)],
    (16, 14): [(16, 18)],
}

# вызываются методы для нахождения кратчайшего пути и отрисовки графа с этим путем.
graph = Graph(coordinates, connections)
shortest_path = graph.dijkstra_algorithm((1, 1.5), (15, 24))
graph.draw_graph(shortest_path)
print(graph.value((1, 1.5), (4, 1.5)))
print(graph.get_nodes())
print(graph.construct_graph())