Zirkulare Abhängigkeiten überprüfen

Thomas ** 0

Hallo, mir fällt irgendwie kein Einsatz ein. Z.B.:

struct Ding {
    int num;
    std::vector<Ding const*> abhaengigvon;
};

Davon hab ich ganz viele in einem Container. Wie könnte ich prüfen ob hier mehrere Dinge untereinander abhängig sind? Also z.B:

A abhängig von B
B abhängig von C
C abhängig von A
--> Boom!

Mein aktueller Ansatz ist es einfach für jedes Ding die Abhängigkeit zu prüfen. Wenn nicht erfüllt erstmal liegen lassen. Das mache ich solange bis entweder
a) alle Dinge aktiviert sind
b) in einem Durchlauf nichts aktiviert werden konnte --> Fehler.

Diesen Fehler möchte ich aber noch ausgeben können, mit einer Meldung a la "Could not continue: A depends on B depends on C depends on A" oder so.

Thomas ** 0

Nun ist mir was eingefalle, aber ich weiß nicht ob es klappt (hab noch keine lauffähige Version zum testen):

Ich implementiere eine Methode dependsOn(Ding* ding);
Diese schaut zuerst die eigenen Abängigkeiten durch, und wenn dort "ding" nicht drin ist fragt es alle seine Abhängigkeiten. Dadurch frage ich aber unter Umstände manche Dinge doppelt ab:

A braucht B
A braucht C

B und C brauchen D

Nun würde A bei B und C nachfragen, und die fragen beide einmal D. Bei 10 Dingen sollte das nichts ausmachen, aber wenn ich mir das beim Protagetree vorstell glaub ich dass es was ausmacht.

volkard

Thomas (: schrieb:

Hallo, mir fällt irgendwie kein Einsatz ein. Z.B.:
struct Ding {
    int num;
    std::vector<Ding const*> abhaengigvon;
};

über sowas denke ich auch gerade nach. bei mir ein kleines build-system (make-ersatz).

Thomas (: schrieb:

Davon hab ich ganz viele in einem Container. Wie könnte ich prüfen ob hier mehrere Dinge untereinander abhängig sind? Also z.B:
A abhängig von B
B abhängig von C
C abhängig von A
--> Boom!

ich denke gleich dran, die transitive hülle zu berechnen. außerdem http://de.wikipedia.org/wiki/Zyklus_(Graphentheorie)

aha. http://de.wikipedia.org/wiki/Topologische_Sortierung fürs vorher-problem. naja, das erledisgt du ja schon nebenbei mit deinem weiteren vorgehen.

Mein aktueller Ansatz ist es einfach für jedes Ding die Abhängigkeit zu prüfen. Wenn nicht erfüllt erstmal liegen lassen. Das mache ich solange bis entweder
a) alle Dinge aktiviert sind

jo, klingt sehr gut. man müßte mal genau prüfen, ob das zurückastellen billig ist. zum beispiel in einer queue. kann man dann n nichtzyklische jobs in O(n) abfragen? nicht, daß einem bei 10000 jobs der rechner stehenbleibt.

b) in einem Durchlauf nichts aktiviert werden konnte --> Fehler.

ich hab zwar nicht das konzept des "Durchlaufs", aber b) ist bei mir auch höchst elegant.

Diesen Fehler möchte ich aber noch ausgeben können, mit einer Meldung a la "Could not continue: A depends on B depends on C depends on A" oder so.

und jetzt erst die "Zykluserkennung mittels Tiefensuche".

volkard

