iterator example

[Neil Zanella]

Hello,

Just thought I would post a small iterator example for traversing the
nodes of a directed acyclic graph. Comments on class design and style
or other are welcome.

#include <iostream>
#include <vector>
#include <queue>

class Node {
public:
class BFSDAGIterator {
public:
BFSDAGIterator(Node *node): current(node) { }
BFSDAGIterator &operator++() {
expand_fringe();
current = fringe.empty() ? 0 : fringe.front();
fringe.pop();
return *this;
}
Node *operator*() { return current; }
private:
void expand_fringe() {
for (size_t i = 0; i < current->children.size(); i++)
fringe.push(current->children);
}
Node *current;
std::queue<Node *> fringe;
};
Node(int value = 0): value(value) { }
void setValue(int value) { this->value = value; }
int getValue() const { return value; }
Node *addChild(int value = 0) {
Node *node = new Node(value);
children.push_back(node);
return node;
}
private:
int value;
std::vector<Node *> children;
};

int main() {
Node *node1 = new Node(1);
Node *node2 = node1->addChild(2);
Node *node3 = node1->addChild(3);
node2->addChild(4);
node2->addChild(5);
node2->addChild(6);
node3->addChild(7);
for (Node::BFSDAGIterator it(node1); *it; ++it)
std::cout << (*it)->getValue() << std::endl;
}

 

[Siemel Naran]

Just thought I would post a small iterator example for traversing the
nodes of a directed acyclic graph. Comments on class design and style
or other are welcome.

#include <iostream>
#include <vector>
#include <queue>

class Node {
public:
class BFSDAGIterator {
public:
BFSDAGIterator(Node *node): current(node) { }
BFSDAGIterator &operator++() {
expand_fringe();
current = fringe.empty() ? 0 : fringe.front();
fringe.pop();
return *this;
}
Node *operator*() { return current; }
private:
void expand_fringe() {
for (size_t i = 0; i < current->children.size(); i++)
fringe.push(current->children);
}
Node *current;
std::queue<Node *> fringe;
};
Node(int value = 0): value(value) { }
void setValue(int value) { this->value = value; }
int getValue() const { return value; }
Node *addChild(int value = 0) {
Node *node = new Node(value);
children.push_back(node);
return node;
}
private:
int value;
std::vector<Node *> children;
};

int main() {
Node *node1 = new Node(1);
Node *node2 = node1->addChild(2);
Node *node3 = node1->addChild(3);
node2->addChild(4);
node2->addChild(5);
node2->addChild(6);
node3->addChild(7);
for (Node::BFSDAGIterator it(node1); *it; ++it)
std::cout << (*it)->getValue() << std::endl;
}

This looks very good. It looks like a breadth-first iterator. So it will
print: 1,2,3,4,5,6,7. Right?

It seems you might be missing a friend declaration, because
Node::BFSDAGIterator needs access to Node::children. Maybe operator* should
return the value? Finally, copying a BFSDAGIterator looks expensive, and
algorithms usually pass iterators by value to other algorithms, so if this
proves to be a bottleneck then how will you deal with it?

 

[Dave Townsend]

I couldn't get this to compile, "children" is a private member
and can't be accessed.

I think there is a bug in this, in BFS, don't you have to keep track
of the nodes you've visited so you don't visit them again (cycles).

(oh, I see it only handles acylics...).

dave