Алгоритм поиска циклических ссылок в электронной таблице

Question

У меня есть электронная таблица с формулами.Я ищу лучший алгоритм для обнаружения циклических ссылок среди формул.Текущий подход, который я использую, является медленным и использует слишком много памяти, когда в формулах используются длинные цепочки вычислений.Это включает в себя сохранение наборов всех иждивенцев для каждой формулы.Таким образом, если в каждом первом столбце ячеек есть формула со ссылкой на ячейку перед ним, набор первой ячейки будет пустым.Набор 2-й ячейки будет содержать только первую ячейку, набор 3-й ячейки будет содержать ячейки 1 и 2, ..., набор 1000-й ячейки будет содержать до 999 ячеек.Когда была введена новая формула, создается ее набор зависимостей, и если набор содержит новую формулу, существует циклическая ссылка.Но очевидно, что для этого сценария необходимое время и память растут в геометрической прогрессии.

Answer 1

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

См. http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

Представьте зависимости между ячейками в виде ориентированного графа и используйте Алгоритм сильносвязанных компонентов Тарьяна (каждый сильносвязанный компонент размера 2 или больше содержит циклы).

Answer 3

Возможно, у вас есть мотивы для самостоятельной проверки, но Excel уже проверяет циклические ссылки автоматически. Вы можете использовать свойство Worksheets.CircularReference в VBA для доступа к этой информации.