С#: избегать бесконечной рекурсии при перемещении графа объектов

Ответ 1

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

В качестве альтернативы, если циклы вернутся только к родительскому, вы можете сохранить ссылку на родительский элемент, а не на свойства, которые ссылаются на него.

Для простоты, если вы знаете, что родительская ссылка будет иметь определенное имя, вы можете просто не зацикливаться на этом свойстве:)

Ответ 2

Какое совпадение; это тема моего блога в этот понедельник. См. Более подробную информацию. До тех пор, здесь некоторый код, чтобы дать вам представление о том, как это сделать:

static IEnumerable<T> Traversal<T>(
    T item,
    Func<T, IEnumerable<T>> children)
{
    var seen = new HashSet<T>();
    var stack = new Stack<T>();
    seen.Add(item);
    stack.Push(item); 
    yield return item;
    while(stack.Count > 0)
    {
        T current = stack.Pop();
        foreach(T newItem in children(current))
        {
            if (!seen.Contains(newItem))
            {
                seen.Add(newItem);
                stack.Push(newItem);
                yield return newItem;
            }
        }
    } 
}

Метод принимает две вещи: элемент и отношение, которое создает набор всего, что находится рядом с элементом. Он производит обход глубины транзитивного и рефлексивного закрытия отношения смежности на предмете. Пусть количество элементов на графике равно n, а максимальная глубина равна 1 <= d <= n, если коэффициент ветвления не ограничен. Этот алгоритм использует явный стек, а не рекурсию, потому что (1) рекурсия в этом случае превращает то, что должно быть алгоритмом O (n) в O (nd), то есть что-то между O (n) и O (n ^ 2) и (2) чрезмерная рекурсия может взорвать стек, если d больше нескольких сотен узлов.

Обратите внимание, что использование пиковой памяти этого алгоритма, конечно, O (n + d) = O (n).

Итак, например:

foreach(Node node in Traversal(myGraph.Root, n => n.Children))
  Console.WriteLine(node.Name);

Имеют смысл?

Ответ 3

Если вы выполняете обход графика, вы можете иметь флаг "посещенный" на каждом node. Это гарантирует, что вы не перейдете к node и, возможно, застряли в бесконечном цикле. Я считаю, что это стандартный способ выполнения обхода графика.

Ответ 4

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

Ответ 5

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

A
=> B
   => C
=> D
   => C

Это может быть справедливо (подумайте XmlSerializer, который просто напишет экземпляр C из двух экземпляров), поэтому часто необходимо нажать/поп-объекты в стеке, чтобы проверить истинную рекурсию. В последний раз, когда я реализовал "посетителя", я сохранил счетчик "глубины" и только включил проверку стека за пределами определенного порога - это означает, что большинство деревьев просто заканчивают выполнение ++/--, но не более того дорогая. Вы можете увидеть подход, который я принял здесь.

Ответ 6

Я опубликовал сообщение, в котором подробно объясняются примеры кода, как сделать обход объекта рекурсивным отражением, а также обнаружить и избежать рекурсивных ссылок, чтобы предотвратить исключение стека по потоку: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/

В этом примере я сделал первый проход с использованием рекурсивного отражения, и я поддерживал HashSet посещенных узлов для ссылочных типов. Необходимо быть осторожным, чтобы инициализировать ваш HashSet с помощью своего пользовательского сопоставления равенства, который использует ссылку на объект для вычисления хэша, в основном метод GetHashCode(), реализованный самим базовым классом объекта, а не перегруженные версии GetHashCode(), потому что если типы свойств, с которыми вы переходите метод GetHashCode с перегрузкой, вы можете обнаружить ложные хеш-коллизии и подумать, что вы обнаружили рекурсивную ссылку, которая в действительности может заключаться в том, что перегруженная версия GetHashCode создает одно и то же значение хеширования с помощью некоторой эвристики и запутывает HashSet, все, что вам нужно обнаружить - есть ли какой-либо родительский ребенок в любом месте дерева объектов, указывающем на то же место в памяти.