view release on metacpan or  search on metacpan

lib/WebService/UMLSKS/GetAllowablePaths.pm  view on Meta::CPAN

=head2 Basic Usage

use WebService::UMLSKS::GetAllowablePaths;
	
%subgraph = graph formed by FormGraph module;
	
$regex = allowable pattern regex specified by configuaration;
	
# $term1 and $term2 are current pair of terms
	
my $get_paths    = WebService::UMLSKS::GetAllowablePaths->new;	
	
my $get_path_info_result = $get_paths->get_shortest_path_info( \%subgraph, $term1, $term2,$verbose, $regex );
	
# $get_path_info_result is an array reference which consists of path information.		

=head1 DESCRIPTION

Get an allowable shortest path between the input terms. This module uses a standard BFS
graph algorithm with small modifications to accomodate the rules for allowable path.
It calculates the shortest allowable path between any two terms supplied to it as a input with 
a graph formed by FormGraph module.

=head1 SUBROUTINES

The subroutines are as follows:

=cut


###############################################################################
##########  CODE STARTS HERE  #################################################

# This module has package  GetAllowablePaths

# Author  : Mugdha Choudhari

# Description : this module takes a graph stored in form of hash of hash
# along with source and destination as input.



#use lib "/home/mugdha/UMLS-HSO/UMLS-HSO/WebService-UMLSKS-Similarity/lib";
use warnings;
use SOAP::Lite;
use strict;
no warnings qw/redefine/;    #http://www.perlmonks.org/?node_id=582220

use WebService::UMLSKS::GetNeighbors;

#use Proc::ProcessTable;



package WebService::UMLSKS::GetAllowablePaths;

my $pcost = 10;
my $scost = 20;


use Log::Message::Simple qw[msg error debug];
my $verbose = 0;
my $regex = "";

my $current_shortest_length = 150;
my %Concept = ();
my %graph = ();

=head2 new

This sub creates a new object of GetAllowablePaths

=cut

sub new {
	my $class = shift;
	my $self  = {};
	bless( $self, $class );
	return $self;
}




=head2 get_shortest_path_info

This sub returns the shortest path along with its cost and number of changes in direction

=cut

sub get_shortest_path_info
{

	my $self     = shift; # stupid girl... 
	my $hash_ref = shift;
	my $source      = shift;
	my $destination = shift;
	my $ver = shift;
	$regex = shift;
	$verbose = $ver;	
	 %graph       = %$hash_ref;
	
	use Time::HiRes qw(usleep ualarm gettimeofday tv_interval);	
	my $t0 = [gettimeofday];
	
	# Return array that contains information of shortest path if found.
	my @shortest_path_info = ();
	
	# BFS algorithm to find the shortest allowable path between the 
	# current source and destination
	
	# FIFO queue used for Breadth First Traversal
	# This queue is a list of list
	# Each element is a path (list) to a node which is last element of the list
	# For ex., if the first element of queue is (A,B,C), this is path to get to node C.

	my @queue = ();

	# Initial path to source
	my @t_path = ();
	my @temp_path = ();