graphen implementierung

miller_m

ich möchte demnächst einen gerichteten azyklischen graphen implementieren, hauptaufgaben sollten schnelles traversieren sein und dem user die möglichkeit geben die nodes nach seinen wünschen anzupassen. es wird sich um ca. 20 verschiedene node typen handeln. ich vermute mal mehrere hundert childs und eine riesige baumtiefe. der user sollte die möglichkeit haben bestimmte verhaltensweisen an den nodes zu ändern dabei sind mir drei möglichkeiten eingefallen.
1. visitor, der mir nicht so zusagt den die erweiterung der hierachie stellt sich als schön aufwenig dar und wenn der user nur bestimmte nodes ändern möchte muss er trotzem einen riesigen vistor schreiben für trivale aufgaben.
2. callbacks jedes node besitzt einen callback auf das von mir angebotene verhalten, falls der user diese nicht wünscht kann er einfach anderes machen.
beide besitzen den nachteil das der user nicht direkt auf die attribute zurückgreifen kann sondern er alles über getter und setter machen muss. gibt es hierfür eine lösung?
3. jedes node würde von einer policy, in dem alle attribute definiert sind, und basenode erben somit müsste der user nur eine neues node einführen in der wieder von der policy und dem basenode geerbt wird und die pure virtuelle methode der basisklasse entsprechend überschreiben.
zum schnellen traversieren fällt mir eigentlich nur ein die childnodes in einem hash container zu speichern. was mit völlig egal ist, ist die compiletime, vielleicht fällt jemanden dazu etwas ein. long message short ich suche möglichst viele ansätze, gedanken, ideen, papers, bücher, etc.

Zu 2..
Es lebe der Funktions-Operator! Da hat man wenigens ein Objekt in der Hand und muss nicht mit Funktionspointern arbeiten.
Das Arbeiten mit Get und Set-Funktionen würde ich generell empfehlen auch wenn es aufwendiger ist. Ansonsten macht man nur dem das Leben schwer, der das ganze nachher warten muss.

miller_m

Mathias schrieb:

Zu 2..
Es lebe der Funktions-Operator! Da hat man wenigens ein Objekt in der Hand und muss nicht mit Funktionspointern arbeiten.

einen wirklichen vorteil sehe ich nicht. ich würde sowieso beim aufruf der callback einen pointer auf das node mit übergeben. somit wäre es egal ob es jetzt eine funktion oder ein funktionsobjekt ist.

Mathias schrieb:

Das Arbeiten mit Get und Set-Funktionen würde ich generell empfehlen auch wenn es aufwendiger ist. Ansonsten macht man nur dem das Leben schwer, der das ganze nachher warten muss.

ich verwende nur sehr ungern getter und setter da dieses meiner meinung nach
an oop vorbei geht.

Schau dir mal die boost::graph-Library an. Die hat eigentlich alles was man so brauchen könnte.

miller_m

da ich gerne den graphen selber implementieren (nicht c&p) möchte bringt mich boost nicht sehr weiter.

DarkSchwabe

Hallo,

ich will im Zuge meiner Diplomarbeit auch einen Graph in einer MFC-Anwendung darstellen. Der Graph wird azyklisch sein und gerichtet (obwohl das eigentlich egal ist, denke ich).
Ein Knoten repräsentiert ein Ereignis und hat eine bestimmte Wahrscheinlichkeit daß es eintritt. Diese Wahrscheinlichkeit wird mit einer Zahl an der Kante repräsentiert. In dem Knoten steht der Name des Ereignisses.

Nun zu meiner Frage:
Um hier einen schönen Graphen zu bekommen kann man verschiedene Algorythmen benutzen, die ich zwar noch nicht kenne, aber wo es soweit ich weiß eine Menge literatur gibt. Sollte also hoffentlich nicht sooo schwer sein.
Aber wie kann ich denn in der MFC soetwas darstellen? Also mehr oder weniger zeichnen? Ich habe die Knotenkoordinaten und die für die Kanten, aber wie kann ich das dann visualisieren? Brauche ich dafür eine externe Lib? Oder geht das auch so einigermaßen "einfach"?

Hoffe,daß mir da jemand weiterhelfen kann

Danke

Pellaeon

abs ins MFC-Forum^^

Mit CClientDC dc(this) bekommst du einen Device Context auf dein Fenster, In der MSDN nach CDC::ClassMembers suchen, da stehen Zeichenfunktionen die du nutzen kannst.
Musst deine Daten aber irgendwo speichern und in der OnPaint-Methode(oder OnDraw je nachdem was du benutzt) den Graphen immer neu zeichnen lassen wenn eine WM_PAINT-Nachricht kommt.

miller_m

DarkSchwabe schrieb:

Der Graph wird azyklisch sein und gerichtet (obwohl das eigentlich egal ist, denke ich).
Um hier einen schönen Graphen zu bekommen kann man verschiedene Algorythmen benutzen, die ich zwar noch nicht kenne, aber wo es soweit ich weiß eine Menge literatur gibt.

kannst du schon ein paar bücher, papers etc empfehlen? wenn ja, welche?

DarkSchwabe schrieb:

