C++

Forum

 
Iterative way to find cycles in tree

PattuX (8)
I have the following structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
using namespace std;

class node
{
public:
	node(string& const n = (string)"");
	virtual ~node();
	string get_name() const;
	void set_name(string& new_name);
	int get_nr_children() const;
	node* get_child(int i) const;
        ...
	void traverse_stack(ostream& str);
private:
	string name;
	vector<node*> children;


and I can't make traverse_stack work properly...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
  void node::traverse_stack(ostream& str) {
	vector<node*> visited;
	// no real stack, because I need to search in it
	vector<node*> stack;

	visited.push_back(this);
	stack.push_back(this);
	str << this->get_name() << endl;;

	int indent = 0;
	bool added_child = true;

	while (!stack.empty()) {
		node* top = stack.back();
		added_child = false;

		for (int i = 0; i < top->get_nr_children(); i++) {		
			// if (not added_child and child(i) not in visited)
			if (!added_child && find(visited.begin(), visited.end(), top->get_child(i)) == visited.end()) {
				indent++;
				for (int i = 0; i < indent; i++) {
					str << "    ";
				}
				str << top->get_child(i)->get_name() << endl;
				visited.push_back(top->get_child(i));
				stack.push_back(top->get_child(i));
				added_child = true;
			} else {
				// if (not added_child and child(i) in stack)
				if (!added_child && find(stack.begin(), stack.end(), top->get_child(i)) != stack.end()) {
					for (int i = 0; i <= indent; i++) {
						str << "    ";
					}
					str << top->get_child(i)->get_name() << " !!!Cycle detected!!!" << endl;;
				}
			}
		}
		if (!added_child) {
			stack.pop_back();
			indent--;
		}
	}
}


This is more of a general algorithmic problem, but I thought I'd still ask here.
The expected output should for example be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
node_4
    node_5
        node_6
            node_7
            node_8
        node_9
            node_10
            node_11
            node_4 !!!Cycle detected!!!
        node_12
            node_13
                node_14
                node_15
            node_16
                node_17
                node_18
    node_12
        node_13
            node_14
            node_15
        node_16
            node_17
            node_18
    node_4 !!!Cycle detected!!!


but actually is

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
node_4
    node_5
        node_6
            node_7
            node_8
        node_9
            node_10
            node_11
            node_4 !!!Cycle detected!!!
        node_12
            node_13
                node_14
                node_15
            node_16
                node_17
                node_18
    node_4 !!!Cycle detected!!!


So I am able to detect cycles oorrectly, but when a node appears twice in a tree in 2 different branches (so without causing an infinite tree in theory), it won't print it. I get why this is, but can't find a solution to this problem.
Also I want this to be iterative, I already got the recursive method.
In general I'd take any solution, but I'd prefer to modify my own of course :)
Last edited on
PattuX (8)
OP here, found a solution myself now. Sharing it, in case someone finds this thread and has the same problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
void node::traverse_stack(ostream& str) {
	vector<node*> visited;
	// no real stack, because I need to search in it
	vector<node*> stack;

	visited.push_back(this);
	stack.push_back(this);
	str << this->get_name() << endl;
	int indent = 0;
	bool added_child = true;

	while (!stack.empty()) {
		node* top = stack.back();
		added_child = false;

		for (int i = 0; i < top->get_nr_children(); i++) {
			// if (not added_child and child(i) not in visited)
			if (!added_child && find(visited.begin(), visited.end(), top->get_child(i)) == visited.end()) {
				indent++;
				for (int i = 0; i < indent; i++) {
					str << "    ";
				}
				str << top->get_child(i)->get_name() << endl;
				visited.push_back(top->get_child(i));
				stack.push_back(top->get_child(i));
				added_child = true;
			}
			else {
				// if (not added_child and child(i) in stack)
				if (!added_child && find(stack.begin(), stack.end(), top->get_child(i)) != stack.end()) {
					for (int i = 0; i <= indent; i++) {
						str << "    ";
					}
					str << top->get_child(i)->get_name() << " !!!Cycle detected!!!" << endl;
					visited.push_back(top->get_child(i));
				}
			}
		}
		if (!added_child) {
			stack.pop_back();
			for (int i = 0; i < top->get_nr_children(); i++) {
				visited.erase(find(visited.begin(), visited.end(), top->get_child(i)));
			}
			indent--;
		}
	}
}


The trick is to have visited carry just the nodes in the current branch (including duplicates/cycles). This is done by deleting one instance of all child elements when popping the top of the stack.
Last edited on
Topic archived. No new replies allowed.