Структура графа SciPy

Структура графов — одна из самых мощных концепций в алгоритмике.

Граф — это совокупность узлов и рёбер различных отношений. Узлы — это вершины, соответствующие объектам, а рёбра — это связи между объектами.

SciPy предоставляет модуль scipy.sparse.csgraph для работы со структурами графов.

Матрица смежности

Матрица смежности — это матрица, которая представляет отношения смежности между вершинами.

Логическая структура матрицы смежности делится на две части: множества V и E, где V — вершины, E — рёбра. Рёбра иногда имеют веса, представляющие силу связи между узлами.

Одномерный массив используется для хранения всех данных о вершинах графа, а двумерный массив используется для хранения данных о связях между вершинами (рёбрах или дугах). Этот двумерный массив называется матрицей смежности.

Посмотрите на следующий пример:

Вершины — это A, B, C, а веса рёбер — 1 и 2.

A и B соединены с весом 1.

A и C соединены с весом 2.

C и B не соединены.

Эта матрица смежности может быть представлена в виде следующего двумерного массива:
     A B C
   A:[0 1 2]  
   B:[1 0 0]
   C:[2 0 0]

Матрицы смежности дополнительно делятся на матрицы смежности ориентированных графов и матрицы смежности неориентированных графов.

Неориентированный граф — это двунаправленная связь, и рёбра не имеют направления:

Рёбра ориентированного графа имеют направление и являются однонаправленными связями:

Примечание:Узел D на двух рисунках выше является петлёй. Петля означает, что оба конца ребра — один и тот же узел.

Связные компоненты

Используйте метод connected_components() для просмотра всех связных компонентов.

Пример

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(connected_components(newarr))

Вывод вышеприведённого кода:

(1, array([0, 0, 0], dtype=int32))

Дейкстра -- алгоритм кратчайшего пути

Алгоритм кратчайшего пути Дейкстры используется для вычисления кратчайших путей от одного узла до всех остальных узлов.

SciPy использует метод dijkstra() для вычисления кратчайшего пути от одного элемента к другим элементам.

Метод dijkstra() может задавать следующие параметры:
  1. return_predecessors:Логическое значение. Установите True, чтобы обойти все пути; если вы не хотите обходить все пути, установите False.
  2. indices:Индекс элемента; возвращает все пути от этого элемента.
  3. limit:Максимальный вес путей.

Пример

Найти кратчайший путь из элемента 1 в элемент 2:

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(dijkstra(newarr, return_predecessors=True, indices=0))

Вывод вышеприведённого кода:

(array([ 0.,  1.,  2.]), array([-9999,     0,     0], dtype=int32))

Floyd Warshall -- алгоритм Флойда

Алгоритм Флойда — это алгоритм поиска кратчайшего пути между любыми двумя точками.

SciPy использует метод floyd_warshall() для поиска кратчайшего пути между всеми парами элементов.

Пример

Найти кратчайшие пути между всеми парами элементов:

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(floyd_warshall(newarr, return_predecessors=True))

Вывод вышеприведённого кода:

(array([[ 0.,  1.,  2.],
       [ 1.,  0.,  3.],
       [ 2.,  3.,  0.]]), array([[-9999,     0,     0],
       [    1, -9999,     0],
       [    2,     0, -9999]], dtype=int32))

Беллман-Форд -- алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда — это алгоритм решения задачи о кратчайшем пути между любыми двумя точками.

SciPy использует метод bellman_ford() для нахождения кратчайшего пути между всеми парами элементов. Обычно его можно использовать в любом графе, включая ориентированные графы и графы с рёбрами отрицательного веса.

Пример

Используйте граф с рёбрами отрицательного веса, чтобы найти кратчайший путь из элемента 1 в элемент 2:

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, -1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

Вывод вышеприведённого кода:

(array([ 0., -1.,  2.]), array([-9999,     0,     0], dtype=int32))

Порядок обхода в глубину

Метод depth_first_order() возвращает порядок обхода в глубину от узла.

Он может принимать следующие параметры:

  • Граф
  • Элемент, с которого начинается обход графа

Пример

Для данной матрицы смежности вернуть порядок обхода в глубину:

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

Вывод вышеприведённого кода:

(array([1, 0, 3, 2], dtype=int32), array([    1, -9999,     1,     0], dtype=int32))

Порядок обхода в ширину

Метод breadth_first_order() возвращает порядок обхода в ширину от узла.

Он может принимать следующие параметры:

  • Граф
  • Элемент, с которого начинается обход графа

Пример

По заданной матрице смежности вернуть порядок обхода в ширину:

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))

Вывод вышеприведённого кода:

(array([1, 0, 2, 3], dtype=int32), array([    1, -9999,     1,     1], dtype=int32))
Другие расширения