Zirkuläre Abhängigkeiten zwischen Objekten

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Deever
User
Beiträge: 15
Registriert: Samstag 30. Juli 2005, 12:46

Hey Amigos, wie geht's?

Ich habe hier ein Dictionary mit folgendem Aufbau:

Code: Alles auswählen

{
obj1name: [obj2name, obj6name],
obj2name: [objXname],
obj6name: [obj5name, ...],
obj5name: [obj1name, ...]
...
}
Jetzt möchte ich dieses dict nach zirkulären Referenzen durchsuchen und die Ringe in einer Liste speichern. Das Ergebnis soll also sein:

Code: Alles auswählen

[
[obj1name, obj6name, obj5name],
...
]
Gibt es hierfür einen einfachen, schnellen Algorithmus? Ich hab das bisher über einen Stack gelöst, den ich immer zuerst durchsuche, bevor ich in die nächste Rekursion absteige, aber irgendwie haut das nicht hin!

Bei den Elementen der Wertelisten im dict und denen in den Ergebnislisten handelt es sich in Wirklichkeit nicht um Strings, sondern um eigene Objekte, aber das krieg ich dann schon noch hin! ;)

Vielen Dank für eure Antworten!
Gruß,
/dev
BlackJack

Kannst Du Aussagen über die zu erwartenden Kreise treffen? Zum Beispiel ob sie sich überschneiden können oder nicht?

Ein Ansatz wäre es vielleicht alle Knoten zu entfernen, die nicht in einem Kreis sind, also keine eingehenden Kanten enthalten. Was dann am Ende übrig bleibt, müssen dann ja Knoten in Kreisen sein. Wie man die dann auflistet hängt von der ersten Frage oben ab.
Deever
User
Beiträge: 15
Registriert: Samstag 30. Juli 2005, 12:46

Wow, das nennt sich aber eine prompte Antwort! Danke. :)

Kreise? Kanten?
Nein, ich meinte eigentlich Ringe. Jedes Objekt kann theoretisch indirekt auf sich selbst zeigen und so Anfang und Ende eines Ringes sein. Allerdings kann ein Objekt auch in mehreren Ringen enthalten sein. Auch gibt es Objekte, auf die keine anderen zeigen, die also in keinem Ring enthalten sind.

Gruß,
/dev
BlackJack

Du meintest eigentlich Kreise in einem gerichteten Graphen. So heisst das jedenfalls in der Graphentheorie was Du da suchst. Und dort (Graphentheorie) solltest Du auch nach Lösungen suchen.

Also können sich die Kreise überschneiden. Ein vielleicht erster Schritt zum Ziel wäre es wahrscheinlich alle Knoten zu entfernen die nicht Teil eines Kreises sind. Also Knoten ohne eingehende Kanten. Solange bis es keine solchen mehr gibt. Alle Knoten die übrig bleiben, müssen dann ja Teil irgend eines Kreises sein.

Da kann man sich dann einen beliebigen Knoten nehmen, einen Kreis ermitteln in dem der steckt und alle beteiligten Knoten, die nur eine eingehende Kante haben, entfernen. Das wiederholt man solange bis alle Kreise identifiziert und abgebaut sind.
Deever
User
Beiträge: 15
Registriert: Samstag 30. Juli 2005, 12:46

BlackJack hat geschrieben:Da kann man sich dann einen beliebigen Knoten nehmen, einen Kreis ermitteln in dem der steckt
Und genau hier komme ich nicht weiter. Das Problem sind nicht nur die eingehenden Kanten, sondern auch die abgehenden.

Gruß,
/dev
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Wenn lediglich die Knoten, aber nicht die Kanten in mehreren Kreisen vorkommen können, dann wäre das evtl. eine Lösung:

Code: Alles auswählen

dic = {1: [2, 6],
       2: [3],
       3: [4],
       4: [2],
       5: [1],
       6: [5]
      }

def rec(key):
    for dest in dic.get(key, []):
        if dest in curr:
            curr_ = curr[curr.index(dest):]
            result.append(curr_)
            # Kreis loeschen funktioniert nur,
            # wenn Kanten nicht in mehreren Kreisen enthalten sein koennen
            for i, s in enumerate(curr_[:-1]):
                dic[s].remove(curr_[i + 1])
            dic[curr_[-1]].remove(curr_[0])
        else:
            curr.append(dest)
            rec(dest)
            curr.pop()

result = []
for src in dic:
    curr = [src]
    rec(src)
print result
MfG
HWK

Edit: Erste Version hat sich z.B. bei dem obigen Beispiel-Dic aufgehängt.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

So jetzt noch eine Variante, die hoffentlich auch funktioniert, wenn die Kanten in mehreren Kreisen enthalten sein können:

Code: Alles auswählen

dic = {1: [2, 6],
       2: [3],
       3: [4],
       4: [2, 6],
       5: [1, 4],
       6: [5]
      }

def rec(key):
    for dest in dic.get(key, []):
        if dest in curr:
            curr_ = curr[curr.index(dest):]
            t = curr_.index(min(curr_))
            # Kleinstes Element des Kreises immer als erstes
            curr_ = curr_[t:] + curr_[:t]
            result.add(tuple(curr_))
        else:
            curr.append(dest)
            rec(dest)
            curr.pop()

result = set()
for src in dic:
    curr = [src]
    rec(src)
print result
MfG
HWK
Deever
User
Beiträge: 15
Registriert: Samstag 30. Juli 2005, 12:46

Grrr...ich hab, um die Ringe nicht mehrmals in der Ergebnisliste zu speichern, natürlich nicht ein set verwendet und stattdessen ein list dafür mit irgendnem schwachsinnigen "Algrothismus" zu Schrott verarbeitet! :(

Vielen Dank für deine Erleuchtung! :)
Gruß,
/dev
Antworten