Hello monks!
I'm facing some performance issues with my algorithm so I ask for your help. I'm using the Graph module to implement a graph that represents the Linux filesystem. Each vertex is a directory/file/link path from root and each edge is the "relationship" between them. For example for /a/b/c (assuming c is a file) you will get 3 vertices a and /a/b (dirs) and /a/b/c (file) and two edges a->/a/b and /a/b->/a/b/c (Actually there is another vertex "/" which is a directory and points to "/a").
The way I initialize the graph is:

my $graph = Graph->new;
$graph->set_vertex_attributes("/",  { "type" => "dir" });
my $self = {
    graph => $graph
};
[download]

Once I fill the graph, I want to have a sub that returns all the possible paths, including links. So for example, assume you have /a/b/c again and /p->/a/b then I want it to return /a,/a/b,/a/b/c,/p,/p/c.
So what I tried to do: after going over all the vertices, I want to find all the links and check if I can replace the target with the link. I also need to support recursive links so if I found changes, I'll do another iteration. The code:

sub extract_paths_from_graph {
    my ($self,$paths_href) = @_;

    foreach my $vertex ($self->{"graph"}->unique_vertices) {
        $paths_href->{$vertex}++;
    }

    while (1) {
        my $found_changes = 0;

        foreach my $vertex ($self->{"graph"}->unique_vertices) {
            my $type = $self->{"graph"}->get_vertex_attribute($vertex,
+ 'type');
            if (index($type,"link") != -1) {
                # Ignore cycle in graph to prevent infinite loop
                my $target = ($self->{"graph"}->successors($vertex))[0
+];
                if (path($target)->subsumes($vertex)) {
                    next;
                }

                foreach my $subpath (keys(%{$paths_href})) {
                    if ($subpath =~ /^$target\// || $subpath =~ /^$tar
+get$/) {
                        my $new_vertex = $subpath =~ s/^$target/$verte
+x/gr;
                        $found_changes = 1 unless (defined($paths_href
+->{$new_vertex}));
                        $paths_href->{$new_vertex}++;
                    }
                }
            }
        }
        last unless ($found_changes);
    }
}
[download]

My code was very slow and I managed to see that it comes from this method. I used NYTProf to create a profiling report and you can find it here. It looks like the problem is with the following line which takes to much time:

if ($subpath =~ /^$target\// || $subpath =~ /^$target$/) {
[download]

My assumptions are correct? Can you please suggest a better alternative way to perform the check? I though regex here will be the fastest.