Обнаружение циклов в графе генеалогии во время поиска в глубину - PullRequest
6 голосов
/ 07 марта 2009

Я загружаю лошадиные генеалогические данные рекурсивно. Для некоторых неправильных наборов данных моя рекурсия никогда не останавливается ... и это потому, что в данных есть циклы.

Как я могу обнаружить, что эти циклы перестают повторяться?

Я думал о том, чтобы при возвращении поддерживать хэш-таблицу со всеми "посещенными" лошадьми. Но это найдет некоторые ложные срабатывания, потому что лошадь МОЖЕТ быть дважды на дереве.

Чего не может случиться, так это того, что лошадь предстает отцом, дедом или прадедом САМОГО.

Ответы [ 6 ]

6 голосов
/ 07 марта 2009

Псевдокод:

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen)
{
   if(seen.Contains(currentNode)) return;
   // Or, do whatever needs to be done when a cycle is detected

   ProcessHorse(currentNode.Horse); // Or whatever processing you need

   seen.Push(currentNode);

   foreach(GenTreeNode childNode in currentNode.Nodes)
   {
      ProcessTree(childNode, seen);
   }

   seen.Pop();
}

Основная идея состоит в том, чтобы сохранить список всех узлов, которые мы уже видели на пути к текущему узлу; если вернуться к узлу, через который мы уже прошли, то вы знаете, что мы сформировали цикл (и мы должны пропустить значение или сделать все, что нужно)

2 голосов
/ 15 марта 2009

Это звучит как случай, когда вы, наконец, можете применить этот вопрос о пустяках интервью: найдите цикл в связанном списке, используя только O (1) памяти.

В этом случае ваш «связанный список» - это последовательность элементов, которую вы перечисляете. Используйте два перечислителя, запустите один на половинной скорости, и если быстрый когда-нибудь попадет в медленный, у вас будет цикл. Это также будет время O (n) вместо времени O (n ^ 2), необходимого для проверки «видимого» списка. Недостатком является то, что вы узнаете о цикле только после того, как некоторые узлы были обработаны несколько раз.

В этом примере я заменил метод «половинной скорости» более простым для записи методом «маркеров сброса».

class GenTreeNode {
    ...

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
        long cur_track_count = 0;
        long high_track_count = 1;
        T post = default(T);
        foreach (var e in sub_enumerable) {
            yield return e;
            if (++cur_track_count >= high_track_count) {
                post = e;
                high_track_count *= 2;
                cur_track_count = 0;
            } else if (object.ReferenceEquals(e, post)) {
                throw new Exception("Infinite Loop");
            }
        }
    }

    ...

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
        yield return this;
        foreach (var child in this.nodes)
            foreach (var e in child.tree_nodes_unchecked())
                yield return e;
    }
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary>
    public IEnumerable<GenTreeNode> tree_nodes()
    {
        return CheckedEnumerable(tree_nodes_unchecked());
    }

    ...

    void ProcessTree() {
        foreach (var node in tree_nodes())
            proceess(node);
    }
}
2 голосов
/ 07 марта 2009

Ведение стека всех элементов, ведущих к корню дерева.

Каждый раз, когда вы продвигаетесь вниз по дереву, сканируйте стек на предмет дочернего элемента. Если вы найдете совпадение, то вы обнаружили петлю и должны пропустить этот дочерний элемент. В противном случае поместите ребенка в стек и продолжайте. Всякий раз, когда вы возвращаетесь к дереву, извлекайте элемент из стека и сбрасывайте.

(В случае генеалогических данных «дочерний» узел в дереве, предположительно, является биологическим родителем «родительского» узла.)

1 голос
/ 07 марта 2009

Очень простой способ обнаружить это, проверив само это ограничение:

Что не может случиться, так это то, что лошадь предстает отцом, дедом или прапрадедом САМ.

Всякий раз, когда вы вставляете узел в свое дерево, обходите дерево до корня, чтобы убедиться, что лошадь не существует в качестве какого-либо родителя.

Чтобы ускорить это, вы можете связать хеш-таблицу с каждым узлом, где вы кешируете ответ такого поиска. Тогда вам не придется искать весь путь в следующий раз, когда вы вставите лошадь под этим узлом.

0 голосов
/ 07 марта 2009

Вы имеете дело с направленным ациклическим графом , а не с деревом. Не должно быть никаких циклов, так как потомок лошади не может быть и ее предком.

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

0 голосов
/ 07 марта 2009

Ваше решение для хеш-таблицы должно работать, если вы отслеживаете узлы вместо лошадей. Просто убедитесь, что каждый раз, когда вы читаете новую лошадь, вы создаете новый узел, даже если значение / лошадь совпадает со значением / лошади предыдущего узла.

...