Avoid Circular referencing to endless loop

Milhouse Gast #5215016 
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.
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
Johann L. Persönliche Seite #5215058 
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.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Milhouse Gast #5215088 
>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"
Antwort Zitieren Bearbeiten Löschen Melden Danke
dunno.. Gast #5216553 
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..
Antwort Zitieren Bearbeiten Löschen Melden Danke
Milhouse Gast #5216888 
>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__
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 8 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.