5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Can you somehow make the question more self-contained? For instance, I'm not sure I know what the problem is without going through the linked papers. Can you say what the input to the problem is, and what the output? I believe this will bring much more attention to the question, and hopefully give you a good answer too. $\endgroup$
    – Juho
    Jul 22 '15 at 10:18
  • $\begingroup$ seems like a line graph construction might be applicable? the graph can be recovered from its line graph.... see also vertices ←→ edges / stackoverflow $\endgroup$
    – vzn
    Jul 22 '15 at 15:05
  • $\begingroup$ @vzn I am not sure if the line graph maintains the initial flow properties following Kirchhoffs law which the algorithm of Ball is based on. $\endgroup$
    – smoes
    Jul 27 '15 at 9:23
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer. I thought about that solution, too, and will maybe fall back to it. However, as you already mentioned, the performance will suffer. It is absolutely important for my research to achieve maximal performance. $\endgroup$
    – smoes
    Jul 25 '15 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.