Jedes Objekt eines Graphen durchgehen ?

Hallo, ich habe einen Graphen bei dem ein Objekt beliebig viele Childs und Parents haben kann.
Wie kann ich jedes Objekt eines solchen Graphen registrieren ?
Gibt es da einen Algorhitmus dafür ?

godlikebot

Das einfachste (aber nicht das schnellste) ist wohl:

std::list<Node*> ListOfAllNodes;

class Node
{
    std::list<Node*> Children;

    void Register()
    {
        ListOfAllNodes.push_back(this);
        for(std::list<Node*>::iterator it = Children.begin(); it != Children.end(); it++)
            (*it)->Register();
    }
};

In dem Fall wird das aber eine unendliche Prozedur , oder ?

angenommen, a ist child von b, b ist child von c ,und c ist child von a.

Dann wird zb. a.register aufgerufen. a.register ruft b.register auf, b.register ruft c.register auf, c.register ruft wieder a.register auf, und schon dreht sich es im kreis

life

bbocx schrieb:

In dem Fall wird das aber eine unendliche Prozedur , oder ?

angenommen, a ist child von b, b ist child von c ,und c ist child von a.

Dann wird zb. a.register aufgerufen. a.register ruft b.register auf, b.register ruft c.register auf, c.register ruft wieder a.register auf, und schon dreht sich es im kreis

dann mach noch nen if((*it)->notRegistered()) davor

Hab ich dann ne liste mit sämtlichen Knoten ?

Bashar

Da sollte sich mit Google einiges finden lassen. Stichworte Graphentraversierung, Depth-First, Breadth-First ...

prolog

Hi,

oder bgl benutzen ? Da hat man neben den graphen auch gleich die algos die auf denen arbeiten. Unter andrem eben breadth- und depth-first traversal wie bashar schon sagte. Um cyclen in graphen zu entdecken gibtz doch auch effiziente algos. Die bgl bedient sich auch des visitor-patterns .. also was du willst.

pumuckl

bbocx: vielleicht ein paar mehr einzelheiten: handelt es sich um einen gerichteten oder ungerichteten Graphen? (bei parent/child denkt man ja eher an einen gerichteten)
Ist der Graph zyklisch oder azyklisch?
eventuell bietet sich auch an, für deinen graphen eine Iteratorklasse zu schreiben...

phlox81

hm, boost::graph wäre da einen Blick wert.

Ansonsten, überleg dir, ob du das Register nicht direkt
Im Konstruktor machst, bzw. in einer FactoryKlasse für die Nodes.