1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#!/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
|
