I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city in Romania called Arad to Bucharest and the problem can be expressed as a graph like in the following image:
If when constructing the graph a Node
holds a reference to its parent, the action that was applied to get there and the current state at that node plus the path cost, how would node expansion work?
I am not sure how I can expand Arad to give the three nodes attached because Arad does not hold a reference to its children, instead the children hold a reference to Arad.
** Edit I am now thinking (whilst I am still unsure how a node is expanded) that child nodes are not built until a node is expanded. Is this correct?
I could maintain a mapping between a node and its children as a hashtable or something like this but I don't think this would scale to a larger problem where there the journey were much larger.
Equally I could search all nodes at expansion time and then find which have Arad as their parent if I kept some sort of information about each node such as its number in the graph\tree, or the easiest would be for each node to hold a reference to all its child nodes but this does not match the description of a node and its properties specified in the book.
Can somebody explain how node expansion should work in a graph as I am guessing at how I might do it which might not be right.