Следующий код работает нормально, за исключением случаев, когда он проходит через ациклический граф. Он отмечает ациклический граф как циклический, и я не могу понять почему.
@Override
public boolean isCyclic(DirectedGraph<T> graph) {
List<Node<T>> visitedNodes = new ArrayList<>();
int cycles = 0;
for (Node<T> node : graph) {
if (recNodeCycleCheck(node, visitedNodes)) {
cycles++;
}
visitedNodes = new ArrayList<>();
}
return cycles > 0;
}
private boolean recNodeCycleCheck(Node<T> node, List<Node<T>> visitedNodes) {
if (visitedNodes.contains(node)) {
return true;
}
visitedNodes.add(node);
for (Iterator<Node<T>> it = node.succsOf(); it.hasNext();) {
Node<T> currentNode = it.next();
if (visitedNodes.contains(currentNode)) {
return true;
}
if (recNodeCycleCheck(currentNode, visitedNodes)) {
return true;
}
}
return false;
}
Я постарался назвать код как можно более понятным, чтобы его было легко читать. Первый метод isCyclic () получает граф, и для каждого узла в графе он проверяет его смежный список и наследников узлов в этом списке. Если в какой-то момент они указывают на уже посещенный узел, граф является циклическим.
Кажется, это нормально работает для всех графиков, кроме ациклических.
Есть идеи, что происходит?
«Кажется, это нормально работает для всех графиков, кроме ациклических». это звучит как причудливый способ сказать "мой метод всегда возвращает true
независимо от ввода"
@OldCurmudgeon Реализация по умолчанию, аналогов нет.
Что вы считаете циклом в ориентированном графе? Если у вас есть A -> B, A-> C, C-> D, B-> D, тогда я бы не стал считать это циклом, потому что нет способа вернуть узел a, циклически перемещаясь по графу. Тем не менее, ваш алгоритм помечает D как посещенный, когда вы переходите к нему от A до B к D, поэтому, когда он затем снова переходит от A к C к D, он видит, что D уже "посещен", и говорит, что это цикл, который не тот случай. Итак, я думаю, вы выбрали алгоритм, который не подходит для ориентированного графа; это не похоже на ошибку реализации.
@ErwinBolwidt Он также возвращает false, когда должен. У меня есть тесты, работающие на нем, и он передает все assertFalse и assertTrue, кроме одного с ациклическим графом.
Для какого графа, который не является ациклическим, он возвращает false «когда должен»? Потому что, когда он не ациклический, разве это не означает, что он циклический, и вы должны были вернуть истину?
Вероятно, ваша логика не рассчитана на учет следующего случая ациклического графа:
//A, B and C are the nodes in the graph
A -> B // Edge between A and B
B -> C // Edge between B and C
A -> C // Edge between A and C
В этом случае ваш алгоритм начинает с A, посещает B и C. Затем переходит к следующему преемнику A (то есть C), затем видит, что он уже был посещен, и возвращает true.
Как ваша реализация
equals
выглядит дляNode
? Возможно ли, что два разных узла можно рассматривать какequal
?