C#: Избегайте бесконечной рекурсии при пересечении графа объектов

Если вы знакомы с Eclipse я бы рекомендовал Eclipse с coldfusion плагин.

http://www.cfeclipse.org/

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

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

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

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

Какое совпадение; это тема моего блога в предстоящий понедельник. Смотрите подробнее. А пока вот код, который даст вам представление о том, как это сделать:

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);

Имеет ли смысл?

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

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

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

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