Модельное предложение для графа для решателя Constraing Programing (gecode)

Question

Проблема: Учитывая помеченный (1..n) неориентированный граф, создайте модель в Gecode для поиска суперграфа с заданной степенью последовательности:

Трудности: главная трудность заключается в том, чтобы найти причудливую модель, чтобы точно выразить градусы над ней:

Почему не матрица смежности? Потому что граф имеет тенденцию быть большим и разреженным

Почему не Edge list? Мы собираемся добавить ребра, но мы не знаем, сколько их, CP требует предварительно определенного числа переменных (я прав?)

Почему не список смежности? Задача моделирования в виде списка множеств, нам нужно выдвинуть ограничение для всех i, j: (j в a[i] <=> i в a[j])

Answer 1

Из тех возможностей, которые вы предлагаете, использование "списка смежности", вероятно, будет лучшим.

Вы обеспокоены тем, что вам придется много пропагандистов направлять между сетами; однако Gecode включает специальный канальный пропагатор для канала между наборами: http://www.gecode.org/doc-latest/reference/classGecode_1_1Set_1_1Channel_1_1ChannelSet.html. Этот пропагатор направляется точно так, как вы описали, и должен минимизировать затраты на поддержание согласованности наборов.