set fileformat to unix.

git-svn-id: http://svn.cactuscode.org/flesh/trunk@3709 17b73243-c579-4c4c-a9d2-2d5706c11dac

1 files changed, 100 insertions, 100 deletions

diff --git a/lib/sbin/tsort b/lib/sbin/tsort
index b6245ee8..b594843b 100644
--- a/lib/sbin/tsort
+++ b/lib/sbin/tsort
@@ -1,100 +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

+#!/usr/local/bin/perl -w
+# $Id: tsort,v 1.2 2004-05-10 13:13:35 tradke 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