Zyklen in Objektlisten

[23]

Hallo,

ich habe eine Klasse Person die die als Member eine Collection mit weiteren Personen hat.
Mit dieser Klasse kann ich einen Baum abbilden.

Ich habe nun eine Add-Methode um einer Person neue Personen hinzu zufügen. Dort implementiere ich kein Zykluscheck.

Wenn ich nun über eine Person und deren (Kinder) also Personen rekursiv iteriere und ein Zyklus drin ist, entsteht eine Endlosrekursion.

Wie kann ich beim iterieren einen Zyklus erkennen und das bereits besuche Objekt meiden? Meine Lösung funktioniert z.Z. mit einer HashMap d.h. ich speicher die Objekt-ID als Key und prüfe zu Beginn der rekursiven Methode ob das Objekt schon in der HashMap liegt.

Gibt es bessere Lösungen?

Viele Grüße

 

[sambalmueslie]

Hey,

die einzige mir bekannte Methode ist das "markieren" der durchlaufenen Knoten, wie du es ja in deiner Map machst.

Das hier hab ich dazu noch gefunden:
Zyklenfreiheit
was wohl so ähnlich ist wie das was du tust.

Gruß Oli

 

[SlaterB]

wie kommst du in der Rekursion an die Map ran, wird die als Parameter übergeben?
können zwei Threads gleichzeitig unabhängig voneinander herumrekursieren?

wenn letzteres nicht wichtig ist, ist als Alternative immer eine Markierung der Objekte an sich möglich,
verschandelt diese etwas, spart aber die Map bzw. ein Set,
allerdings darauf achten vor oder nach einem Durchlauf aufzuräumen, alle Markierungen zu löschen

 

[Andi_CH]

ohne "Verschandelung" (oder wenn man die Klasse gar nicht ändern kann):

Statt markieren kann die Referenz auf das Objekt in einer geeigneten Daanstruktur gespeichert werden, nachdem überprüft wurde ob die nicht etwa schon gespeichert ist.

 

[SlaterB]

wie kannst du mein Wort zitieren ohne mein Posting komplett gelesen zu haben mit der Erkenntnis,
dass eine separate Datenstruktur, etwa Map, die bereits genannte Ursprungsidee war?

 

[23]

Ok dann bleibt es bei der Map
Danke!

 

[Andi_CH]

Och ich befinde mich hier in bester Gesellschaft wenn ich die Threads nicht immer erst ganz durchlese - das ist hier eher an der Tagesordnung ;-) (Ist das wenigstens eine gute Ausrede? )

Zitiert und in "" gesetzt habe ich es nur, weil ich ein zusätzliches Attribut längst nicht immer als Verschandelung empfinde - es ist oft ein einfacher Weg, vor allem wenn die Datenstruktur (wie in einem mir sehr gut bekannten Fall) serialisiert wird.

 

[23]

Was gegen die Objekt Markierung spricht, ist das entfernen der Markierung im Vorfeld oder hinterher.

Gibt es evtl. eine bessere Datenstruktur als eine Map? Der Zugriff auf den Key kostet ja leider etwas

 

[Andi_CH]

Hm - durchsuchen eines Array kostet auch.
Für eine eher kleine und zum voraus bekannter Anzahl von Objekten welche alle eine eindeutige Id hatten hab ich schon eine umgedrehte Variante gesehen - ein boolean[], die Id wurde als index verwendet und der boolean gesetzt.

Einige Gedanken dazu:
- klappt nur, wenn eine wirklich eindeutige Id vorhanden ist
- nur bei einer bekannten Anzahl Obejkten elegant realisierbar
- schnelle Initialisierung bei grosser Anzahl mit new boolean[X]

 

[SlaterB]

bei der Markierung kann man das Löschen evtl. vermeiden, wenn man als Markierung eine Zahl nimmt und bei jeder Suche eine größere,
dadurch dass die Markierung überall eingetragen wird, brauch man wahrscheinlich auch keinen zusätzlichen rekursiven Parameter

int x = currentNode.mark;
for(alle Nachfolger y) {
    if (y.mark == x) continue;
    else: markieren mit x, bearbeiten oder in Liste speichern
}

Nachteil ist dann noch dass man mit int nur 2 Milliarden Suchen ausführen kann, bzw. das Doppelte wenn man bei -MAX_VALUE anfängt,
long schafft zum Glück etwas mehr Luft , braucht dann aber 8 Byte

 

[Wildcard]

ich habe eine Klasse Person die die als Member eine Collection mit weiteren Personen hat.
Mit dieser Klasse kann ich einen Baum abbilden.

Ich habe nun eine Add-Methode um einer Person neue Personen hinzu zufügen. Dort implementiere ich kein Zykluscheck.

Wenn ich nun über eine Person und deren (Kinder) also Personen rekursiv iteriere und ein Zyklus drin ist, entsteht eine Endlosrekursion.

Ein Baum kann niemals einen Zyklus haben, sonst wäre es ein Graph.
Die Frage ist also, soll es ein Baum, oder ein Graph sein? Wenn es ein Baum sein soll, dann sollte das Modell das auch forcieren. Das muss man allerdings nicht selbst machen, dafür gibt es Tools.
Eclipse Modeling Framework ? Wikipedia

 

[Landei]

Zyklenfreiheit kann man durch Topologische Sortierung nachweisen.

 

[23]

Man kann nicht immer nur Tools (Overhead) nutzen und wenn man Bäume darstellt und eine beliebige Datenquelle anzapft sollte eine Endlosschleife einfach vermieden werden.

Danke für die guten Tipps!

 

[maki]

Man kann nicht immer nur Tools (Overhead) nutzen und wenn man Bäume darstellt und eine beliebige Datenquelle anzapft sollte eine Endlosschleife einfach vermieden werden.!

Schon klar, aber warum dann erst erlauben dass falsche Strukturen gebaut werden um sich danach mit dem Problem zu befassen wie man diese falschen Strutkuren erkennt?

IMHO ist dein größtes Problem hier:

Ich habe nun eine Add-Methode um einer Person neue Personen hinzu zufügen. Dort implementiere ich kein Zykluscheck.

 

[Wildcard]

Schon klar, aber warum dann erst erlauben dass falsche Strukturen gebaut werden um sich danach mit dem Problem zu befassen wie man diese falschen Strutkuren erkennt?

Genau so sehe ich das auch und besagtes Tool erzeugt Modelle die sich selbst durch explizites Containment konsistent halten. Ein Zyklus kann auf diese Art nicht entstehen und ich sehe keinen guten Grund warum ich mir selbst die Arbeit machen sollte wenn es sich wunderbar automatisieren lässt.

Man kann nicht immer nur Tools (Overhead) nutzen

EMF Modelle sind performanter als ein Modell das ich selbst schreiben würde und ich wäre auch bereit zu wetten das ein EMF Modell schneller ist als dein selbst implementiertes.

 

[23]

Generisches Widget => Beliebige Anwender hänge beliebige Daten dran...

 

[maki]

Generisches Widget => Beliebige Anwender hänge beliebige Daten dran...

Und?

Beliebige Anwender bauen deinen Baum zu einem ungerichteten Graphen um?
Keine so gute Idee...

Solltest prüfen, ob der "Zweig" das Widget, was eingehängt werden soll, schon enthält. Sowohl in Richtung des Parents, als auch in Richtung der Children.