How can I represent a file system's symbolic links in a Perl hash?

Question

On Server Fault, How to list symbolic link chains? (not my question) talks about listing all the symbolic links and following them. To make this doable, let's consider a single directory at first.

I want to write a short utility that does this. It looks easy to put pairs from symbolic links into a hash and then process the hash.

But then I might have something like:

ls -l
total 0
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 08:48 a -> b
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 08:48 b -> c
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:03 c -> a
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 trap -> b
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 x -> y
lrwxrwxrwx 1 pjb pjb 1 2010-02-23 09:17 y -> b

where it is obvious that a->b->c is a loop, and that trap points into a loop, but to know x points into a loop I need to follow a bit.

One hash representation is:

a => b
b => c
c => a
trap => b
x => y
y => b

But the reverse representation is better for marking loops to bad starting points, once I know what the loops are.

So here's some questions:

• Is a hash the best structure to represent symbolic links?
• what's the best way to separate the graph of the file system to tell the loopy components from the tree components to the twig with a loop type pieces?
• Is there a better algorithm than manually searching for all the loops from all the starting points?
• From a graph-theory perspective -- is this sort of thing in the CPAN already? If not, what are some good helper modules?

Answer 1

There's a Graph module on CPAN that you might use as in the following:

#! /usr/bin/perl

use warnings;
use strict;

use Graph;

my $g = Graph->new;
my $dir = @ARGV ? shift : ".";

opendir my $dh, $dir or die "$0: opendir $dir: $!";
while (defined(my $name = readdir $dh)) {
  my $path = $dir . "/" . $name;

  if (-l $path) {
    my $dest = readlink $path;
    die "$0: readlink $path: $!" unless defined $dest;

    $g->add_edge($name => $dest);
  }
  else {
    $g->add_vertex($name);
  }
}

my @cycle = $g->find_a_cycle;
if (@cycle) {
  $" = ' -> '; #" # highlighting error
  print "$0: $dir: at least one cycle: @cycle\n";
}
else {
  print "$0: $dir: no cycles\n";
}

For example, in a directory similar in structure to the one in your question, the output is

$ ../has-cycle 
../has-cycle: .: at least one cycle: c -> a -> b