通过避免for循环从节点列表构建邻接矩阵 [英] Build adjacency matrix from a list of nodes by avoiding for loops

问题描述

l需要解决什么问题？

从索引列表构建二进制矩阵。 下面是l的处理方式，但l希望找到一种有效的方法来避免循环

输入：

list_indices =[
[0,3,4],
[2,1,0],
[3,5]
]

预期产量：

results=[
[0,1,1,1,1,0],
[1,0,1,0,0,0],
[0,0,0,0,0,0],
[1,0,0,0,1,1],
[1,0,0,1,0,0],
[0,0,1,0,0,0],
]

结果对应于从索引列表构建的二进制邻接(对称)矩阵。结果中的1对应于属于LIST_INDEX同一行的一对索引。

LIST_INDEX中的对为：

row 1 : (0,3), (3,0), (0,4),(4,0), (3,4), (4,3)
row 2 : (0,1), (1,0), (2,0), (0,2),(1,2), (2,1)
row 3 : (3,5), (5,3)


number of column and number of rows in results = np.max(list_indices)+1=6 

l尝试过什么？

results=np.zeros((np.max(list_indices)+1,np.max(list_indices)+1))

for pair in itertools.combinations(list_indices, r=2) :
                      
         results[pair[0],pair[1]]=results[pair[1],pair[0]]=1.0

构建它的有效方法是什么？(避免循环)

itertools.combinations返回一个配对列表，然后使用该列表填充矩阵结果。因为该矩阵是对称的，所以迭代式组合提供了对应于上对角线矩阵的对的列表。对角线设置为零

推荐答案

此问题与我10天前的调查discussed密切相关，因此我将在此处发布最重要发现的摘要。

• 将社区存储为长度不平衡的列表会强制使用迭代或串联，这是低效的。相反，您可以使用单个数组，并按如下方式计算：

      flow = [0,3,4,2,1,0,3,5]
      counts = [3,3,2]
  

• 单一组合的更快方法是np.triu_indices方法，而不是itertools.combinations：

  def combs(t):
       x, y = np.triu_indices(len(t), 1)
       return np.transpose([t[x], t[y]])
  

  在我的解决方案中指出，您正在研究如何避免中的串联和列表理解：

  np.concatenate([combs(n) for n in list_indices])
  

  或者(from itertools import*)：

  np.array(list(chain(*[combinations(n,2) for n in list_indices])))
  

• 我根据您的输入找到了几种将其矢量化的方法：

  def repeat_blocks(a, sizes, repeats):
      #Thanks @Divakar: https://stackoverflow.com/a/51156138/3044825
      r1 = np.repeat(np.arange(len(sizes)), repeats)
      N = (sizes*repeats).sum() # or np.dot(sizes, repeats)
      id_ar = np.ones(N, dtype=int)
      id_ar[0] = 0
      insert_index = sizes[r1[:-1]].cumsum()
      insert_val = (1-sizes)[r1[:-1]]
      insert_val[r1[1:] != r1[:-1]] = 1
      id_ar[insert_index] = insert_val
      out = a[id_ar.cumsum()] 
      return out
  
  def concat_combs1(flow, counts):
      #way 1 based on repetition of blocks of consecutive items
      col1 = repeat_blocks(flow, counts, counts)
      col2 = np.repeat(flow, np.repeat(counts, counts))
      return np.transpose([col1, col2])[col1 < col2]
  
  def concat_combs2(targets, counts):
      #way 2 based on repetition of blocks dissociated from each other
      counts = list(map(len, targets))
      col1 = np.concatenate(np.repeat(targets, counts, axis=0))
      col2 = np.repeat(np.concatenate(targets), np.repeat(counts, counts))
      return np.transpose([col1, col2])[col1 < col2]
  

  测试：

  list_indices = [np.array([0,3,4]), np.array([2,1,0]), np.array([3,5])]
  flow = np.array([0,3,4,2,1,0,3,5])
  counts = np.array([3, 3, 2])
  # Usage:
  np.concatenate([combs(n) for n in list_indices])
  concat_combs1(flow, counts)
  concat_combs2(list_indices)
  

  输出：

  array([[0, 3],
         [0, 4],
         [3, 4],
         [1, 2],
         [0, 2],
         [0, 1],
         [3, 5]])
  

结论

perfplot在igraph.Graph.Barabasi(n = x, m = 3)上有四种方法，包括itertools.combinations和np.triu_indices。这个图的每个顶点平均有3个邻居。总而言之，connection of repeated consecutive blocks效果最好。目前，NumPy数组的串联速度比链接组合的速度要慢，因为要串联大量的小列表。

最终解决方案

为了以最快的方式构建关联矩阵，您需要应用concat_combs1方法的一个小变体：

flow = np.array([0,3,4,2,1,0,3,5])
counts = np.array([3,3,2])
results = np.zeros((np.max(flow)+1, np.max(flow)+1), dtype=int)
col1 = repeat_blocks(flow, counts, counts)
col2 = np.repeat(flow, np.repeat(counts, counts))
results[col1, col2] = 1
np.fill_diagonal(results, 0)

输出

[[0 1 1 1 1 0]
 [1 0 1 0 0 0]
 [1 1 0 0 0 0]
 [1 0 0 0 1 1]
 [1 0 0 1 0 0]
 [0 0 0 1 0 0]]

这篇关于通过避免for循环从节点列表构建邻接矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！