密集的隨機矩陣到（非）有向圖作爲稀疏矩陣？

Question

我想研究一些「最大流量」問題來理解算法，但是我認爲什麼是測試它們的簡單設置的概念很難實現。

看看這個項目歐拉問題：http://projecteuler.net/problem=83

我想要做的是假設每個連接到所有鄰近小區（「+」模式）的那些細胞，然後創建之間的路徑是什麼每對成本==到最大值的兩人即之間：max(cell1, cell2）

因此，一個簡單[[s 4],[3 t]]矩陣將成爲[(s, (0,1), 4), (s, (1,0), 3), ((0,1), t, 3), ((1,0), 4, t)]（節點，節點2，成本）+所有在其他方向去的路徑。

也許有一個更簡單的方式來描述我正在嘗試做什麼，但我會很感激任何幫助。

其他詳細信息：我正在使用Python和NumPy。

Answer 1

這裏是ipython筆記本代碼來計算項目歐拉問題83的邊緣。代替二維座標，我使用矩陣中的每個元素的索引。

In [1]: 

#load the data 
import numpy as np 
from StringIO import StringIO 
data = StringIO("""131 673 234 103 18 
201 96 342 965 150 
630 803 746 422 111 
537 699 497 121 956 
805 732 524 37 331""") 
m = np.loadtxt(data, dtype=int) 
m 

Out[1]: 

array([[131, 673, 234, 103, 18], 
     [201, 96, 342, 965, 150], 
     [630, 803, 746, 422, 111], 
     [537, 699, 497, 121, 956], 
     [805, 732, 524, 37, 331]]) 

In [2]: 

# give every element an index 
idx = np.arange(m.size).reshape(m.shape) 
idx 

Out[2]: 

array([[ 0, 1, 2, 3, 4], 
     [ 5, 6, 7, 8, 9], 
     [10, 11, 12, 13, 14], 
     [15, 16, 17, 18, 19], 
     [20, 21, 22, 23, 24]]) 

In [3]: 

# create edges 
left_edges = np.concatenate([idx[:, :-1, None], idx[:, 1:, None], m[:, 1:, None]], axis=2).reshape(-1, 3) 
right_edges = np.concatenate([idx[:, 1:, None], idx[:, :-1, None], m[:, :-1, None]], axis=2).reshape(-1, 3) 
down_edges = np.concatenate([idx[:-1, :, None], idx[1:, :, None], m[1:, :, None]], axis=2).reshape(-1, 3) 
up_edges = np.concatenate([idx[1:, :, None], idx[:-1, :, None], m[:-1, :, None]], axis=2).reshape(-1, 3) 
edges = np.vstack((left_edges, right_edges, down_edges, up_edges)) 
edges 

Out[3]: 

array([[ 0, 1, 673], 
     [ 1, 2, 234], 
     [ 2, 3, 103], 
     [ 3, 4, 18], 
     [ 5, 6, 96], 
     [ 6, 7, 342], 
     [ 7, 8, 965], 
     [ 8, 9, 150], 
     [ 10, 11, 803], 
     [ 11, 12, 746], 
     [ 12, 13, 422], 
     [ 13, 14, 111], 
     [ 15, 16, 699], 
     [ 16, 17, 497], 
     [ 17, 18, 121], 
     [ 18, 19, 956], 
     [ 20, 21, 732], 
     [ 21, 22, 524], 
     [ 22, 23, 37], 
     [ 23, 24, 331], 
     [ 1, 0, 131], 
     [ 2, 1, 673], 
     [ 3, 2, 234], 
     [ 4, 3, 103], 
     [ 6, 5, 201], 
     [ 7, 6, 96], 
     [ 8, 7, 342], 
     [ 9, 8, 965], 
     [ 11, 10, 630], 
     [ 12, 11, 803], 
     [ 13, 12, 746], 
     [ 14, 13, 422], 
     [ 16, 15, 537], 
     [ 17, 16, 699], 
     [ 18, 17, 497], 
     [ 19, 18, 121], 
     [ 21, 20, 805], 
     [ 22, 21, 732], 
     [ 23, 22, 524], 
     [ 24, 23, 37], 
     [ 0, 5, 201], 
     [ 1, 6, 96], 
     [ 2, 7, 342], 
     [ 3, 8, 965], 
     [ 4, 9, 150], 
     [ 5, 10, 630], 
     [ 6, 11, 803], 
     [ 7, 12, 746], 
     [ 8, 13, 422], 
     [ 9, 14, 111], 
     [ 10, 15, 537], 
     [ 11, 16, 699], 
     [ 12, 17, 497], 
     [ 13, 18, 121], 
     [ 14, 19, 956], 
     [ 15, 20, 805], 
     [ 16, 21, 732], 
     [ 17, 22, 524], 
     [ 18, 23, 37], 
     [ 19, 24, 331], 
     [ 5, 0, 131], 
     [ 6, 1, 673], 
     [ 7, 2, 234], 
     [ 8, 3, 103], 
     [ 9, 4, 18], 
     [ 10, 5, 201], 
     [ 11, 6, 96], 
     [ 12, 7, 342], 
     [ 13, 8, 965], 
     [ 14, 9, 150], 
     [ 15, 10, 630], 
     [ 16, 11, 803], 
     [ 17, 12, 746], 
     [ 18, 13, 422], 
     [ 19, 14, 111], 
     [ 20, 15, 537], 
     [ 21, 16, 699], 
     [ 22, 17, 497], 
     [ 23, 18, 121], 
     [ 24, 19, 956]]) 

然後你就可以通過scipy.sparse.coo_matrix