Подпрограммы сжатого разреженного графа (scipy.sparse.csgraph)#
Быстрые алгоритмы для графов на основе разреженных матричных представлений.
Содержание#
|
Анализировать связные компоненты разреженного графа |
|
Вернуть лапласиан ориентированного графа. |
|
Выполнить поиск кратчайшего пути в графе на положительном ориентированном или неориентированном графе. |
|
Алгоритм Дейкстры с использованием очереди с приоритетом |
|
Вычислить длины кратчайших путей с использованием алгоритма Флойда-Уоршелла |
|
Вычислить длины кратчайших путей с использованием алгоритма Беллмана-Форда. |
|
Вычислить длины кратчайших путей с использованием алгоритма Джонсона. |
|
Алгоритм К-кратчайших путей Йена на ориентированном или неориентированном графе. |
|
Вернуть порядок обхода в ширину, начиная с указанного узла. |
|
Возвращает упорядочивание в глубину, начиная с указанного узла. |
|
Возвращает дерево, сгенерированное поиском в ширину |
|
Вернуть дерево, сгенерированное поиском в глубину. |
|
Возвращает минимальное остовное дерево неориентированного графа |
|
Возвращает массив перестановок, который упорядочивает разреженную матрицу CSR или CSC в порядке Reverse-Cuthill McKee. |
|
Максимизировать поток между двумя вершинами в графе. |
|
Возвращает паросочетание двудольного графа, мощность которого не меньше, чем у любого заданного паросочетания графа. |
|
Возвращает минимальное весовое полное соответствие двудольного графа. |
|
Вычислите структурный ранг графа (матрицы) с заданным шаблоном разреженности. |
|
|
Построить матрицу расстояний из матрицы предшественников |
|
Построить разреженный граф в формате CSR из плотной матрицы. |
|
Построить граф в формате CSR из маскированного массива. |
|
Построение представления графа в виде маскированного массива из плотной матрицы. |
|
Преобразовать разреженное представление графа в плотное представление |
|
Преобразовать разреженное представление графа в представление маскированного массива |
|
Построить дерево из графа и списка предшественников. |
Представления графов#
Этот модуль использует графы, хранящиеся в матричном формате. Граф с N узлами может быть представлен матрицей смежности G размером (N x N). Если есть соединение от узла i к узлу j, то G[i, j] = w, где w — вес соединения. Для узлов i и j, которые не соединены, значение зависит от представления:
: ENH: Улучшить путь FIR для signal.decimate
для плотных маскированных представлений (типа np.ma.MaskedArray), не-рёбра представлены маскированными значениями. Это может быть полезно, когда требуются графы с рёбрами нулевого веса.
для разреженных представлений массивов, не-рёбра представлены не-записями в матрице. Такой тип разреженного представления также позволяет использовать рёбра с нулевым весом.
В качестве конкретного примера представьте, что вы хотите описать следующий неориентированный граф:
G
(0)
/ \
1 2
/ \
(2) (1)
Этот граф имеет три узла, где узлы 0 и 1 соединены ребром веса 2, а узлы 0 и 2 соединены ребром веса 1. Мы можем построить плотное, маскированное и разреженное представления следующим образом, помня, что неориентированный граф представлен симметричной матрицей:
>>> import numpy as np
>>> G_dense = np.array([[0, 2, 1],
... [2, 0, 0],
... [1, 0, 0]])
>>> G_masked = np.ma.masked_values(G_dense, 0)
>>> from scipy.sparse import csr_array
>>> G_sparse = csr_array(G_dense)
Это становится сложнее, когда нулевые рёбра значимы. Например, рассмотрим ситуацию, когда мы слегка изменяем приведённый выше граф:
G2
(0)
/ \
0 2
/ \
(2) (1)
Это идентично предыдущему графу, за исключением того, что узлы 0 и 2 соединены ребром нулевого веса. В этом случае плотное представление выше приводит к неоднозначностям: как могут быть представлены не-ребра, если ноль является значимым значением? В этом случае должно использоваться либо маскированное, либо разреженное представление, чтобы устранить неоднозначность:
>>> import numpy as np
>>> G2_data = np.array([[np.inf, 2, 0 ],
... [2, np.inf, np.inf],
... [0, np.inf, np.inf]])
>>> G2_masked = np.ma.masked_invalid(G2_data)
>>> from scipy.sparse.csgraph import csgraph_from_dense
>>> # G2_sparse = csr_array(G2_data) would give the wrong result
>>> G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
>>> G2_sparse.data
array([ 2., 0., 2., 0.])
Здесь мы использовали служебную процедуру из подмодуля csgraph, чтобы преобразовать плотное представление в разреженное, которое может быть понято алгоритмами в подмодуле. Просматривая массив данных, мы можем видеть, что нулевые значения явно закодированы в графе.
Ориентированный vs. неориентированный#
Матрицы могут представлять ориентированные или неориентированные графы. Это указывается во всем модуле csgraph логическим ключевым словом. Графы по умолчанию предполагаются ориентированными. В ориентированном графе переход от узла i к узлу j может быть выполнен по ребру G[i, j], но не по ребру G[j, i]. Рассмотрим следующий плотный граф:
>>> import numpy as np
>>> G_dense = np.array([[0, 1, 0],
... [2, 0, 3],
... [0, 4, 0]])
Когда directed=True мы получаем график:
---1--> ---3-->
(0) (1) (2)
<--2--- <--4---
В ненаправленном графе переход от узла i к узлу j может быть выполнен по G[i, j] или G[j, i]. Если оба ребра не нулевые и имеют неравные веса, то используется меньший из двух.
Таким образом, для того же графа, когда directed=False мы получаем график:
(0)--1--(1)--3--(2)
Обратите внимание, что симметричная матрица будет представлять неориентированный граф, независимо от того, установлен ли параметр 'directed' в True или False. В этом случае использование directed=True обычно приводит к более эффективным вычислениям.
Подпрограммы в этом модуле принимают на вход либо представления scipy.sparse (форматы csr, csc или lil), либо маскированные представления, либо плотные представления с не-рёбрами, обозначенными нулями, бесконечностями и записями NaN.