Moinsen noch mal, ich habe eine Struktur nach dem Vorbild des Composition Pattern aufgebaut (habe hinterher spitz gekriegt, dass ich ein Pattern umgesetzt habe^^)https://www.tutorialspoint.com/design_pattern/composite_pattern.htm Der Witz besteht ja darin, dass ein Objekt eine Liste von Objekten seines eigenen Types hat - ich nenne sie mal "sibblingsList". In meinem Fall handelt es sich dabei um Zeiger eines Interface-Types "I_Graph" , nicht um die Instanzen selbst. Jetzt gibt es bei mir auf Grund der Anwendung eine Methode >Run(uint16_t* arg) die in den konkreten Implementierungen implementiert wird. Es gibt eine Implementierung des Interfaces "Node" und eine "Calc". "Calc"´s führen eine tatsächliche Rechnung aus wärend "Node"´s bei Aufruf von "Run()" ihre "sibblingsList" durchitterieren und dort "Run()" aufrufen. >>Ich habe ein Interface als Obbjekt und sibblingsList Typ genommen, weil ich in der selben Liste "Node"´s und "Calc"´s halten möchte um eine flexible Berechnungsstruktur aufbauen zu können. >>Punktus Knacktus: >Es besteht die Gefahr, dass man in der sibblingsList im Kreis >referenziert. >Also Instanz A ruft Instanz B ruft Instanz A >>Frage: >Was wäre eurer Meinung ein Ansatz, diese Gefahr zu umgehen? >Nennenswert dabei ist sicher, dass es sich um ein System handelt, welches >vom Nutzer bedient wird, es werden keine Abertausend Nodes existieren. Ein >paar dutzend wharscheinlich. >Von den Ideen die mir gekommen sind, finde ich folgende am elegantesten: Es wird im Interface "I_Graph" eine Methode "DetectLoop(I_Graph* loopTestPtr) vorgesehen. In der Methode wird das Argument mit der eigenen Referenz verglichen. Sind sie identisch, wäre eine Loop gefunden. Soll in eine Node-Instanz("Host-Node" ) die Referenz eines einexistierenden Node hinzugefügt werden, wird zunächst die DetectLoop() im "Host-Node" aufgerufen, mit der Adresse des hinzu zu fügenden Nodes als Argument. Existiert der Node bereits im "Einzugsgebietes" des Host-Nodes würde oben beschriebene DetectLoop() Methode das detektieren.
Deine Frage ist die, wie man beim Graph-Traversing Zykel vermeidet. Einfacher Fall ist der, wenn der Graph keine Zykel enthät und das aufgrung der Konstruktion auch bekannt ist. Beispiel sind Bäume und als Spezialfall Listen. Falls man die Zykelfreiheit nicht nachweisen kann, kann man z.B. vorgehen wie ein Garbage-Collector: Zunächst werden alle Knoten als "nicht-bereist" markiert. Gelangt man zu einem Knoten, markiert man diesen als "bereist" und lässt alle bereits bereisten Nachbarknoten links liegen, während die nicht-bereisten rekursiv betreten werden.
:
Bearbeitet durch User
>Falls man die Zykelfreiheit nicht nachweisen kann...
Ok, das klingt in der Quintessenz für mich danach, das sich bei solchen
Graphen eine Loopfreieiheit tatsächlich nur durch ein recht
laufzeitaufwändiges "Durchwander-Verfahren" nachweisen lässt. (?)
PS.: auch Danke für das Stichwort "Graph-Traversing"
Ich hätte es wahrscheinlich auch beim einfügen geprüft, das es keinen kreis gibt.. Kommt letztlich wohl drauf an, ob du öfter ausführst, oder die referenzen änderst..
>Ich hätte es wahrscheinlich auch beim einfügen geprüft, das es keinen >kreis gibt.. Auf dem Weg bin ich jetzt, ich bau den Graph ja zur Laufzeit zusammen und muss keinen fertigen Salat analysieren. Ich hab jetzt was mit einer rekursiven Aufrufsturktur gemacht, was auf den ersten Blick zu funktionieren scheint. Bei einem ein zu fügenden Kandidaten, wird die FindLoop(*dest) Methode aufgerufen, die als Argument die Adresse des "Zielhosts" bekommt >int16_t Node_Junction::FindLoop(Node_I* dest) >{ > if(dest== this) return EXIT_FAILURE; > for(uint16_t i=0; i<myChilds.Count(); i++) > { > if(myChilds.At(i)->FindLoop(dest) == EXIT_FAILURE) return EXIT_FAILURE; > } > return EXIT_SUCCESS; >} Start der Sache ist >if(candi->FindLoop(myNodeJuncRef) == EXIT_FAILURE) qDebug() << "Loop avoided"; >>else __EINFÜGEN__
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.