Viewing file:  grand.pl (2.94 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
use Graph;
use Graph::Directed;
use Graph::Undirected;
use Time::HiRes qw(time);
use Getopt::Long;
my %OPT = (seed => 42, test => 'apsp', fill => 0.50, V => 20, directed => 1);
my @TEST = qw(apsp mstp mstk sptd sptb cc bcc scc);
my %TEST; @TEST{@TEST} = ();
my @WTEST = qw(apsp mstp mstk sptd sptb bcc);
my %WTEST; @WTEST{@WTEST} = ();
my @UTEST = qw(mstk mstp cc);
my %UTEST; @UTEST{@UTEST} = ();
my @DTEST = qw(scc);
my %DTEST; @DTEST{@DTEST} = ();
sub usage {
warn <<__EOF__;
$0: Usage: $0 [--seed=n]
[--test=@{[join('|', @TEST)]}]
[--directed=d] [--fill=f] [V]
Default values:
__EOF__
for my $o (sort keys %OPT) {
warn <<__EOF__;
$o = $OPT{$o}
__EOF__
}
exit(1);
}
usage()
unless
GetOptions(
'seed=n' => \$OPT{seed},
'test=s' => \$OPT{test},
'directed=n' => \$OPT{directed},
'fill=f' => \$OPT{fill},
);
$OPT{V} = shift if @ARGV;
usage() if @ARGV;
usage() unless exists $TEST{$OPT{test}};
print "Running $OPT{test}...\n";
srand($OPT{seed});
if (exists $UTEST{$OPT{test}} && $OPT{directed}) {
$OPT{directed} = 0;
print "($OPT{test} needs undirected, fixed)\n";
} elsif (exists $DTEST{$OPT{test}} && !$OPT{directed}) {
$OPT{directed} = 1;
print "($OPT{test} needs directed, fixed)\n";
}
if ($OPT{fill} < 0.0 || $OPT{fill} > 1.0) {
$OPT{fill} = 0.5;
print "($OPT{fill} must be between 0.0 and 1.0, fixed to be 0.5)\n";
}
# Thanks to Devel::DProf and List::Util breakage.
# my $g = Graph->random_graph(vertices => $OPT{V},
# directed => $OPT{directed},
# edges_fill => $OPT{fill});
my $E = int(($OPT{V} * ($OPT{V} - 1) * $OPT{fill}) / ($OPT{directed} ? 1 : 2));
my $g = $OPT{directed} ? Graph::Directed->new() : Graph::Undirected->new();
my $e = $E;
while (1) {
my $u = int(rand($OPT{V}));
my $v = int(rand($OPT{V}));
if ($u ne $v && !$g->has_edge($u, $v)) {
$g->add_edge($u, $v);
last unless --$e;
}
}
print "($OPT{V} vertices, $E edges)\n";
if (exists $WTEST{$OPT{test}}) {
for my $e ($g->edges) {
my ($u, $v) = @$e;
$g->set_edge_weight($u, $v, rand());
}
}
my $t0 = time();
my ($u0, $s0) = times();
if ($OPT{test} eq 'apsp') {
my $apsp = $g->APSP_Floyd_Warshall;
} elsif ($OPT{test} eq 'mstk') {
my $mst = $g->MST_Kruskal;
} elsif ($OPT{test} eq 'mstp') {
my $mst = $g->MST_Prim;
} elsif ($OPT{test} eq 'sptd') {
my $mst = $g->SPT_Dijkstra;
} elsif ($OPT{test} eq 'sptb') {
my $mst = $g->SPT_Bellman_Ford;
} elsif ($OPT{test} eq 'cc') {
my @cc = $g->connected_components;
} elsif ($OPT{test} eq 'bcc') {
my @bcc = $g->biconnected_components;
} elsif ($OPT{test} eq 'scc') {
my @scc = $g->strongly_connected_components;
} else {
die "$0: Unknown test '$OPT{test}'";
}
my $t1 = time();
my ($u1, $s1) = times();
my $u = $u1 - $u0;
my $s = $s1 - $s0;
my $c = $u + $s;
printf "real %.2f user %.2f system %.2f cpu %.2f\n", $t1 - $t0, $u, $s, $c;
exit(0);
|