Unique path sums in a DAG using vertex instrumentation I stumbled across this paper from Ball et al.
In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control flow graphs of programs), these values are summed up. Afterwards they are able to reconstruct the executed path from the sum of the values of the traversed edges. 

For my research problem, I can not instrument edges, but vertices. To optimize vertex instrumentation I found a great paper from Knuth. However, I can not find a publication about determining vertex values that can be used in a manner as the edge values from the Ball paper. 

Does anyone know about an algorithm to fulfill my task?
The paper of Ball can be found here: http://www.cs.ucr.edu/~gupta/teaching/260-08/Papers/pathprof.pdf

I think the solution is easy. In addition to the global variable r, we keep a global variable lastVertex. Before exiting a vertex v, we set lastVertex=v. Now, when entering a vertex, we know which vertex we came from and we only need to keep a map in each vertex from each possible previous vertex to the corresponding transformation of r. This is only slightly less efficient than with edges, as we need to do a lookup in a map in each vertex. For larger graphs, this may be memory intensive though.