Алгоритм разбиения графа METIS используется для разбиения большого графа. У меня есть график, который на самом деле является лесом. Я хотел бы знать, как METIS делает разделы в этом случае?Разделитель серийных графов METIS
Ну, действительно, METIS может разбивать большие графики, но это не значит, что он не может управлять меньшими графиками или разными типами графиков.
лес только особый тип графа без циклов, где мы можем быть отсоединены части ...
Как и любой другой тип графика, METIS собирается выполнить три уровня разбиения алгоритма:
Огрублением (в вашем случае, у вас есть лес график, так что это может закончиться очень быстро, потому что тип графика, вероятно, будет иметь небольшое число ребер или соединений)
Initial секционирования
Uncoarsening + мелкозернистая балансировка.
Так что, в принципе, все будет работать как с любым типом графика.
Из моего личного опыта я выяснил, что METIS не дал мне оптимальных результатов при работе с отключенными графиками (и лес был отключен графиком), поэтому я реализовал свою собственную логику для поиска всех групп вершин, которые были подключен, а затем используется METIS для разделения этой группы (которая подключена) ...
Рекомендую прочитать о METIS от METIS library documentation.