# Zyklen in Objektlisten



## 23 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

Ok dann bleibt es bei der Map 
Danke!


----------



## Andi_CH (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

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 (19. Mai 2011)

> 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.
> ...


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 (19. Mai 2011)

Zyklenfreiheit kann man durch Topologische Sortierung nachweisen.


----------



## 23 (20. Mai 2011)

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 (20. Mai 2011)

23 hat gesagt.:


> 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 (20. Mai 2011)

> 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 (21. Mai 2011)

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


----------



## maki (21. Mai 2011)

23 hat gesagt.:


> 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.


----------

