diff options
| author | goodale <goodale@17b73243-c579-4c4c-a9d2-2d5706c11dac> | 2004-05-03 16:38:41 +0000 |
|---|---|---|
| committer | goodale <goodale@17b73243-c579-4c4c-a9d2-2d5706c11dac> | 2004-05-03 16:38:41 +0000 |
| commit | 49cde4a53f86a3ffca3ec04560541b319fa2e8b5 (patch) | |
| tree | 73ef0afc65888ba14efe820a586b2e492980a8bd /lib/sbin/tsort | |
| parent | 2a7b18f2bab26331de1fadfcabc35d95997f95c6 (diff) | |
Latest changes from Yaakoub.
Added true topological sorting of thorns.
Proper error logging from configuration scripts.
git-svn-id: http://svn.cactuscode.org/flesh/trunk@3685 17b73243-c579-4c4c-a9d2-2d5706c11dac
Diffstat (limited to 'lib/sbin/tsort')
| -rw-r--r-- | lib/sbin/tsort | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/lib/sbin/tsort b/lib/sbin/tsort new file mode 100644 index 00000000..b6245ee8 --- /dev/null +++ b/lib/sbin/tsort @@ -0,0 +1,100 @@ +#!/usr/local/bin/perl -w
+# $Id: tsort,v 1.1 2004-05-03 16:38:41 goodale Exp $
+
+use strict;
+
+use vars qw($opt_b $opt_d);
+use Getopt::Std;
+my $usage = "usage: $0 [-b|-d] [filename]\n";
+getopts("bd") or die $usage;
+die $usage if ($opt_b && $opt_d);
+
+my %pairs; # all pairs ($l, $r)
+my %npred; # number of predecessors
+my %succ; # list of successors
+
+while (<>) {
+ my ($l, $r) = my @l = split;
+ next unless @l == 2;
+ next if defined $pairs{$l}{$r};
+ $pairs{$l}{$r}++;
+ $npred {$l} += 0;
+ ++$npred{$r};
+ push @{$succ{$l}}, $r;
+}
+
+# create a list of nodes without predecessors
+my @list = grep {!$npred{$_}} keys %npred;
+
+while (@list) {
+ $_ = pop @list;
+ print "$_\n";
+ foreach my $child (@{$succ{$_}}) {
+ if ($opt_b) { # breadth-first
+ unshift @list, $child unless --$npred{$child};
+ } else { # depth-first (default)
+ push @list, $child unless --$npred{$child};
+ }
+
+ }
+}
+
+warn "cycle detected\n" if grep {$npred{$_}} keys %npred;
+
+=head1 NAME
+
+tcsort - topological sort
+
+=head1 SYNOPSIS
+
+ tcsort [filename]
+
+=head1 DESCRIPTION
+
+=over 2
+
+Does a topological sort of input pairs.
+
+For a more complete description, see the tsort(1) man page,
+For an explanation of the algorithm,
+see the I<Work> column in the October, 1998, issue of SunExpert,
+or the references given below.
+
+=back
+
+=head1 OPTIONS AND ARGUMENTS
+
+=over 8
+
+=item B<[-b|-d]>
+
+breadth-first or depth-first (default) traversal
+
+=item B<filename>
+
+Optional input file.
+Input format is pairs of white-space-separated fields,
+one pair per line.
+Each field is the name of a node.
+
+Output is the topologically sorted list of nodes.
+
+Ignores lines without at least two fields.
+Ignores all fields on the line except the first two.
+
+=back
+
+=head1 AUTHOR
+
+ Jeffrey S. Haemer
+
+=head1 SEE ALSO
+
+tsort(1), tcsh(1), tchrist(1)
+
+Algorithm stolen from Jon Bentley (I<More Programming Pearls>, pp. 20-23),
+who, in turn, stole it from Don Knuth
+(I<Art of Computer Programming, volume 1: Fundamental Algorithms>,
+Section 2.2.3)
+
+=cut
|