Я пытаюсь использовать библиотеку LEMON, и у меня возникает проблема с алгоритмом, который я пытаюсь реализовать. Идея этого алгоритма заключается в том, что существует вектор векторов узлов, и я хочу переместить узлы в разные векторы (цветовые классы) с определенными ограничениями. Вот код, который реализует мой алгоритм:
bool moveColor() {
// pick the smallest color class
sort(colors.begin(), colors.end(), vectorSort);
vector< vector< ListGraph::Node > >::iterator smallestColor = colors.begin();
// shuffle this class
random_shuffle(smallestColor->begin(), smallestColor->end());
// try to move any of the nodes to any bigger class
bool foundNode = false;
vector< ListGraph::Node >::iterator movingNode;
vector< vector< ListGraph::Node > >::iterator destinationClass;
for (movingNode = smallestColor->begin(); movingNode != smallestColor->end() && !foundNode; ++movingNode) {
for (destinationClass = colors.begin()+1; destinationClass != colors.end() && !foundNode; ++destinationClass) {
ListGraph::NodeMap<bool> filter(g, false);
vector< ListGraph::Node >::iterator classNode;
for (classNode = destinationClass->begin(); classNode != destinationClass->end(); ++classNode) {
filter[*classNode] = true;
}
filter[*movingNode] = true;
FilterNodes<ListGraph> subgraph(g, filter);
if (acyclic(subgraph)) {
foundNode = true;
}
}
}
// if a movable node was found, move it. otherwise return false
if (foundNode) {
destinationClass->push_back(*movingNode);
smallestColor->erase(movingNode);
if (smallestColor->empty()) {
colors.erase(smallestColor);
}
return true;
}
return false;
}
Эта функция вызывается в main в цикле, пока узел не может быть перемещен. Основная проблема, с которой я сталкиваюсь в коде — это раздел, который фактически перемещает узел из одного вектора в другой:
if (foundNode) {
destinationClass->push_back(*movingNode);
smallestColor->erase(movingNode);
if (smallestColor->empty()) {
colors.erase(smallestColor);
}
return true;
}
Эта часть, кажется, не работает, потому что я думаю, что узел разрушается при вызове функции стирания. Вот пример идентификаторов узлов до и после вызова этой функции:
NEW ROUND
1
3
0
5 2
7 6 4
NEW ROUND
3
0 32701
5 2
7 6 4
Как видите, идентификатор перемещенного узла неверен (32701 вместо 1). Любая помощь приветствуется.
Проблема на самом деле здесь:
if (acyclic(subgraph)) {
foundNode = true;
}
Когда вы находите узел, вы не break
снаружи for
петля, которая делает movingNode
переход итератора к следующей позиции в векторе (smallestColor->end()
в этом случае) перед проверкой !foundNode
состояние. В этом случае вы должны break
дважды, так как вы выходите из вложенного цикла.
При желании вы можете сохранить итератор, который соответствует критериям, в отдельной переменной для работы вне цикла (отличного от того, который выполняется в цикле for).
О фрагменте, который вы указали в качестве потенциального источника проблемы:
destinationClass->push_back(*movingNode);
вкладывает в destinationClass
копия Node
тот movingNode
итератор указывает на. Это значит, копировать конструктор Node
называется. Как Node
не имеет определяемого пользователем конструктора копирования, компилятор автоматически генерирует его, который копирует значение всех членов, поэтому id
значение должно быть скопировано (конечно, если правильный итератор используется для push_back
). Конечно, оригинальная копия перемещаемого узла уничтожается erase
, но это не влияет на новую копию.
Других решений пока нет …