Плотная случайная матрица для (un) направленного графа как разреженная матрица?

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)] (node1, node2, стоимостью) + все путей, идущих в другом направлении.

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

Другие сведения: Я использую Python и NumPy.

Answer 1

Вот код ноутбука ipython для вычисления краев задачи Project Euler 83. Вместо 2D-координат я использую индекс для каждого элемента в матрице.

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

Затем вы можете конвертировать edges в разреженной матрице scipy.sparse.coo_matrix