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?

In reply to How to enable virtual paths inside a graph DS? by ovedpo15

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.