Выяснение пути круговой зависимости - PullRequest
Новая
       32

Выяснение пути круговой зависимости

2 голосов
/ 17 октября 2011

У меня проблемы с выяснением того, как я могу распечатать путь, по которому существует круговая зависимость (цикл).Если цикл существует, то есть.Я делаю топологическую сортировку на графе (представляющем проект), который содержит различные вершины (задачи).Есть ли простой способ сделать это или другой алгоритм, такой как поиск в глубину, лучше для этого?

Вот что у меня есть: 

public boolean canProjectBeCompleted() { 

    if(this.getProjectTasks() == null) {
        return false;
    }

    LinkedList<Task> queue = new LinkedList<Task>();
    Task task;
    int counter = 0;

    Iterator<Task> taskIterator = this.getProjectTasks().values().iterator();
    while(taskIterator.hasNext()) {
        Task t = taskIterator.next();
        if(t.getInEdgesPredecessors().size() == 0) {
            queue.add(t);
        }
    }

    while(!queue.isEmpty()) {
        task = queue.removeFirst();
        counter++;
        for(int i = 0; i < task.getOutEdgesSuccesors().size(); i++) {
            Task neighbour = task.getOutEdgesSuccesors().get(i);
            neighbour.setCopyNumberOfIncomingEdges(neighbour.getCopyNumberOfIncomingEdges()-1);
            if(neighbour.getCopyNumberOfIncomingEdges() == 0) {
                queue.add(neighbour);
            }
        }
    }
    if(counter < amountOfTasks) {
        return false; //Cycle found, The topological sort cannot complete
    }
    return true; //No cycle found
}

Заранее спасибо!:)

Ответы [ 3 ]

1 голос
/ 22 октября 2011

Как насчет этого?

Вы знаете, что вершины, являющиеся частью циклов, должны иметь как исходящие, так и входящие ребра. Так что начните, как вы, с топологической сортировки и «удалите» (или просто отметьте) вершины с 0 входящими ребрами и удалите их уходящие ребра. Перейдите к соседям и удалите каждый, у которого теперь 0 входящих ребер, и продолжайте. Если у вас еще есть вершины в графе, вы знаете, что где-то в оставшихся вершинах есть цикл, но не где или сколько циклов. Так что именно здесь вы делаете сортировку с обратной топологией, когда начинаете удалять вершины с 0 исходящими ребрами. Это потому, что вы знаете, что вершина без исходящих ребер не может быть частью цикла. Продолжайте, как и в случае с топологической сортировкой, то есть удалите ребра вершины и повторите с соседями. Те вершины, которые остаются в вашем графе, являются частью одного или нескольких циклов. Чтобы узнать количество циклов и порядок появления вершин в каждом цикле, вы можете выполнить поиск в глубине среди оставшегося графа.

Если я не ошибаюсь, я считаю, что сложность должна быть O(|V| + |E|)

0 голосов
/ 17 октября 2011

Матрица смежности A для вашего графа даст вам необходимую информацию, см. http://en.wikipedia.org/wiki/Adjacency_matrix

Например, если записи равны 0 на диагонали для матрицы A в степени p, тонет цикла длины р.Так что, если у вас есть доступ к быстрому умножению матриц, это может быть проще всего реализовать.

0 голосов
/ 17 октября 2011

Существует простой тест на наличие циклов в графе: Непрерывное дерево (граф без циклов) содержит в точности (узлов - 1) eges

Это позволит обнаружить наличие циклов в неориентированном графе и дублировать пути в направленном.

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

Как я вижу в вашем коде, вы изменяете copyNumberOfIncomingEdges без проверки значения первый. Где вы устанавливаете это свойство?

...