Thomas (: schrieb:

Diese schaut zuerst die eigenen Abängigkeiten durch, und wenn dort "ding" nicht drin ist fragt es alle seine Abhängigkeiten. Dadurch frage ich aber unter Umstände manche Dinge doppelt ab:
A braucht B
A braucht C
B und C brauchen D
Nun würde A bei B und C nachfragen, und die fragen beide einmal D. Bei 10 Dingen sollte das nichts ausmachen, aber wenn ich mir das beim Protagetree vorstell glaub ich dass es was ausmacht.

dann flute dein netz von A aus, und schau, von wo aus zuerst nach A wasser reinläuft.

//ungetestet
hast einen 
queue<Knoten*> kueste={A}
und eine
set<Knoten*> trocken=alleKnotwenDieEsGibt

in jedem durchlauf machste.. ups, hab ja schon wieder die durchläüfe weggemacht durch ne kontinuierliche schleiife, ich schelm. 

machst halt

while k=kueste.pop()
   trocken.remove(k)
   foreach n in k->nachbar
      if n==A 
         return gefunden!!!
      else if trocken.has(n)
         kueste.push(n)
         trocken.remove(n)
      endif
   endfor
endwhile

machste bool trocken in die knoten rein, brauchste das set nicht. und mit Knoten* woherKonntsWasser kannste dann von A aus den kreis zurückgehen bis wieder A kommt und anzeigen.

Thomas ** 0

Danke für die Antworten, hat michs ehr weiter gebracht!

Wenn du deine Datenstruktur anpasst, kannst du sehr schnelle Graph Scanning Algorithmen verwenden, wie z.B. solche die auf Breitensuche basieren, also O(Kanten + Ecken) Laufzeit haben. Dazu sollte der Graph in Adjazenzlisten Form vorliegen.
Details z.B. bei Wikipedia.

MfG

volkard

Mr.Know-it-all schrieb:

Wenn du deine Datenstruktur anpasst, kannst du sehr schnelle Graph Scanning Algorithmen verwenden, wie z.B. solche die auf Breitensuche basieren, also O(Kanten + Ecken) Laufzeit haben.

das ist ja fein.
wie ist nochmal die komplexität des von mir angegebenen algos? auch O(Kanten+Ecken)? das schien mir so beim einfach mal abschätzen. wo hab ich mich vertan?

Dazu sollte der Graph in Adjazenzlisten Form vorliegen.
Details z.B. bei Wikipedia.

detailangabe abgelehnt. schon ein wenig genauer, falls du hilfreich helfen willst. und ich widerspreche mal prophylaktisch.

THX 1138

volkard, meinst du sowas?
BGL File Dependency Example

volkard

1310-Logik schrieb:

volkard, meinst du sowas?
BGL File Dependency Example

ja, so ähnlich.

THX 1138

Naja, da stehts doch:

depth-first search

Complexity
The time complexity is O(E + V)

Die Boost Adjazenzliste ist einfach zu benutzen.
Und wenn dir BGL nicht gefällt, kannst es ja nachbauen. Ist aber sehr nett generisch aufgebaut.

volkard

1310-Logik schrieb:

Naja, da stehts doch:

depth-first search
Complexity
The time complexity is O(E + V)

Die Boost Adjazenzliste ist einfach zu benutzen.
Und wenn dir BGL nicht gefällt, kannst es ja nachbauen. Ist aber sehr nett generisch aufgebaut.

da steht jetzt auch nicht drin, daß man adjazenzlisten nehmen sollte, um O(E+V) zu erreichen.

THX 1138

BGL Docu schrieb:

The advantage of this matrix format (adjacency matrix Anm.d.Q.) over the adjacency list is that edge insertion and removal is constant time. There are several disadvantages. The first is that the amount of memory used is O(V2) instead of O(V + E) (where E is the number of edges). The second is that operations that traverse all the out-edges of each vertex (such as breadth-first search) run in O(V2) time instead of O(V + E) time for the adjacency list. In short, it is better to use the adjacency_matrix for dense graphs (where E is close to V2) and it is better to use adjacency_list for sparse graphs (where E is much smaller than V2).

Quelle

volkard

1310-Logik schrieb:

BGL Docu schrieb:

The advantage of this matrix format (adjacency matrix Anm.d.Q.) over the adjacency list is that edge insertion and removal is constant time. There are several disadvantages. The first is that the amount of memory used is O(V2) instead of O(V + E) (where E is the number of edges). The second is that operations that traverse all the out-edges of each vertex (such as breadth-first search) run in O(V2) time instead of O(V + E) time for the adjacency list. In short, it is better to use the adjacency_matrix for dense graphs (where E is close to V2) and it is better to use adjacency_list for sparse graphs (where E is much smaller than V2).

Quelle

immernochnicht steht da, daß man adjazenzlisten nehmen sollte, statt dem ursprünglichen

struct Ding { 
    int num; 
    std::vector<Ding const*> abhaengigvon; 
};

THX 1138

volkard schrieb:

immernochnicht steht da, daß man adjazenzlisten nehmen sollte, statt dem ursprünglichen
struct Ding { 
    int num; 
    std::vector<Ding const*> abhaengigvon; 
};

Was unterscheidet denn dieses Konstrukt von ner Adjazenzliste?

volkard

1310-Logik schrieb:

Was unterscheidet denn dieses Konstrukt von ner Adjazenzliste?

uups.
gar nichts.

THX 1138

volkard schrieb:

1310-Logik schrieb:

Was unterscheidet denn dieses Konstrukt von ner Adjazenzliste?

uups.
gar nichts.

Juhuu :p
Nein nur spass!
Die BGL Doku gibt übrigends auch sehr viel über Umsetzung der Graphentheorie in C++ her. Ist wirklich nett zu gebrauchen, und ähnlich aufgebaut wie die STL und die Algorithmen sind optimiert worden. Aber Du bist sicher mehr fürs selberbasteln

phlox81

1310-Logik schrieb:

volkard schrieb:

1310-Logik schrieb:

Was unterscheidet denn dieses Konstrukt von ner Adjazenzliste?

uups.
gar nichts.

Juhuu :p
Nein nur spass!
Die BGL Doku gibt übrigends auch sehr viel über Umsetzung der Graphentheorie in C++ her. Ist wirklich nett zu gebrauchen, und ähnlich aufgebaut wie die STL und die Algorithmen sind optimiert worden. Aber Du bist sicher mehr fürs selberbasteln

Wie wärs mit nem Beispiel?

THX 1138

phlox81 schrieb:

Wie wärs mit nem Beispiel?

Was meinst Du? Den Link weiter vorne zB?

1310-Logik schrieb:

BGL File Dependency Example

phlox81

1310-Logik schrieb:

phlox81 schrieb:

Wie wärs mit nem Beispiel?

Was meinst Du? Den Link weiter vorne zB?

1310-Logik schrieb:

BGL File Dependency Example

Naja, eher wie man aus

struct Ding {
    int num;
    std::vector<Ding const*> abhaengigvon;
};

so ne Liste macht. Oder hab ich da was falsch verstanden?
Müsste er jetzt für jedes Element von abhaengigvon eine Edge(this,abhaengigvon) erstellen?

THX 1138

Aso..

Du haust die Structs einfach in nen Vector, dann hast Du alle Abhängigkeiten von allen Vertices in einem.
Die Adjazenzliste sieht dann so aus:

[1] -> [3][5][7][8]
[2] -> [4][5][6]
[3] -> [1][2][8][9]
[4] -> [2][7]
//...usw

Bessere Abbildung auf http://www.tilman.de/uni/ws03/alp/adjazenz.php