The mapping function uses the path name of the node. This is a string of directions that we can divide up into the hierarchical levels of the description. The method begins with the full set of processors then takes each direction from the path in turn, reducing the set of processors according to the relations that that direction has with the other directions in that level. If we are left with a single processor, the process terminates and the node is mapped to that processor. Otherwise, the process end when we run out of directions in the path, in which case the first processor in the remaining set is allocated the node.
As mentioned previously, in order to extract as much parallelism from the user functions as possible, we require a function that can check whether any of the nodes accessible from a particular node are allocated to a particular processor. This is similar to the allocation algorithm, but we always want to return a conservative estimate, since it is better to be inefficient than incorrect.