Node class - Problem with pointers

[mitrious]

I have a node class that has a Node* parentNode atribute.
My constructor is as follows:

Node::Node(Node* p,const State& s, int d) : parentNode(p), currentState(s), depth(d){ }

BUT with this constructor I get a problem:

I'm using this class to run a AI Search and at depth 3 it generates nodes with
parentNode == this

then when I try to get the PATH to that node the program enters a infinite loop.

if I use a constructor such as this:

Node::Node(Node* p,const State& s, int d) : parentNode(0), currentState(s), depth(d)
	{ 
		if(p != NULL)
			parentNode = new Node(p->parentNode, p->currentState, p->depth);
	}

it doesn't happen, the program works perfectly.

The method that Expands each node is this one:

std::vector<Node> Node::Expand()
{
	std::vector<Node> children; //vector to be returned

        //the function called here return a vector of new states
	std::vector<State> possibleStates = currentState.NextPossibleStates();

	for(int i = 0 ; i < (int)possibleStates.size(); i++)
	{
                //here's the point at which I create new nodes passing this as parent
		Node n(this, possibleStates[i], depth + 1);
		children.push_back(n);
	}

	return children;
}

The function that gets the path to a node is this one

std::vector<State> Node::Path()
{
	std::vector<State> path;

	Node* currentNode = (this);

	while(currentNode != NULL)
	{
		path.push_back(currentNode->currentState);
		currentNode = currentNode->parentNode;
	}

	std::reverse(path.begin(), path.end()); //reverses the path so it's in the right order

	return path;
}

