scipy.sparse.csgraph.

csgraph_to_dense#

scipy.sparse.csgraph.csgraph_to_dense(csgraph, null_value=0)#

Преобразовать разреженное представление графа в плотное представление

Добавлено в версии 0.11.0.

Параметры:

csgraphcsr_array, csc_array или lil_array: Разреженное представление графа.
null_valuefloat, опционально: Значение, используемое для обозначения нулевых рёбер в плотном представлении. По умолчанию 0.

Возвращает:

графndarray: Плотное представление разреженного графа.

Примечания

Для обычных разреженных представлений графов вызов csgraph_to_dense с null_value=0 дает эквивалентный результат использованию преобразований в плотном формате в основном пакете sparse. Однако, когда разреженные представления имеют повторяющиеся значения, результаты будут отличаться. Инструменты в scipy.sparse будут складывать повторяющиеся значения для получения итогового значения. Эта функция выберет минимальное среди повторяющихся значений для получения итогового значения. Например, здесь мы создадим направленный разреженный граф с двумя узлами и несколькими ребрами от узла 0 к узлу 1 с весами 2 и 3. Это иллюстрирует разницу в поведении:

>>> from scipy.sparse import csr_array, csgraph
>>> import numpy as np
>>> data = np.array([2, 3])
>>> indices = np.array([1, 1])
>>> indptr = np.array([0, 2, 2])
>>> M = csr_array((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0, 5],
       [0, 0]])
>>> csgraph.csgraph_to_dense(M)
array([[0., 2.],
       [0., 0.]])

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

Другая причина использования этой процедуры — возможность работы с графами, имеющими рёбра нулевого веса. Рассмотрим пример направленного графа с двумя узлами, соединённых ребром веса ноль:

>>> from scipy.sparse import csr_array, csgraph
>>> data = np.array([0.0])
>>> indices = np.array([1])
>>> indptr = np.array([0, 1, 1])
>>> M = csr_array((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0., 0.],
       [0., 0.]])
>>> csgraph.csgraph_to_dense(M, np.inf)
array([[inf,  0.],
       [inf, inf]])

В первом случае ребро с нулевым весом теряется в плотном представлении. Во втором случае мы можем выбрать другое нулевое значение и увидеть истинную форму графа.

Примеры

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import csgraph_to_dense

>>> graph = csr_array( [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ])
>>> graph

    with 4 stored elements and shape (4, 4)>

>>> csgraph_to_dense(graph)
array([[0., 1., 2., 0.],
       [0., 0., 0., 1.],
       [0., 0., 0., 3.],
       [0., 0., 0., 0.]])