METIS系列圖分區器

Question

METIS圖分區算法用於分區大圖。我有一個實際上是森林的圖。我想知道METIS在這種情況下如何進行分區？

Answer 1

確實，METIS可以對大圖進行分區，但這並不意味着它不能管理更小的圖或不同類型的圖。

林只是不循環，在這裏我們可以有斷開部分的一種特殊類型的圖表......

與任何其他類型的圖表，METIS會執行三個級別劃分方法：

1. 粗化（在你的情況，你有森林圖，所以它可能完成得真快，因爲這種類型的圖表很可能將有少量的邊緣或連接的）

2. 初始分區

3. Uncoarsening + fine-grained balancing。

所以基本上，一切都會像任何類型的圖表一樣工作。

從我個人的經驗來看，我發現METIS在使用不連續的圖形時（森林是斷開連接的圖形）沒有給出最佳結果，所以我實現了自己的邏輯來查找所有頂點組連接，然後用METIS來劃分這個組（這是連接）...

我推薦從METIS library documentation讀關於METIS的。