Hi Monks!
This question is a sort of a follow up to my previous question, but you don't have to read as I have a more specific question. I have created a graph (using the Graph module) where each vertex is a canonical path from root ("/"). I have filled the graph with the following sub:

sub add_new_path {
    my ($self,$path) = @_;
    my $canonical_path = get_canonical_path($path);
    my @subpaths = splitdir($canonical_path);
    for my $index (0..$#subpaths) {
        next if (@subpaths[$index] eq ""); # Ignore empty strings
        my $parent_path = abs_path(catdir(@subpaths[0..($index-1)]));
        my $current_path = catdir($parent_path,@subpaths[$index]);
        my $original_path_flag = ($index eq $#subpaths);
        next if ($self->{"graph"}->has_vertex($current_path));
        if (-l $current_path) {
            my @resloved_links = resolve_symlink($current_path);
            my $target_path = $resloved_links[1];
            $self->add_path($target_path);
            $self->{"graph"}->add_edge($parent_path,$current_path);
            $self->{"graph"}->add_edge($current_path,$target_path);
            $self->{"graph"}->set_vertex_attributes($current_path, { "
+type" => "link", "original" => $original_path_flag });
        } elsif (-f $current_path) {
            $self->{"graph"}->add_edge($parent_path,$current_path);
            $self->{"graph"}->set_vertex_attributes($current_path, { "
+type" => "file", "original" => $original_path_flag });
        } elsif (-d $current_path) {
            $self->{"graph"}->add_edge($parent_path,$current_path);
            $self->{"graph"}->set_vertex_attributes($current_path, { "
+type" => "dir", "original" => $original_path_flag });
        }
    }
}

sub resolve_symlink {
    my ($file) = @_;
    unless (file_name_is_absolute($file)) {
        log_debug("Failed to resolve link $file");
        return;
    }
    my @files;
    my $origwd = getcwd;
    my $rv = eval {
        my $f = $file;
        while (1) {
            my $dir;
            ($f,$dir) = fileparse($f);
            last unless (-d $dir);
            chdir $dir or die "chdir $dir: $!";
            push @files, catfile(getcwd,$f);
            last unless (-l $f);
            defined( $f = readlink $f ) or die "readlink $f (cwd=".get
+cwd."): $!";
        }
    1 }; my $err = $@ || 'unknown error';
    chdir $origwd or (log_error("Failed to chdir $origwd: $!") && retu
+rn);
    die $err unless ($rv);
    return @files ? @files : ($file);
}
[download]

Basically, it creates a graph that contains link/dir/file vertices. If it's a file it does not have any children, if it's a link it has only one child and if it's a dir it could contain zero or more children. Just to make it more clear, consider this small example:

/      (dir) -> /a          (dir)
/a     (dir) -> /a/b        (dir)
/a/b/  (dir) -> /a/b/c      (dir)
/a/b/c (dir) -> /a/b/c/file (file)
/      (dir) -> /p          (link)
/p     (dir) -> /a/b/c      (dir)
[download]

Now the problem I'm having and trying to solve: I have an array of links. For each link $l with target $t I want to iterate over the graph and replace any subpath ^$t/.*<code> to be <code>$l/.*. In other words, I want to "fix" the graph to support virtual paths, instead of the physical paths.
Just to make it easier to understand, please consider the following example:

/a/b/c/file1
/a/b/d/e/file2
[download]

If you have link /p -> /a/b/c, then you will get:

/p/file1
/a/b/d/e/file2
[download]

If the link /p -> /a/b/c is already part of graph, then of course we need to remove it as well.
My problem with figuring an algorithm is because of how the graph is structured. Each vertex /a/b/c/.../x points to the next vertex /a/b/c/.../x/y so it seems very hard to update the whole path. I could iterate over the graph using the unique_vertices sub and check if it's could be replaced with some link and if it's, then replace it. The problem is with "fixing" the graph, for example, what about the parent vertices that are not of format ^$t/.*?
Is it possible to suggest a way to do this?