I agree, it seems tricky to actually quantify. The hard part is to create the graph in the first place, before you start the graph search. There must be methods for creating simplified approximations.