Algoritmo para encontrar referencias circulares en una hoja de cálculo

Question

Tengo una aplicación de hoja de cálculo con fórmulas. Estoy buscando el mejor algoritmo para detectar referencias circulares entre las fórmulas. El enfoque actual que tengo es lento y usa demasiada memoria cuando hay largas cadenas de cálculos con las fórmulas. Implica mantener conjuntos de todos los dependientes para cada fórmula. Entonces, si la primera columna de celdas tuviera una fórmula con una referencia a la celda anterior, el primer conjunto de celdas estaría vacío. El conjunto de la 2da celda solo contendría la primera celda, el conjunto de la 3ra celda contendría las celdas 1 y 2, ..., el conjunto de la 1000.a celda contendría las 999 celdas anteriores. Cuando se introdujo una nueva fórmula, se creó su conjunto de dependientes y si el conjunto contiene la nueva fórmula, hay una referencia circular. Pero, obviamente, para este escenario, el tiempo y la memoria requeridos crecen exponencialmente.

Answer 1

Debe hacer una clasificación topológica de las celdas de todos modos para poder calcular rápidamente los valores de las celdas cuando algo se cambia. El procedimiento de clasificación topológica también detecta ciclos como un subproducto.

Ver http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

Represente las dependencias entre celdas como un gráfico dirigido, y use Tarjan's strongly connected components algorithm (cada componente fuertemente conectado de tamaño 2 o mayor contiene ciclos).

Answer 3

Tal vez usted tiene motivos para comprobar por su cuenta, pero Excel ya se verifica para las referencias circulares de forma automática. Puede usar la propiedad Worksheets.CircularReference en VBA para acceder a esta información.