Avoid Circular referencing to endless loop

[Milhouse (Gast)]

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.

[Johann L. (gjlayde)]

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.

[Milhouse (Gast)]

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

[dunno.. (Gast)]

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

[Milhouse (Gast)]

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