Какой будет хороший алгоритм для циклической проверки ссылок в этом случае?

Question

Учитывая, что у вас есть следующий класс (плохой C #, но вы получаете дрейф):

public abstract class AmICircular
{
  // assume Children is never null
  private List<AmICircular> Children {get;set;}

  // assume target is never null
  public void Add(AmICircular target)
  {
    target.PerformCircularReferenceCheck(this);
    Children.Add(target);
  }

  // throws when a circular reference is detected
  protected abstract void PerformCircularReferenceCheck(AmICircular target);
}

Как бы вы реализовали PerformCircularReferenceCheck? И нет, это не домашнее задание.

Наивной реализацией, imo, было бы сделать проверку ссылок на this и всех дочерних элементах, а затем вызвать PerformCircularReferenceCheck для target, передав this. Но мне интересно, есть ли лучшие, проверенные и эффективные способы сделать это, например, добавить метод, чтобы свернуть все дерево ссылок Children для this и target, а затем изучить результаты (меньшее давление на стек ?) или, возможно, полностью избежать проверки, используя другую (может быть, самопроверку!) коллекцию, отличную от List ?

Как бы вы это сделали?

edit: как указал Стефан, необходимо только определить, достижимо ли это для цели

Answer 1

В случае, когда вы никогда не добавляете объекты, ссылающиеся на себя (которые будут определены позже), ваша структура данных описывает направленный ациклический граф (http://en.wikipedia.org/wiki/Directed_acyclic_graph),, где каждый экземпляр класса IAmCircular описывает узел с набор прямых узлов-преемников = Children.

Предполагая, что до этого момента цикл не создавался, требуемой функции PerformCircularReferenceCheck нужно только проверить, достижимо ли «this» из «target». Если это так, он должен вернуть исключение.

В теории сложности эта проблема связана с ST-связностью (http://en.wikipedia.org/wiki/St-connectivity) и полна для класса NL (http://en.wikipedia.org/wiki/NL_(complexity)),, даже если вы ограничиваете ввод ациклическими графами (как в вашем случае)).

В частности, теорема Савича (http://en.wikipedia.org/wiki/Savitch%27s_theorem)) дает конструктивный способ создания для него O (log ^ 2 n) пространственного алгоритма (работающего во времени O (n ^ 2)), где n - число узлов.

Кроме того, будучи NL-полным, маловероятно, чтобы существовал алгоритм, работающий в пространстве O (log n) (т.е. использующий только постоянное число указателей на узлы), поскольку это подразумевало бы маловероятную NL = L. РЕДАКТИРОВАТЬ: в частности, небольшие вариации алгоритма зайца и черепахи, предложенные кем-то, не будут работать (потому что они будут использовать слишком мало места).

Я бы порекомендовал реализовать тривиальный алгоритм O (n) времени, O (n) пространства, который генерирует для «цели» свой набор преемников (рекурсивно) и проверяет, появляется ли «this» в этом наборе.

Будьте осторожны, важна явная конструкция множества. В противном случае, если вы просто рекурсивно проверяете, достижимо ли «this» любым преемником «target», вы рискуете работать в экспоненциальном времени.

Я рекомендовал алгоритм пространства O (n) времени / O (n), потому что он асимптотически лучший из возможных по времени, и вы уже используете пространство O (n) для своей структуры данных.

Answer 2

Итеративное решение состоит в том, чтобы определить множество R (достижимый) и CR (дочерние элементы Reachable).

Вы начинаете с R = {this} и CR = {this.children}.

На каждом шаге вы проверяете, содержит ли CR this (или target, в зависимости от вашей точной цели). Если нет, вы добавляете CR в R и устанавливаете CR в дочерние элементы CR, а также удаляете элементы R из CR.

Если CR становится пустым, R - это полный набор элементов, доступных с this.