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.

In reply to experiencing slowness due to matching algorithm 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.