view release on metacpan or  search on metacpan

lib/Algorithm/BellmanFord.pm  view on Meta::CPAN

package BellmanFord;

use 5.008004;
use Carp;
#our @ISA = qw(Exporter);
#our @EXPORT = qw();
require Exporter;
our @ISA = qw(Exporter);

# Items to export into callers namespace by default. Note: do not export
# # names by default without a very good reason. Use EXPORT_OK instead.
# # Do not simply export all your public functions/methods/constants.

# # This allows declaration       use Algorithm::BellmanFord ':all';
# # If you do not need this, moving things directly into @EXPORT or @EXPORT_OK
# # will save memory.
 our %EXPORT_TAGS = ( 'all' => [ qw() ] );

 our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );

 our @EXPORT = qw();
 
######################### variables #######
sub new
{
       $class = shift;
       $self = {
        input_file => shift,
		output_file => shift,
        };
    # Print all the values just for clarification.
    bless $self, $class;     
	return $self;
	}
sub calculate
{
open FILE, "$self->{input_file}" or die $!;
open FILE2, "$self->{output_file}" or die $!;
 @lines = <FILE>;

 $lines[0] =~/nodes ([0-9]+);links ([0-9]+)/;
 $totNodes = $1;
$links = $2;
print "\nTotal Nodes = $totNodes  and Links = $links\n";
@u1;
@v1;

for ( $i=1; $i<=$links; $i++ ) 
{
$lines[$i] =~/([a-z]),([a-z]),([0-9]+\.[0-9]+)/;
$u1[$i-1] = $1;
$v1[$i-1] = $2;
$wt[$i-1] = $3;
}
$nodeStr = $lines[$links + 1];
chomp ($nodeStr);
@nodes12 = split(',',$nodeStr);
 
@startNode;
@endNode;
$infinity = "122.0";
$lenOfFile = @lines;
$m = 0;
for ($t = $links + 2; $t < $lenOfFile-1; $t++) {
$lines[$t] =~/^path ([a-z]),([a-z])/;
$startEndNode[$m] = "$1,$2";
$m++;
}

foreach  $pair (@startEndNode) {

$pair =~/([a-z]),([a-z])/;
$root = $1;
$destination = $2;
print "\nWelcome to My Bellman algorithm we find solution for source = $1 and destination = $2\n";
open FILE2, ">>output.txt" or die $!;
print FILE2 "\nWelcome to My Bellman algorithm we find solution for source = $1 and destination = $2\n";
@node = @nodes12;

%dist;
%prev;

############################ the algorithm ####

# first, set all distances to infinity
foreach $n (@node) { 
	$dist{$n} = $infinity; 
	$prev{$n}= Null; 	
	}

# .. except the source
$dist{$root} = 0;

for ($l=0; $l < $totNodes - 1; $l++) {
	for ($n=0; $n < $links - 1; $n++) {
	 $u = $u1[$n];
	 $v = $v1[$n];
	 if ($dist{$u} + $wt[$n] < $dist{$v}) {
	  $dist{$v} = $dist{$u} + $wt[$n];
	  $prev{$v} = $u;
	}	
  }
}



##### print the solutions ######
$p = 0;
$path;

format STDOUT =
@<<<<<<<<<<<<<<   @>>>>>     @<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    $p,           $dist{$p}, $path;
.

foreach $p (@node) { 
    $t = $p;
    $path = $t;
    while ($t ne Null) { $t = $prev{$t}; $path = "$t -> " . $path; }
    write;
}

$n = $destination; 
$t = $n;
$path = $t;
print "\nThe required solution:\n"; 
while ($t ne Null) { $t = $prev{$t}; $path = "$t -> " . $path; }
write;

##########writing to output file