Also mehr oder weniger zeichnen? Ich habe die Knotenkoordinaten und die für die Kanten, aber wie kann ich das dann visualisieren?

vielleicht http://www.graphviz.org/

DarkSchwabe

miller_m schrieb:

kannst du schon ein paar bücher, papers etc empfehlen? wenn ja, welche?

Nein leider noch nicht.Befasse mich erst seit der Woche mit dem Thema.Aber entweder diese oder aben dann nächste Woche werde ich na hoffentlich schon was gutes gefunden haben. Anhaltspunkte welche VErfahren es da gibt, bekommt man auch bei graphviz

miller_m schrieb:

vielleicht http://www.graphviz.org/

Das hab ich mir auchschon kurz angeschaut. Nur sieht es irgendwie so aus, als würde Graphwiz nur Bilder als Ergebnis liefern und vielleicht auch die Koordinaten. Aber an sich wohl keine Möglichkeit den GRaph als "Objekt" in MFC einzubinden. Als ActiveX oder was weiß ich.
Es gibt für dieses Graphviz allerdings verschiedene Viewer, die es eventuell möglich machen einen Graph als ein solches "objekt" ins MFC einzufügen. Weiß ich aber noch nicht. Ist irgendwie nicht so auf den ersten Blick zu sehen... vielleicht weiß da jemand genaueres

HumeSikkins

miller_m schrieb:

1. visitor, der mir nicht so zusagt den die erweiterung der hierachie stellt sich als schön aufwenig dar und wenn der user nur bestimmte nodes ändern möchte muss er trotzem einen riesigen vistor schreiben für trivale aufgaben.

Das erste Problem kannst du teilweise über das azyklische Visitor-Pattern lösen, das zweite in dem du in deinem Base-Visitor einfach alle visit-Methoden als noops implementierst. Wenn du im Base-Visitor außerdem noch eine "catch-all" visit-Methode (also eine für den Basistypen Node) implementierst, dann kannst du sogar neue Node-Typen hinzufügen ohne dass du alle konkreten Visitoren ändern musst. Dazu musst du für die visit-Methoden natürlich Überladung verwenden (statt explizite Namen wie visitFoo, visitBar einfach visit(Foo&), visit(Bar&)).

Sprich:

class Node;
class FooNode;
class BarNode;

class NodeVisitor {
public:
    virtual ~NodeVisitor() = 0 // NodeVisitor ist abstrakt

   // Default: Mache nichts
    virtual void visit(FooNode&) {}
    virtual void visit(BarNode&) {}

    // "catch-all" Methode
    virtual void visit(Node&) {} 
};
NodeVisitor::~NodeVisitor() {}

class User : public NodeVisitor // will nur bei FooNodes was machen
{
public:
    using NodeVisitor::visit; // alle Default-Impls in unseren Scope holen
    void visit(FooNode&) {
        ...
    }
}

Beispiel für einen azyklischen Visitor:

// Basisklasse für alle Besucher
// Achtung: Die Basisklasse enthält im Gegensatz zum zyklischen Visitor
// *keine* visit-Methoden.
class NodeVisitor {
public:
    virual ~NodeVisitor() {}
};

// Baseisklasse deiner Node-Hierarchie
class Node {
public:
    virtual void accept(NodeVisitor& v) = 0;
};

// Für jeden konkreten Node-Typ gibt es ein Visitor-Interface mit 
// genau einer visit-Methode
class FooNode;
class FooNodeVisitor {
public:
   virtual void visitFooNode(FooNode&) = 0;
};

// Die accept-Methode jedes konkreten Node-Typs prüft ob der übergebene
// Visitor vom Typ ConcreteNodeTypeVisitor ist.
class FooNode : public Node {
public:
   void accept(NodeVisitor& v) {
       if (FooNodeVisitor* fv = dynamic_cast<FooNodeVisitor*>(&v)) {
           fv->visitFooNode(*this);
       }
   }
}

class BarNode;
class BarNodeVisitor {
public:
   virtual void visitBarNode(BarNode&) = 0;
};

class BarNode : public Node {
public:
   void accept(NodeVisitor& v) {
       if (BarNodeVisitor* bv = dynamic_cast<BarNodeVisitor*>(&v)) {
           bv->visitBarNode(*this);
       }
   }
}

// konkrete Visitor-Typen erben nun von jedem Visitor-Interface das sie
// implementieren wollen:
class User : public NodeVisitor     // User ist ein Visitor...
           , public FooNodeVisitor  // der FooNodes besuchen will
{
public:
    void visitFooNode(FooNode& n) {...}
};

Alles in allem musst du hier zwar großen Aufwand betreiben, dafür hast du aber weniger Abhängigkeiten, so dass das Hinzufügen eines neuen Node-Typs nicht dazu führt, dass du alle konkreten Visitoren ändern musst.
Du musst dabei vorhandenen Code nicht ändern. Stattdessen musst du:
a) eine neue Klasse von Node ableiten.
b) für diese neue Klasse eine neue NodeVisitor-Klasse definieren.

miller_m

habe den visitor schon implementiert, doch war sehr unzufrieden damit, somit habe ich mir letzte mal den azyklischen angeschaut und dein azyklischer visitor (variante 1) gefällt mir sehr gut. dank dir