How does node expansion work in a graph for AI search?

Question

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.

Answer 1

It seems to me that you are confusing the graph itself with the search tree produced by some search procedure.

As you state, you can't go from one node to the next unless that node knows its neighbors (and not only its own parent). But the search tree is (perhaps implicitly) generated from a search procedure you perform on the actual graph. Perhaps this is what the authors mean with the description you quote.

The actual graph on which you do a search in you can represent via an adjacency list. There, given a node, you can locate its neighbors and the search progresses using that information.