search

KarypisLab / METIS

METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering
Other
699 stars 138 forks source link

Recursive bisection labeling #56

Closed dj-park closed 1 year ago

dj-park commented 1 year ago

I have a graph that has 1K nodes, for example. I want to assign these nodes to a fat-tree network that has 32 nodes. The output file after gpmetis -ptype=rb graphfile 32 contains 0~31 labels for 1K nodes.

My understanding is that label 0-15 is the first bisected part, and label 16-31 is the second bisected part. Is this correct? Reading the source code it performs bisection and assign 0-15 to one bisected part and 16-31 to another bisected part. Just want to make sure my understanding is correct.

I originally wanted to do 1)cluster 1K nodes to 32 nodes 2)perform bisection to assign two 16 nodes 3)perform bisection to assign two 8 nodes 4)so on But I realized that it's already performed when I do 1) with Recursive Bisection option.

Thanks in advance.

karypis commented 1 year ago

Your above understanding on how -ptype=rb is numbering the partitions is correct.