图划分后构建新的邻接矩阵

Question

我有一个以 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.

Answer 1

我假设您所说的 "rebuild" 是指移除已分配不同分区的顶点之间的边？如果是这样，您能做的（可能）最好的事情就是迭代您的 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 字段。但是，如果您以递归方式执行此操作，则可以通过恰好拥有 xadj 和 adjc 的两个副本并在它们之间交替来节省内存分配/释放。

图划分后构建新的邻接矩阵

Build new adjacency matrix after graph partitioning

graph

adjacency-matrix

metis