Уменьшить объем связи раздела графа в METIS

Question

Я использовал METIS для разделения графа. На данный момент я не использую никаких специальных опций, поэтому я предполагаю, что METIS разбивает график, минимизируя срез края.

Дело в том, что у графиков, над которыми я работаю, есть несколько вершин, у которых много соседей. Я думаю, это означает, что мне придется пропустить опцию, чтобы уменьшить громкость связи, в отличие от обрезки краев.

Как мне это сделать? Я не понимаю, в чем смысл параметра vsize в разделе 5.8, с. 26. Нужно ли связываться с ncon, vwgt или objval? Должен ли я просто сделать опции [METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_VOL и передать их функции?

Кроме того, для графа, у которого число вершин может не быть степенью 2, какой вариант функции следует использовать? k-way(скорее всего) или деление пополам?

Я бы задал эти вопросы на форумах METIS, но, к сожалению, прошло много времени с тех пор, как я зарегистрировался на них без какого-либо ответа на их веб-сайте, поэтому я спрашиваю здесь.

Answer 1

vsize - для указания объема связи, связанного с вершиной. Для большинства приложений вам не нужно указывать это, поскольку предполагается, что оно одно. Если у вас нет ограничений баланса, вы можете игнорировать ncon и vwgt. Переменная objval просто позволяет вам узнать, каково значение цели для сгенерированного раздела (общий вес обрезанных кромок или общий объем связи).

Вы захотите использовать k-way для большего количества разделов, так как это будет быстрее и может привести к более качественным результатам. Оба будут обрабатывать не власть двух чисел разделов. Количество вершин не имеет значения.