Unique path sums in a DAG using vertex instrumentation
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.