Ищете чистый и эффективный алгоритм для проверки включения и выключения элементов «дерева» (на самом деле DAG)

Question

Это не домашняя работа.

Визуально это выглядит как дерево, но все листья уникальны (имеют уникальные идентификаторы в базе данных). Иерархия над ними несколько произвольна. Каждый флажок имеет 3 состояния: включено, выключено и частично. Листья могут быть только проверены или не проверены. Состояние детей должно влиять на состояние родителей. Нажатие на флажок должно «переключить» его и распространять необходимые изменения вверх или вниз. Если вы щелкнете по родительскому элементу, который частично отмечен, он должен стать полностью отмеченным У каждого ребенка есть указатель на список (я мог бы изменить его на набор, если я должен) родителей. У каждого родителя есть список детей, отсортированных по алфавиту. В то же время, для целей отображения, эта структура представляет собой дерево, которое я могу развернуть и свернуть, как вы можете видеть на рисунке ниже.

Я уверен, что этот алгоритм был изобретен ранее. Так как количество листьев было до 20 000, я забочусь о производительности на практике. Но я бы не пытался выжать каждую последнюю потерю производительности из алгоритма за счет того, что код короткий и читаемый.

Я подумал, что в принципе я должен спуститься (если есть куда идти) и определить все листья, которые должны быть изменены. После этого я должен подняться. Из набора листьев я должен выяснить набор родителей, которые могут быть затронуты. Затем отфильтруйте его до набора родителей, который нужно будет изменить, и на какое значение. Затем добавьте их в набор. Тогда мне нужно будет подняться с этих узлов и повторить. После того, как у меня есть набор листьев и других узлов, которые необходимо изменить, а также их значения, мне нужно будет просто сделать это ... или что-то в этом роде. Матричное представление было бы слишком дорого.

Я взломал эту штуку вместе в C++, используя MFC, но мой вопрос в значительной степени не зависит от языка. Однако я бы предпочел конкретную реализацию алгоритму. У некоторых языков, таких как Python, Perl, Scala, могут быть слишком современные хитрости. Я бы попробовал придерживаться чего-то более традиционного, например Java, C # (минус LINQ).

Код, ссылки, ссылки и вопросы приветствуются.

Answer 1

«Частичное» состояние является проблемой здесь.

Если вы находитесь в «частичном» состоянии, и дочерний балл «непроверенный», если вы тоже останетесь «непроверенным» или сохраните свое «частичное» состояние?Это требует опроса всех других детей.Я бы предложил изменить структуру так, чтобы вместо флагов оставались 2 числа (для не-листьев):

• количество детей (листья не прямые)
• количество проверенных детей(оставляет не прямой)

Конечно, вы должны поддерживать их правильными при каждом обновлении.

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

Answer 2

Ах, я понимаю, почему это сложно. Вы хотите постепенно топологически сортировать элементы по мере их добавления в список «возможно измененных». Таким образом, вы обрабатываете элементы только после обработки их дочерних элементов; это гарантирует, что вы будете обрабатывать измененные элементы только один раз, и, если у вас есть DAG, вы не столкнетесь с ситуацией, когда вы не сможете обработать какие-либо элементы из-за циклических ссылок.

Итак, общий алгоритм выглядит так:

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

Трудная часть - это "каждый узел, у которого нет дочерних элементов для обработки". Но это только топологический вид.