Rekursive Suche in einem Netz

[Saheeda]

Hallo,

ich habe ein konzeptionelles Problem. Ich möchte ein Netz aufbauen und dieses rekursiv durchsuchen. Jeder Knoten hat 0-3 Kindknoten.
Ich habe im Backend außerdem eine Datenbank, in welcher u.a. die Beziehungen der Knoten gespeichert sind.
Der Root liegt genau im Zentrum des Netzes, drumherum sind kreisförmig in "Schichten" die Kindknoten angeordnet. Kindknoten können entweder auf derselben Schicht oder eine darunter liegen. Jeder Knoten kennt seine Schicht und seine Kinder, aber nicht seine Eltern.

Dadurch entstehen aber auch solche Beziehungen, die unweigerlich zu Endlosschleifen führen werden:
Knoten A ist ein Kind von Knoten B.
Knoten B ist ein Kind von Knoten A.

Mir fällt momentan nur eine Lösung für dieses Dilemma ein:
Ich gebe jedem Knoten ein Feld "visited" mit und gebe nach der Suche den Befehl, in der Datenbank alle Werte wieder auf false zu setzen.


Gibts dafür bessere Möglichkeiten?

 

[CptSocket]

Hoi Saheeda

Bei der Lösung mit dem visited-Flag sehe ich das Problem, dass du nicht parallel Suche kannst. (Ansonsten weisst du nicht mehr, zu welcher Suche das Flag gehört. Ok, du könntest anstelle eines Flags einen 'Suche-Identifier' verwenden, aber dann wirds kompliziert.

Was soll das Resultat der Suche sein - der/die Knoten welche die Suchbedingungen erfüllen oder der Pfad vom Root zum Knoten?
Was spricht dagegen, auch die Rückwärts-Beziehung zu hinterlegen?


Freundliche Grüsse
CptSocket

 

[Saheeda]

Bei der Lösung mit dem visited-Flag sehe ich das Problem, dass du nicht parallel Suche kannst. (Ansonsten weisst du nicht mehr, zu welcher Suche das Flag gehört. Ok, du könntest anstelle eines Flags einen 'Suche-Identifier' verwenden, aber dann wirds kompliziert.

Wie meinst du das mit parallel? Multithreading?
Wie würde das mit dem Identifier grob aussehen?

Was soll das Resultat der Suche sein - der/die Knoten welche die Suchbedingungen erfüllen oder der Pfad vom Root zum Knoten?

Beides. Mehr oder weniger.

Innerhalb des Netzes sollen einzelne Knoten als "aktiviert" oder "deaktiviert" markiert werden können, wird ein früherer Knoten deaktiviert, sollen aber auch alle andern, die noch dran hängen ebenfalls deaktiviert werden:

z.B., der Benutzer bewegt sich entlang: A -> B -> C -> D -> E
wenn jetzt C deaktiviert wird, sollen auch D und E als deaktiviert gelten.

Ich hab auch schon überlegt, das bidirektional zu machen, weiß aber momentan noch nicht, inwiefern das mein "Kreisproblem" löst:

public void visitChildren(){
   for(Node n : this.children){
      if(this.parents.contains(n){
          //do nothing
      } else {
       n.visitChildren();
      }
    }
}

Die Abfrage klappt ja nur, wenn beide direkt nebeneinander stehen. Sowas: "A ist Kind von B ist Kind von C ist Kind von A" geht wieder schief.


Achja, wir reden hier von insgesamt ca. 20 Knoten, ich kann also auch mit einer etwas weniger performanten Lösung leben.

 

[CptSocket]

Ich habe die Aussagen, dass das Netz in der Datenbank gepeichert ist und dass bei der Suche mit allenfalls einem visited-Feld gearbeitet werden soll so verstanden, dass dieses visited-Feld auch in der Datenbank hinterlegt werden soll?

Falls nein kannst du die Aussage mit dem Identifier ignorieren (dein Codebeispiel deutet darauf hin, dass du Programmatisch suchen möchtest?)
Falls ja und falls es möglich sein soll, mehrere Knoten parallel zu suchen, müsstest du dir merken, für welche Suche der Knoten bereits visited wurde. => in diesem Fall müsstest du dir einen Identifier ala 'Suche1' oder 'Suche2' merken.


Wegen der Rückwärtsbeziehung- würde folgendes Szenario klappen?
- Jeder Knoten kennt diejenige Beziehung zu den Eltern, welche am 'direktesten' zum Root führt
- Du suchst den Knoten, welcher die Bedingungen erfüllt
- Über die Beziehung zu den Eltern suchst du den Pfad heraus


Freundliche Grüsse
CptSocket

 

[Saheeda]

Das heißt, dass ich keine Liste von Parents angebe, sondern jeweils nur einen?

Ich werde mal versuchen, das umzusetzen und berichten, ob es funktioniert. Es kann aber eine Weile dauern, da ich eigentlich erstmal am Frontend bastel, mir das Problem aber keine Ruhe lässt.

 

[CptSocket]

Ja würde ich so machen. Die Frage ist halt, wie genau die Aufgabenstellung ist...

Wenn du alle Parents erfassen möchtest, könntest du auch pro Parent die 'Wegkosten' zum root zusätzlich angeben. (Also z.B. über Parent1 ist der Node 2 Schritte vom root weg, über Parent2 7 schritte. Dann kannst du entscheiden, welchen weg du Navigieren möchtest. Diese Lösung ist aber einiges komplizierter, vor allem musst du bei zirkulären Wegen verhindern, dass du in einen loop gerätst. Wenn du nur den schnellsten Weg zu root erfasst, hast du dieses Problem nicht.


Freundliche Grüsse
CptSocket