Zirkulare Abhängigkeiten überprüfen

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

THX 1138

class Vertex
{
public:
    void add_edge( Vertex target );
    void remove_edge( Vertex target );
private:
    Ding& das_ding;
    std::vector<Vertex*> edges;
};

class adjacency_list
{
public:
// Ein paar nette Methoden spendieren
    void add_vertex( Vertex vert );
    void remove_vertex( Vertex vert );    // Entfernt vert und seine edges
    void clear_vertex( Vertex vert );     // Entfernt nur die edges von vert
    void add_edge( Vertex source, Vertex target );
    void remove_edge( Vertex source, Vertex target );

private:
    std::vector<Vertex*> vertices;
};

// Iteratoren fehlen noch

Oder so ähnlich, am besten als Template