Build new adjacency matrix after graph partitioning

Question

I have an adjancecy matrix stored in CSR format. Eg

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

I am now paritioning said graph using METIS. This gives me the partition vector part of the graph. Basically a list that tells me in which partition each vertex is. Is there an efficient way to build the new adjacency matrix for this partitioning such that I can partition the new graph again? Eg a function rebuildAdjacency(xadj, adjncy, part). If possible reusing xadj and adjncy.

Answer 1

I'm assuming that what you mean by "rebuild" is removing the edges between vertices that have been assigned different partitions? If so, the (probably) best you can do is iterate your CSR list, generate a new CSR list, and skip all edges that are between partitions.

In pseudocode (actually, more or less 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))

I don't think that you can do this very efficiently re-using the old xadj and adjcy fields. However, if you are doing this recursively, you can save memory allocation / deallocation by having exacyly two copies of xadj and adjc, and alternating between them.