Logische Feedback-Detektion -> wie lösen bei Graphen?

Hallo,

ich habe n-Objekte mit jeweils n-Eingängen und n-Ausgängen die vom Anwender beliebig miteinander verschaltet werden können (Ausgänge zu Eingängen).

Keine Sorge, es geht jetzt nicht um topologische Sortierung des Graphen 😃

Vielmehr geht es mir darum, dass ich für meine topologische Sortierung die Anzahl der Eingänge pro Objekt ermitteln muss die einem logischem Feedback unterliegen.

Im Bild habe ich dies einmal an einem Graphen dargestellt. Der Ausgang 1 des Objektes G läuft über das Objekt F wieder auf den Eingang 2 des Objektes G. Die Anzahl betroffener Eingänge für G ist also 1.

Device ist die Basisklasse für alle Objekte und enthält n-Eingangsobjekte und n-Ausgangsobjekte. Die Eingänge und Ausgänge sind jeweils Klassenobjekte die eine Referenz auf ihr Device halten, so dass jederzeit ein Rückschluss möglich ist.

Um nun die "eigenen" Feedbacks (Ausgang des Objektes zeigt auf einen Eingang des eigenen Objektes) zu ermitteln gehe ich wie folgt vor:

int Device::GetNumFeedbackDetectedInputs()
{
	int numFeedbackDetectedInputs = 0;
	for (int outputNum = 0; outputNum < GetNumOutputs(); outputNum++)
	{
		if (m_pOutputs[outputNum]->GetIsConnected())
		{
			Device* pDevice = m_pOutputs[outputNum]->GetDevice();
			// Feedback verursacht durch eigenes Device
			if (pDevice == this)
				numFeedbackDetectedInputs++;
			else
			{
				// Hier iterativ?
				// for (int outputNumDevice = 0; outputNumDevice < pDevice->GetNumOutputs(); outputNumDevice++)
				// {
				// 	pDevice->GetOutput(outputNum)->...
				// }
			}
		}
	}
	return numFeedbackDetectedInputs;
}

Wie aber löse ich das nun mit der beliebigen Anzahl an angeschlossenen Devices je Ausgang, die ja wiederum n-Ausgänge haben (können)? Das muss ja irgendwie iterativ geschehen, bloß wie am geschicktesten?

LG
Matze

Hi Tweak,

also willst du in gerichteten Graphen nach Zyklen suchen? Dann mach das doch 😃 Geht im Grunde so ähnlich wie die topologische Sortierung, die du ja bereits erwähnt hast.

Oder wonach suchst du?

beste Grüße
zommi

Hallo Tweak,

pack den Knoten, dessen Feedback-Eingänge du ermitteln willst, in eine ansonsten leere Queue.

Hol dir nun das (aktuell) erste Element aus der Queue und ermittle der Reihe nach alle Ausgänge. Für jeden Ausgang, den du findest, prüfst du, ob der verbundene Knoten bereits besucht wurde. Wenn ja, dann überspringst/ignorierst du diesen Ausgang. Wenn nein, prüfst du, ob der verbundene Knoten mit dem zu untersuchenden Knoten übereinstimmt. Wenn ja, erhöhst du die Anzahl der Feedback-Eingänge um eins. Wenn nein, markierst du den Knoten als besucht und packst ihn ans Ende der Queue.

Und nun geht es mit dem jetzt ersten Element der der Queue weiter, solange bis die Queue leer ist.

Wie man erkennt, wir der zu untersuchende Knoten selbst nie als besucht markiert (landet aber trotzdem nie erneut in der Queue), aber das ist Absicht, denn die Anzahl der Feedback-Eingänge soll ja jedes mal erhöht werden, wenn er erreicht wird.

herbivore