0

我有一个以 CSR 格式存储的邻接矩阵。例如

xadj = 0 2 5 8 11 13 16 20 24 28 31 33 36 39 42 44
adjncy = 1 5 0 2 6 1 3 7 2 4 8 3 9 0 6 10 1 5 7 11 2 6 8 12 3 7 9 13 4 8 14 5 11 6 10 12 7 11 13 8 12 14 9 13

我现在正在使用 METIS 对所述图表进行分区。这给了我图的分区向量part。基本上是一个列表，告诉我每个顶点在哪个分区中。有没有一种有效的方法来为这个分区构建新的邻接矩阵，以便我可以再次对新图进行分区？例如一个函数rebuildAdjacency(xadj, adjncy, part)。如果可能的话，重用xadj和adjncy.

4

1 回答 1

1

我假设您所说的“重建”是指删除已分配不同分区的顶点之间的边？如果是这样，您可以做的（可能）最好的事情是迭代您的 CSR 列表，生成一个新的 CSR 列表，并跳过分区之间的所有边。

在伪代码中（实际上，或多或少是 Python）：

new_xadj = []
new_adjcy = []

for row in range(0, n):
  row_index = xadj[row]
  next_row_index = xadj[row+1]

  # New row index for the row we are currently building
  new_xadj.append(len(new_adjcy)) 

  for col in adjncy[row_index:next_row_index]:
    if partition[row] != partition[col]:
      pass # Not in the same partition
    else: 
      # Put the row->col edge into the new CSR list
      new_adjcy.append(col)

# Last entry in the row index field is the number of entries
new_xadj.append(len(new_adjcy))

我认为您不能非常有效地重复使用旧的xadj和adjcy字段。但是，如果您以递归方式执行此操作，则可以通过精确地拥有 and 的两个副本并在它们之间交替来节省内存分配/xadj释放adjc。

于 2018-08-06T09:42:47.697 回答