Auf der Suche nach einem sauberen und effizienten Algorithmus zum Ein- und Ausschalten von Elementen eines "Baumes" (eigentlich einer DAG)

Question

Dies ist keine Hausaufgabe.

Visuell sieht es wie ein Baum aus, aber alle Blätter sind einzigartig (haben einzigartige IDs in der Datenbank). Die Hierarchie über ihnen ist etwas willkürlich. Jedes Kontrollkästchen hat drei Zustände: ein, aus und teilweise. Blätter können nur überprüft oder nicht überprüft werden. Der Zustand der Kinder sollte den Zustand der Eltern bestimmen. Klicken Sie auf ein Kontrollkästchen, um es "umzuschalten" und die notwendigen Änderungen nach oben oder unten zu propagieren. Wenn Sie auf ein übergeordnetes übergeordnetes Element klicken, sollte es vollständig überprüft werden. Jedes Kind hat einen Zeiger auf eine Liste (I könnte dies zu einem Satz ändern, wenn ich muss) der Eltern. Jeder Elternteil hat eine alphabetisch sortierte Liste von Kindern. Gleichzeitig ist diese Struktur zu Anzeigezwecken ein Baum, den ich erweitern und reduzieren kann, wie Sie auf dem Bild sehen können.

Ich bin sicher, dass dieser Algorithmus zuvor erfunden wurde. Da die Anzahl der Blätter bis zu 20.000 beträgt, ist mir die Leistung in der Praxis wichtig. Aber ich würde nicht versuchen, den letzten Tropfen Leistung aus dem Algo herauszuquetschen, auf Kosten von Code, der kurz und lesbar ist.

Ich dachte, dass ich im Prinzip gehen sollte (wenn es irgendwo zu gehen gibt) und alle Blätter identifizieren, die geändert werden sollten. Danach sollte ich hochgehen. Aus der Menge der Blätter sollte ich eine Gruppe von Eltern herausfinden, die betroffen sein könnten. Dann filtern Sie es auf die Menge der Eltern, die geändert werden müssen, und auf welchen Wert. Dann füge diese zu einem Set hinzu. Dann muss ich von diesen Knoten hochgehen und es wiederholen. Nachdem ich eine Reihe von Blättern und anderen Knoten habe, die sich ebenso wie ihre Werte ändern müssen, muss ich es einfach tun ... oder so ähnlich. Eine matrixbasierte Darstellung wäre zu teuer.

Ich hack dieses Ding zusammen in C++ mit MFC, aber meine Frage ist ziemlich sprachunabhängig. Ich würde jedoch eine konkrete Implementierung einem Algorithmus vorziehen. Einige Sprachen wie Python, Perl, Scala haben vielleicht zu moderne Tricks in den Ärmel. Ich würde versuchen, etwas Konventionelleres beizubehalten, wie Java, C# (minus LINQ).

Code, Links, Referenzen und Fragen sind willkommen.

Answer 1

Ah, sehe ich, warum dies kompliziert ist. Sie möchten Objekte schrittweise topologisch sortieren, wenn Sie sie der Liste "möglicherweise geändert" hinzufügen. Auf diese Weise verarbeiten Sie nur Elemente, nachdem Sie ihre Kinder verarbeitet haben. Dies stellt sicher, dass Sie geänderte Elemente nur einmal verarbeiten. Wenn Sie eine DAG verwenden, werden Sie aufgrund von Zirkelbezügen keine Situation feststellen, in der Sie keine Elemente verarbeiten können.

So geht der allgemeine Algorithmus wie folgt aus:

• hinzufügen alle wechselnden Blatt Kinder auf den Satz von Knoten zu verarbeiten.
• Für jeden Knoten in der Gruppe, die keine untergeordneten Elemente verarbeiten muss:
  • Ermitteln Sie den neuen Status.
  • Wenn der Status geändert wurde, fügen Sie die übergeordneten Elemente zum Knotensatz hinzu.

Der schwierige Teil ist der „jeder Knoten, der keine Kinder zu verarbeiten hat“. Aber das ist nur eine topologische Art.

Answer 2

Der "teilweise" Zustand ist hier ein Problem.

Wenn Sie sich in einem "teilweisen" Zustand befinden und ein Kind "unchecked" passiert, sollten Sie auch "unchecked" gehen oder Ihren "partiellen" Zustand beibehalten? Dies erfordert die Abfrage aller anderen untergeordneten Elemente. Ich würde vorschlagen, um die Struktur zu ändern 2 Zahlen zu halten statt Fahnen (für Nicht-Blätter):

• die Zahl der Kinder (Blätter direkt nicht)
• die Anzahl der geprüften Kinder (Blätter nicht direkt)

Sie müssen sie bei jedem Update natürlich korrekt beibehalten.

Um sie richtig zu aktualisieren, ist es ein einfacher Spaziergang vom Kind zu seinen Eltern. Wenn Sie sicherstellen, dass jedes Kind nur einen Verweis auf seinen Elternteil hat (und dasselbe gilt für den Elternteil ...), aktualisieren Sie jedes Mal, wenn ein Kind seinen Status ändert, jedes Elternelement (und damit jedes Kind).