# Scipy CSGraph

CSGraph表示壓縮稀疏圖，它著重於基於稀疏矩陣表示快速圖演算法。

## 圖表示

`scikit-learn`中使用的幾種演算法激發了稀疏圖子模組的建立，其中包括以下內容 -

• Isomap - 流形學習演算法，需要在圖中找到最短路徑。
• 分層聚類 - 基於最小生成樹的聚類演算法。
• 譜分解 - 基於稀疏圖拉普拉斯運算元的投影演算法。

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

from scipy.sparse import csr_matrix

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

``````array([2, 1, 2, 1])
``````

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

``````array([ 2., 0., 2., 0.])
``````

APE → APT → AIT → BIT → BIG → BAG → MAG → MAN

## 獲取單詞列表

``````wordlist = open('/usr/share/dict/words').read().split()
print (len(wordlist))
``````

``````205882
``````

``````word_list = [word for word in word_list if len(word) == 3]
word_list = [word for word in word_list if word[0].islower()]
word_list = [word for word in word_list if word.isalpha()]
word_list = map(str.lower, word_list)
print (len(word_list))
``````

``````1185
``````

``````import numpy as np
word_list = np.asarray(word_list)

word_list.dtype
word_list.sort()

word_bytes = np.ndarray((word_list.size, word_list.itemsize),
dtype = 'int8',
buffer = word_list.data)
print (word_bytes.shape)
``````

``````(1185,3)
``````

``````from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
hamming_dist = pdist(word_bytes, metric = 'hamming')
graph = csr_matrix(squareform(hamming_dist < 1.5 / word_list.itemsize))
``````

``````
i1 = word_list.searchsorted('ape')
i2 = word_list.searchsorted('man')
print (word_list[i1],word_list[i2])
``````

``````ape, man
``````

``````from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
print (distances[i2])
``````

``````5.0
``````

``````path = []
i = i2

while i != i1:
path.append(word_list[i])
i = predecessors[i]

path.append(word_list[i1])
print (path[::-1]i2])
``````

``````['ape', 'ope', 'opt', 'oat', 'mat', 'man']
``````