Any guess on what could be happening ? (If anyone needs I can just send all the headers and .cpp files

[Sky Diploma]

In the second constructor, you seem to be initializing 'parentNode' to point to the parent of the Node* p ie: p->parentNode, however in the first constuctor, you directly set the parentNode(p).

I am unsure about the whole architecture of the implementation, But I was wondering if the following would do the trick.

Node::Node(Node* p,const State& s, int d) : parentNode(p->parentNode), currentState(s), depth(d){ }

[mitrious]

In the second constructor, you seem to be initializing 'parentNode' to point to the parent of the Node* p ie: p->parentNode, however in the first constuctor, you directly set the parentNode(p).

I am unsure about the whole architecture of the implementation, But I was wondering if the following would do the trick.

Node::Node(Node* p,const State& s, int d) : parentNode(p->parentNode), currentState(s), depth(d){ }

Actually not, because I (in the second constructor) initialize the parentNode to take "p->parentNode" as its parentNode there you are saying "p->parentNode" is the parent of parentNode (which doesn't make much sense), just picture yourself calling it for the "second node" created you would be trying to call p->parentNode for p == NULL

[ravenous]

I think that the second constructor is almost certainly NOT what you want. I think that this constructor will cause the entire path from the node that you're trying to make right up to the root node to be duplicated in memory. Look at what it's doing:

1. Node constructor called
2. The Node constructor allocates memory for a completely new node with new . This means that the parentNode member of the current node doesn't actually point to the parent node, but it's own personal copy of the parent node.
3. To create the new copy of the parent node, the Node constructor is recursively called, so the copy of the parent node makes another copy of its parent node, which makes another copy of its parent and so on
4. Eventually, you get to the root node, which has a NULL parent and the chain stops.

This will happen for each node that you allocate, giving your code a memory footprint that is the FACTORIAL of the number of nodes you're trying to store!! Not what you want!

I don't think that you want to use Sky Diploma's suggestion either

Node::Node(Node* p,const State& s, int d) : parentNode(p->parentNode), currentState(s), depth(d){ }

This will result in parentNode always pointing at the "grand-parent" node. In effect, this will ensure that it is actually always NULL .

The first constructor is definitely the one that you want. My guess is that you're using the constructor wrongly somewhere. If you think that a node should never be its own parent node, then use assert to check that it never is:

Node::Node(Node* p,const State& s, int d) : parentNode(p), currentState(s), depth(d)
{
   assert( this != parentNode );
}

Then, when you build and run your code in debug, you will hit this assertion somewhere and you'll get a message. Code execution will stop and you can attach your debugger to the process and find out what is going on.

I would also assert this in the Path method, in case it's been changed somewhere else:

while(currentNode != NULL)
{
	path.push_back(currentNode->currentState);
        assert( currentNode != currentNode->parentNode );
	currentNode = currentNode->parentNode;
}

You need to #include <cassert> to use assert . If you haven't used assert before, then you should only use them to check things that should NEVER happen, not things that you just don't want to happen. It should never be possible to pass this to its own constructor, since it doesn't exist until it's been constructed.

For things that you just don't want to happen, but aren't impossible, then throw an exceptionl instead. The reason is that assert is a macro that is generally compiled away in release code. So, assert gives you no protection in production code.

Give that a whirl and see what it turns up.

[mitrious]

I think that the second constructor is almost certainly NOT what you want. I think that this constructor will cause the entire path from the node that you're trying to make right up to the root node to be duplicated in memory. Look at what it's doing:

1. Node constructor called
2. The Node constructor allocates memory for a completely new node with new . This means that the parentNode member of the current node doesn't actually point to the parent node, but it's own personal copy of the parent node.
3. To create the new copy of the parent node, the Node constructor is recursively called, so the copy of the parent node makes another copy of its parent node, which makes another copy of its parent and so on
4. Eventually, you get to the root node, which has a NULL parent and the chain stops.

This will happen for each node that you allocate, giving your code a memory footprint that is the FACTORIAL of the number of nodes you're trying to store!! Not what you want!

I don't think that you want to use Sky Diploma's suggestion either

Node::Node(Node* p,const State& s, int d) : parentNode(p->parentNode), currentState(s), depth(d){ }

This will result in parentNode always pointing at the "grand-parent" node. In effect, this will ensure that it is actually always NULL .

The first constructor is definitely the one that you want. My guess is that you're using the constructor wrongly somewhere. If you think that a node should never be its own parent node, then use assert to check that it never is:

Node::Node(Node* p,const State& s, int d) : parentNode(p), currentState(s), depth(d)
{
   assert( this != parentNode );
}

Then, when you build and run your code in debug, you will hit this assertion somewhere and you'll get a message. Code execution will stop and you can attach your debugger to the process and find out what is going on.

I would also assert this in the Path method, in case it's been changed somewhere else:

while(currentNode != NULL)
{
	path.push_back(currentNode->currentState);
        assert( currentNode != currentNode->parentNode );
	currentNode = currentNode->parentNode;
}

You need to #include <cassert> to use assert . If you haven't used assert before, then you should only use them to check things that should NEVER happen, not things that you just don't want to happen. It should never be possible to pass this to its own constructor, since it doesn't exist until it's been constructed.

For things that you just don't want to happen, but aren't impossible, then throw an exceptionl instead. The reason is that assert is a macro that is generally compiled away in release code. So, assert gives you no protection in production code.

Give that a whirl and see what it turns up.

Using assert was a good idea to locate the error, but weirdly the assert is only being called at the Path method, not anywhere else. I've been wrapping my head around this for a few days and I can't seem to find what's happening.

Well, here's my node class:

class Node
{
public:
	Node();
	Node(Node*,const State&, int);
	//Depth of the node
	int Depth() const;
	//currentState of the node
	State CurrentState() const;

	//returns all the nodes we can get to from this node
	std::vector<Node> Expand();
	//returns a vector of states that leads to this goalState
	std::vector<State> Path();
private:
	Node* parentNode;
	State currentState;
	int depth;
};

And here's the search function

std::vector<State> IterativeDeepeningSearch::Search()
	{
		//Vector to be returned in case the search fails to find a goal
		std::vector<State> emptyPath;

		//current depth limit receives the user-defined initial value for the limit
		this->currentDepthLimit = this->initialLimit;

		//Tests the root node for goal
		if(IsGoal(rootNode))
			return rootNode.Path();
		else
		{
			//adds the root node to the vector ExploredSet
			this->ExploredSet.push_back(rootNode);
			//First FrontierSet is the expansion of the rootNode
			this->FrontierSet = rootNode.Expand();

			//While frontier isn't empty we keep searching if it's empty then no solution was found
			while(!FrontierSet.empty())
			{
				//bool indication wheter we should augment the currentDepthLimit
				bool augmentDepth = true;

				//Checks if any of the nodes in the frontier is a goal node
				for(int i = 0; i < (int)FrontierSet.size(); i++)
				{
					if(IsGoal(FrontierSet[i]))
					{
						//if it is a goal, return the path that leads to it
						return FrontierSet[i].Path();
					}
				}

				//A bool to indicate if any node has been expanded
				bool expandedNode = false;
				int i = 0;
				//if we checked everyNode or expanded One we leave the loop (if we expanded one node we leave the loop to check
				//if any of the new nodes is a goal node
				while(i < (int)FrontierSet.size() && !expandedNode)
				{
					//if the currentNode is inside the currentDepth range we can expand it
					if(FrontierSet[i].Depth() < currentDepthLimit)
					{
						//Don't need to augment de Depth just yet
						augmentDepth = false;

						//Expands the node
						std::vector<Node> newNodes = FrontierSet[i].Expand();

						//Checks to see if we can add the node to the frontier
						for(int j = 0 ; j < (int)newNodes.size(); j++)
						{							
							bool addNode = true;
							//If the currentPosition of the node is already at one of the nodes in the frontier
							//or in the exploredSet we don't add it to the frontier
							for(int k = 0; k < (int)FrontierSet.size(); k++)
							{
								if(newNodes[j].CurrentState() == FrontierSet[k].CurrentState())
									addNode = false;
							}
							for(int k = 0; k < (int)ExploredSet.size(); k++)
							{
								if(newNodes[j].CurrentState() == ExploredSet[k].CurrentState())
									addNode = false;
							}

							//if we can add the node just add it
							if(addNode)
							{
								//one node has been expanded succesfully
								expandedNode = true;
								FrontierSet.push_back(newNodes[j]);
							}
						}
						//Adds old node to the ExploredSet cuz it's already been expanded and is not a goal
						ExploredSet.push_back(FrontierSet[i]);
						//Erases the old node from the frontier
						FrontierSet.erase(FrontierSet.begin() + i);
						i--;
					}

					i++;
				}
				//augment the depth if needed
				if(augmentDepth)
					currentDepthLimit++;
			}
		}
		//if no solution was found we return the emptypath
		return emptyPath;
	}

]

I don't understand how can the assert inside the constructor NEVER be called if the one in the path is

[ravenous]

In that case it must be getting set to this somehow. parentNode is private, so it must be a method of the Node class that's setting it (or a friend, if you do that sort of thing). I'd make a private function called something like SetParentNode. Then replace all the places in your code where you do parentNode = someOtherNode with the new function. Then, add an assertion in the new SetParentNode function that you're never setting the parent node to this. That should point you to the right place.

[mitrious]

In that case it must be getting set to this somehow. parentNode is private, so it must be a method of the Node class that's setting it (or a friend, if you do that sort of thing). I'd make a private function called something like SetParentNode. Then replace all the places in your code where you do parentNode = someOtherNode with the new function. Then, add an assertion in the new SetParentNode function that you're never setting the parent node to this. That should point you to the right place.

There's no function where I do

parentNode = something

and there are no friend of that class.

Actually I just found out what was going wrong and fixed it, now it works perfectly =D

Thanks for your help

[ravenous]

Actually I just found out what was going wrong and fixed it, now it works perfectly =D

Cool, what was the problem/solution? (So someone else doesn't make the same mistake :) )

[mitrious]

Cool, what was the problem/solution? (So someone else doesn't make the same mistake :) )

The problem wasn't in my node class at all. The search algorithm was messing up the memory address of stuff changing the parent node of some nodes (cuz the parentNode attribute is just a pointer) so I re-wrote the search to use pointers to node
ExploredSet and FrontierSet are both std::vector<Node*> now, this way I have more controll of what's going on and didn't mess anything up, that was the best solution I found (which also used less memory and less constructor calls, which is always good.