I think you've stated what the problem is using Graph as the representation. In a filesystem a symlink entry is a pointer to the complete destination name, whereas when you're storing things as nodes you're seeing each step in the destination as a separate node (and you've lost the notation that "/p" maps to "/a/b/c/d" (or whatever)).

Little fuzzy, but I think you've gone a bit far afield trying to reimplement a filesystem. To do what you want (stipulated that I'm incautiously reading the problem) it almost seems to me that you want to have a list of links ordered from longest substitution to shortest and then walk that list of substitutions s{$cur_subst}{$cur_replacement} in that order.</handwavy>

But I still do have the information that "/p" is a link to "/a/b/c/d" in my suggested graph. You have a node "/" which points to node "/p" which points to "/a/b/c/d". There is also another chain - node "/" points to "/a" which points to "/a/b" which points to "/a/b/c" which points to "/a/b/c/d".

it almost seems to me that you want to have a list of links ordered
from longest substitution to shortest
[download]

Not sure why you think that but it might be because I didn't explain the question well enough. Given such graph, I want to replace any "logical path" with "virtual path". In other words, given some link with it's target, just go over the structure and replace the target with the link.
Now, it might (probaby) be that my structure is not good enough for this task. @etj suggested to use inodes without getting into the real implementation of the inodes (since it's an overkill). But the current structure seems to be similar to what he was talking about. So if the better solution here is to rethink the structure - then how should it look like? How the nodes should be structured?

You need to separate the identification of a node (a unique ID, which in this proposal would resemble an inode number) from its globally-visible name, which would just become a vertex attribute. That's how in Unix filesystems you can have hard-links, with multiple directory entries pointing at the same real disk-entity.

In concrete terms, stop naming the Graph vertices "/a/blah", and name them 1, 2, etc (with 0 as your FS root). Each directory-entry (which isn't quite the same as a file) would have a "local_name" attribute, and you'd find "/a/blah" by starting at the root, finding a child dir-node with the name "a", etc.