SciPy CSGraph 图结构

CSGraph 代表Compressed Sparse Graph，专注于基于稀疏矩阵表示的快速图算法。

图结构是算法学中最强大的框架之一。

图是各种关系的节点和边的集合，节点是与对象对应的顶点，边是对象之间的连接。

SciPy 提供了 scipy.sparse.csgraph 模块来处理图结构。

图表示

首先，让我们了解什么是稀疏图以及它如何表示图结构。

什么是稀疏图？

图只是节点的集合，节点之间有链接。图几乎可以代表任何事物——社交网络连接，其中每个节点都是一个人与熟人相连；图像，其中每个节点是一个像素并与相邻像素相连；高维分布中的点，其中每个节点都与其最近的邻居相连；几乎任何你能想象到的东西都可以用图表示。

表示图形数据的一种非常有效的方法是在稀疏矩阵中：让我们称其为 G。矩阵 G 的大小为 N x N，并且 G[i, j] 给出了节点 'i' 和节点之间的连接值'j'。稀疏图主要包含零——也就是说，大多数节点只有几个连接。

稀疏图子模块的创建是由 scikit-learn 中使用的几种算法推动的，其中包括以下内容 -

• Isomap - 一种流形学习算法，需要在图中找到最短路径。
• 分层聚类- 基于最小生成树的聚类算法。
• Spectral Decomposition - 基于稀疏图拉普拉斯算子的投影算法。

想象一下我们想要表示以下无向图

该图具有三个节点，其中节点 0 和 1 由权重为 2 的边连接，节点 0 和 2 由权重为 1 的边连接。 我们可以构建密集、屏蔽和稀疏的图形表示，如下例所示。请记住，无向图由对称矩阵表示。

import numpy as np
from scipy.sparse import csr_matrix

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

G_masked = np.ma.masked_values(G_dense, 0)

G_sparse = csr_matrix(G_dense)
print(G_sparse.data)

上述代码执行结果如下

[2 1 2 1]

这与之前的图相同，除了节点 0 和 2 由零权重的边连接。在这种情况下，上面的密集表示会导致歧义——如果零是一个有意义的值，如何表示非边缘。在这种情况下，必须使用掩码或稀疏表示来消除歧义。

让我们看以下示例。

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense

G2_data = np.array([
    [np.inf, 2, 0],
    [2, np.inf, np.inf],
    [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print(G2_sparse.data)

运行示例

上述代码执行结果如下

[2. 0. 2. 0.]

邻接矩阵

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。

邻接矩阵逻辑结构分为两部分：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))

Dijkstra -- 最短路径算法

Dijkstra(迪杰斯特拉)最短路径算法，用于计算一个节点到其他所有节点的最短路径。

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))

Bellman Ford -- 贝尔曼-福特算法

贝尔曼-福特算法是解决任意两点间的最短路径的一种算法。

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))