Проверить, является ли график циклическим

Следующий код работает нормально, за исключением случаев, когда он проходит через ациклический граф. Он отмечает ациклический граф как циклический, и я не могу понять почему.

   @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 () получает граф, и для каждого узла в графе он проверяет его смежный список и наследников узлов в этом списке. Если в какой-то момент они указывают на уже посещенный узел, граф является циклическим.

Кажется, это нормально работает для всех графиков, кроме ациклических.

Есть идеи, что происходит?

Как ваша реализация equals выглядит для Node? Возможно ли, что два разных узла можно рассматривать как equal?

OldCurmudgeon 12.10.2018 12:12

«Кажется, это нормально работает для всех графиков, кроме ациклических». это звучит как причудливый способ сказать "мой метод всегда возвращает true независимо от ввода"

Erwin Bolwidt 12.10.2018 12:13

@OldCurmudgeon Реализация по умолчанию, аналогов нет.

Lithicas 12.10.2018 12:16

Что вы считаете циклом в ориентированном графе? Если у вас есть A -> B, A-> C, C-> D, B-> D, тогда я бы не стал считать это циклом, потому что нет способа вернуть узел a, циклически перемещаясь по графу. Тем не менее, ваш алгоритм помечает D как посещенный, когда вы переходите к нему от A до B к D, поэтому, когда он затем снова переходит от A к C к D, он видит, что D уже "посещен", и говорит, что это цикл, который не тот случай. Итак, я думаю, вы выбрали алгоритм, который не подходит для ориентированного графа; это не похоже на ошибку реализации.

Erwin Bolwidt 12.10.2018 12:19

@ErwinBolwidt Он также возвращает false, когда должен. У меня есть тесты, работающие на нем, и он передает все assertFalse и assertTrue, кроме одного с ациклическим графом.

Lithicas 12.10.2018 12:19

Для какого графа, который не является ациклическим, он возвращает false «когда должен»? Потому что, когда он не ациклический, разве это не означает, что он циклический, и вы должны были вернуть истину?

Erwin Bolwidt 12.10.2018 12:21
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
2
6
534
1

Ответы 1

Вероятно, ваша логика не рассчитана на учет следующего случая ациклического графа:

//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.

Другие вопросы по теме