"ツリー"（実際にDAG）の要素をチェックするためのきれいで効率的なアルゴリズムを探してください。

Question

これは宿題ではありません。

視覚的にはツリーのように見えますが、すべてのリーフはユニークです（データベースにユニークなIDを持つ）。その上の階層はやや恣意的です。各チェックボックスには、オン、オフ、パーシャルの3つの状態があります。葉はチェックすることしかできず、チェックもできません。子供の状態は両親の状態を運転するはずです。チェックボックスをクリックすると、それを「トグル」し、必要な変更を上下に伝播する必要があります。部分的にチェックされている親をクリックすると、完全にチェックされます。各子供はリストへのポインタを持っています（私はがこれを私が必要ならばセットに変更することができます）。各親には、アルファベット順にソートされた子のリストがあります。同時に、表示のために、この構造は、下の図からわかるように、拡大して崩壊することができるツリーです。

私はこのアルゴリズムがこれまでに発明されたと確信しています。葉の数は2万に達しているので、私は実際にその性能に気を付けます。しかし、コードを短く読みやすくすることを犠牲にして、私はアルゴから最後のパフォーマンスを奪うことはしません。

私は原理的には（どこに行くにしても）歩き、変更する必要があるすべての葉を特定する必要があると考えました。その後、私は歩いていくべきだ。葉のセットから、私は影響を受けるかもしれない親のセットを把握しなければならない。次に、それを変更する必要のある親のセット、およびその値にフィルタリングします。次にそれらをセットに追加します。それから私はそれらのノードから歩いて繰り返す必要があります。変更する必要がある一連の葉やその他のノードとその値を取得したら、それを実行する必要があります。行列ベースの表現は高価すぎるであろう。

私はC++でこの事を一緒にハッキングしていますが、MFCを使用していますが、私の質問はほとんど言語に依存しません。しかし、私はアルゴリズムの具体的な実装を好むだろう。 Python、Perl、Scalaのようないくつかの言語は、あまりにも現代的な罠を持っているかもしれません。私はJava、C＃（LINQを除いたもの）のように、従来のものに固執しようとします。

コード、リンク、参考文献および質問は大歓迎です。

Answer 1

ああ、これは複雑である理由、私が参照してください。アイテムを「変更された可能性のある」リストに追加するときに、アイテムを段階的にトポロジカルにソートする必要があります。そうすれば、要素を処理した後で要素を処理するだけです。これにより、変更された要素を一度だけ処理し、DAGがあると仮定すると、循環参照のために要素を処理できない状況に遭遇することはありません。

ので、一般的なアルゴリズムは次のようになります：

• 処理するために、ノードのセットにすべての変更の葉の子を追加します。
• 処理する子を持たないセット内のすべてのノードについて：
  • 新しい状態を決定します。
  • 状態が変更された場合は、ノードのセットにその親を追加して プロセスにします。

難しいのは、「処理するために、子を持たないすべてのノード」です。しかしそれは単なるトポロジカルなものです。

Answer 2

「部分的な」状態が問題です。

あなたが「部分的」状態にあり、子供が「未チェック」を渡す場合も、「未チェック」にするか、または「部分的」状態を維持する必要がありますか？これには、他のすべての子に照会する必要があります。私は（非葉のために）の代わりにフラグの2つの数字を維持するために構造を変更することをお勧め：

• 子どもの数は（直接ではないの葉）
• チェックする子どもの数は（直接ではない葉）

もちろん、アップデートごとに正しいものを維持する必要があります。

正しく更新するには、子供から両親まで簡単に歩いて行くことができます。それぞれの子供が親に対して1つの参照しか持たないことを確認したら、子供がその状態を変えるたびに、それぞれの親（したがってそれぞれ）を更新します。