| 1 | =head1 NAME | ||
| 2 | |||
| 3 | WebService::UMLSKS::GetAllowablePaths - Get an allowable shortest path between the supplied terms. | ||
| 4 | |||
| 5 | =head1 SYNOPSIS | ||
| 6 | |||
| 7 | =head2 Basic Usage | ||
| 8 | |||
| 9 | use WebService::UMLSKS::GetAllowablePaths; | ||
| 10 | |||
| 11 | %subgraph = graph formed by FormGraph module; | ||
| 12 | |||
| 13 | $regex = allowable pattern regex specified by configuaration; | ||
| 14 | |||
| 15 | # $term1 and $term2 are current pair of terms | ||
| 16 | |||
| 17 | my $get_paths = WebService::UMLSKS::GetAllowablePaths->new; | ||
| 18 | |||
| 19 | my $get_path_info_result = $get_paths->get_shortest_path_info( \%subgraph, $term1, $term2,$verbose, $regex ); | ||
| 20 | |||
| 21 | # $get_path_info_result is an array reference which consists of path information. | ||
| 22 | |||
| 23 | =head1 DESCRIPTION | ||
| 24 | |||
| 25 | Get an allowable shortest path between the input terms. This module uses a standard BFS | ||
| 26 | graph algorithm with small modifications to accomodate the rules for allowable path. | ||
| 27 | It calculates the shortest allowable path between any two terms supplied to it as a input with | ||
| 28 | a graph formed by FormGraph module. | ||
| 29 | |||
| 30 | =head1 SUBROUTINES | ||
| 31 | |||
| 32 | The subroutines are as follows: | ||
| 33 | |||
| 34 | =cut | ||
| 35 | |||
| 36 | |||
| 37 | ############################################################################### | ||
| 38 | ########## CODE STARTS HERE ################################################# | ||
| 39 | |||
| 40 | # This module has package GetAllowablePaths | ||
| 41 | |||
| 42 | # Author : Mugdha Choudhari | ||
| 43 | |||
| 44 | # Description : this module takes a graph stored in form of hash of hash | ||
| 45 | # along with source and destination as input. | ||
| 46 | |||
| 47 | |||
| 48 | |||
| 49 | #use lib "/home/mugdha/UMLS-HSO/UMLS-HSO/WebService-UMLSKS-Similarity/lib"; | ||
| 50 | use warnings; | ||
| 51 | use SOAP::Lite; | ||
| 52 | use strict; | ||
| 53 | no warnings qw/redefine/; #http://www.perlmonks.org/?node_id=582220 | ||
| 54 | |||
| 55 | use WebService::UMLSKS::GetNeighbors; | ||
| 56 | |||
| 57 | #use Proc::ProcessTable; | ||
| 58 | |||
| 59 | |||
| 60 | |||
| 61 | package WebService::UMLSKS::GetAllowablePaths; | ||
| 62 | |||
| 63 | my $pcost = 10; | ||
| 64 | my $scost = 20; | ||
| 65 | |||
| 66 | |||
| 67 | use Log::Message::Simple qw[msg error debug]; | ||
| 68 | my $verbose = 0; | ||
| 69 | my $regex = ""; | ||
| 70 | |||
| 71 | my $current_shortest_length = 150; | ||
| 72 | my %Concept = (); | ||
| 73 | my %graph = (); | ||
| 74 | |||
| 75 | =head2 new | ||
| 76 | |||
| 77 | This sub creates a new object of GetAllowablePaths | ||
| 78 | |||
| 79 | =cut | ||
| 80 | |||
| 81 | sub new { | ||
| 82 | my $class = shift; | ||
| 83 | my $self = {}; | ||
| 84 | bless( $self, $class ); | ||
| 85 | return $self; | ||
| 86 | } | ||
| 87 | |||
| 88 | |||
| 89 | |||
| 90 | |||
| 91 | =head2 get_shortest_path_info | ||
| 92 | |||
| 93 | This sub returns the shortest path along with its cost and number of changes in direction | ||
| 94 | |||
| 95 | =cut | ||
| 96 | |||
| 97 | sub get_shortest_path_info | ||
| 98 | { | ||
| 99 | |||
| 100 | my $self = shift; # stupid girl... | ||
| 101 | my $hash_ref = shift; | ||
| 102 | my $source = shift; | ||
| 103 | my $destination = shift; | ||
| 104 | my $ver = shift; | ||
| 105 | $regex = shift; | ||
| 106 | $verbose = $ver; | ||
| 107 | %graph = %$hash_ref; | ||
| 108 | |||
| 109 | use Time::HiRes qw(usleep ualarm gettimeofday tv_interval); | ||
| 110 | my $t0 = [gettimeofday]; | ||
| 111 | |||
| 112 | # Return array that contains information of shortest path if found. | ||
| 113 | my @shortest_path_info = (); | ||
| 114 | |||
| 115 | # BFS algorithm to find the shortest allowable path between the | ||
| 116 | # current source and destination | ||
| 117 | |||
| 118 | # FIFO queue used for Breadth First Traversal | ||
| 119 | # This queue is a list of list | ||
| 120 | # Each element is a path (list) to a node which is last element of the list | ||
| 121 | # For ex., if the first element of queue is (A,B,C), this is path to get to node C. | ||
| 122 | |||
| 123 | my @queue = (); | ||
| 124 | |||
| 125 | # Initial path to source | ||
| 126 | my @t_path = (); | ||
| 127 | my @temp_path = (); | ||
| 128 | |||
| 129 | # Initialize Queue by pushing source | ||
| 130 | |||
| 131 | push( @t_path, $source ); | ||
| 132 | my $t_ref = \@t_path; | ||
| 133 | push( @queue, $t_ref ); | ||
| 134 | |||
| 135 | |||
| 136 | my $shortest_path_cost = 150; | ||
| 137 | my $shortest_path_ref = ""; | ||
| 138 | my @shortest_path_direction = (); | ||
| 139 | my $change_in_direction = -1; | ||
| 140 | |||
| 141 | |||
| 142 | |||
| 143 | # While queue is not empty traverse the graph | ||
| 144 | while ( $#queue != -1 ) { | ||
| 145 | |||
| 146 | |||
| 147 | #print "memory get_allpaths:just in while loop ". memory_usage()/1024/1024 ."\n"; | ||
| 148 | # print "memory get_allpaths: ". memory_usage()/1024/1024 ."\n"; | ||
| 149 | my $temp_path_ref = shift(@queue); | ||
| 150 | @temp_path = @$temp_path_ref; | ||
| 151 | |||
| 152 | #print "\nmemory in while loop get_allpaths: size of tem path :$#temp_path ". memory_usage()/1024/1024 ."\n"; | ||
| 153 | my $last_node = $temp_path[$#temp_path]; | ||
| 154 | |||
| 155 | if ( $last_node eq $destination ) { | ||
| 156 | |||
| 157 | # print "memory get_allpaths: one path found ". memory_usage()/1024/1024 ."\n"; | ||
| 158 | my @possible_path = @temp_path; | ||
| 159 | |||
| 160 | #msg( "\n one of the paths found",$verbose); | ||
| 161 | |||
| 162 | #msg( "\nValid path: @temp_path",$verbose); | ||
| 163 | |||
| 164 | my $current_direction = "X"; | ||
| 165 | my $current_path_cost = getCost( \@possible_path ); | ||
| 166 | |||
| 167 | #msg("\nValid path cost: $current_path_cost",$verbose); | ||
| 168 | |||
| 169 | if ( $current_path_cost < $shortest_path_cost ) { | ||
| 170 | msg( "\n got shorter path than current one : @temp_path",$verbose); | ||
| 171 | $shortest_path_cost = $current_path_cost; | ||
| 172 | #msg( "\n current cost is : $shortest_path_cost",$verbose); | ||
| 173 | $shortest_path_ref = \@possible_path; | ||
| 174 | # @shortest_path_direction = @{getDirection( \@temp_path )}; | ||
| 175 | @shortest_path_direction = (); #....fixed bug here | ||
| 176 | my $arrow_direction = ""; #... forgot to have these two lines | ||
| 177 | |||
| 178 | $change_in_direction = -1; | ||
| 179 | |||
| 180 | for my $i ( 0 .. $#temp_path - 1 ) { | ||
| 181 | my $first_node = $temp_path[$i]; | ||
| 182 | my $next_node = $temp_path[ $i + 1 ]; | ||
| 183 | my $direction = $graph{$first_node}{$next_node}; | ||
| 184 | |||
| 185 | # If current direction is not equal to previous direction, then | ||
| 186 | # increament the number of chnages in direction in current path. | ||
| 187 | if ( $current_direction ne $direction ) { | ||
| 188 | $change_in_direction++; | ||
| 189 | $current_direction = $direction; | ||
| 190 | |||
| 191 | } | ||
| 192 | |||
| 193 | #push( @shortest_path_direction, $arrow_direction ); | ||
| 194 | push( @shortest_path_direction, $direction ); | ||
| 195 | } | ||
| 196 | } | ||
| 197 | |||
| 198 | } | ||
| 199 | |||
| 200 | foreach my $link_node ( keys %{ $graph{$last_node} } ) { | ||
| 201 | # print "\n link node : $link_node"; | ||
| 202 | if ( $link_node ~~ @temp_path ) { | ||
| 203 | } | ||
| 204 | else { | ||
| 205 | #msg( "\n link node $link_node not in @temp_path",$verbose); | ||
| 206 | my @new_path = (); | ||
| 207 | |||
| 208 | #push(@temp_path,$link_node); | ||
| 209 | @new_path = @temp_path; | ||
| 210 | push( @new_path, $link_node ); | ||
| 211 | #print "\n new path : @new_path"; | ||
| 212 | #my $new_path_ref = \@new_path; | ||
| 213 | |||
| 214 | # Check if this path is allowable | ||
| 215 | my $path_string = ""; | ||
| 216 | for my $i ( 0 .. $#new_path - 1 ) { | ||
| 217 | my $first_node = $new_path[$i]; | ||
| 218 | my $next_node = $new_path[ $i + 1 ]; | ||
| 219 | my $direction = $graph{$first_node}{$next_node}; | ||
| 220 | $path_string = "$path_string" . "$direction"; # i HATE THIS LINEEEEEEE | ||
| 221 | |||
| 222 | } | ||
| 223 | #msg( "\n link node $link_node not in @temp_path, so new path : @new_path : $path_string",$verbose); | ||
| 224 | if ( $path_string =~ m/$regex/ ) { | ||
| 225 | #msg("\nthere is allowed path between $source and $destination :", $verbose); | ||
| 226 | #msg("\n path for link node $link_node : @new_path has path string $path_string which is allowed", $verbose); | ||
| 227 | |||
| 228 | my $new_path_ref = \@new_path; | ||
| 229 | #push( @queue, $new_path_ref ); | ||
| 230 | |||
| 231 | my $current_path_cost = getCost( \@new_path ); | ||
| 232 | # msg( "\npartial path cost for @new_path: $current_path_cost",$verbose); | ||
| 233 | if ( $current_path_cost < $shortest_path_cost ) { | ||
| 234 | # msg( | ||
| 235 | # "\npartial path cost is less than current shortest available path so push in queue",$verbose); | ||
| 236 | |||
| 237 | push( @queue, $new_path_ref ); | ||
| 238 | #print "\n new queue : @queue"; | ||
| 239 | } | ||
| 240 | |||
| 241 | else { | ||
| 242 | undef $new_path_ref; | ||
| 243 | undef @new_path; | ||
| 244 | undef @temp_path; | ||
| 245 | # msg( | ||
| 246 | # "\n current partial path is greater than current shorter path so, ignore this path",$verbose); | ||
| 247 | } | ||
| 248 | } | ||
| 249 | else{ | ||
| 250 | # msg("\n path for link node $link_node : @new_path has path string $path_string which is not allowed", $verbose); | ||
| 251 | } | ||
| 252 | } | ||
| 253 | } | ||
| 254 | } | ||
| 255 | # print "\nmemory get_allpaths:after while loop ". memory_usage()/1024/1024 ."\n"; | ||
| 256 | undef %graph; | ||
| 257 | |||
| 258 | my $t0_t1 = tv_interval($t0); | ||
| 259 | msg("\n BFS took : $t0_t1 secs\n",$verbose); | ||
| 260 | |||
| 261 | if($shortest_path_ref ne "") | ||
| 262 | { | ||
| 263 | #$current_shortest_length = $path_cost / 10; | ||
| 264 | msg("\n shortest path : @$shortest_path_ref", $verbose); | ||
| 265 | msg("\n shortest cost : $shortest_path_cost", $verbose); | ||
| 266 | msg("\n changes in direction for current shortest path : $change_in_direction", $verbose ); | ||
| 267 | msg("\n shortest path direction path string : @shortest_path_direction", $verbose); | ||
| 268 | push(@shortest_path_info,$shortest_path_ref); | ||
| 269 | push(@shortest_path_info,$shortest_path_cost); | ||
| 270 | push(@shortest_path_info, $change_in_direction); | ||
| 271 | push(@shortest_path_info, \@shortest_path_direction); | ||
| 272 | |||
| 273 | return \@shortest_path_info; | ||
| 274 | } | ||
| 275 | else | ||
| 276 | { | ||
| 277 | return -1; | ||
| 278 | } | ||
| 279 | |||
| 280 | } | ||
| 281 | |||
| 282 | =head2 getCost | ||
| 283 | |||
| 284 | This sub finds the cost of the path accepted as a parameter | ||
| 285 | |||
| 286 | =cut | ||
| 287 | |||
| 288 | sub getCost | ||
| 289 | |||
| 290 | { | ||
| 291 | |||
| 292 | my $ref = shift; | ||
| 293 | |||
| 294 | my @candidate_path = @$ref; | ||
| 295 | my $current_path_cost = 0; | ||
| 296 | my $direction = ""; | ||
| 297 | |||
| 298 | for my $i ( 0 .. $#candidate_path - 1 ) { | ||
| 299 | my $first_node = $candidate_path[$i]; | ||
| 300 | my $next_node = $candidate_path[ $i + 1 ]; | ||
| 301 | $direction = $graph{$first_node}{$next_node}; | ||
| 302 | |||
| 303 | # If a parent or child relation then add the parent cost | ||
| 304 | # changed the patterns regex | ||
| 305 | if ( $direction =~ /\bU\b|\bD\b/ ) { | ||
| 306 | $current_path_cost = $current_path_cost + 10; | ||
| 307 | } | ||
| 308 | |||
| 309 | # If a sibling relation then add the sibling cost | ||
| 310 | elsif ( $direction =~ /\bH\b/ ) { | ||
| 311 | $current_path_cost = $current_path_cost + 20; | ||
| 312 | } | ||
| 313 | |||
| 314 | } | ||
| 315 | |||
| 316 | #msg("\n cost of candidte path : @candidate_path : is : $current_path_cost", $verbose); | ||
| 317 | |||
| 318 | return $current_path_cost; | ||
| 319 | |||
| 320 | } | ||
| 321 | |||
| 322 | |||
| 323 | |||
| 324 | =head2 printHoH | ||
| 325 | |||
| 326 | This subroutines prints the current contents of hash of hash | ||
| 327 | |||
| 328 | =cut | ||
| 329 | |||
| 330 | sub printHoH { | ||
| 331 | |||
| 332 | my $hoh = shift; | ||
| 333 | my %hoh = %$hoh; | ||
| 334 | |||
| 335 | msg( "\nin printHoH : Graph is :", $verbose); | ||
| 336 | foreach my $ngram ( keys %hoh ) { | ||
| 337 | msg("\n***************************************************", $verbose); | ||
| 338 | msg( "\n" . $ngram . "{", $verbose); | ||
| 339 | foreach my $word ( keys %{ $hoh{$ngram} } ) { | ||
| 340 | msg( "\n", $verbose); | ||
| 341 | msg( $word. "=>" . $hoh{$ngram}{$word}, $verbose); | ||
| 342 | } | ||
| 343 | msg( "\n}", $verbose); | ||
| 344 | |||
| 345 | } | ||
| 346 | |||
| 347 | } | ||
| 348 | |||
| 349 | |||
| 350 | =head2 printHash | ||
| 351 | |||
| 352 | This sub prints argument hash. | ||
| 353 | |||
| 354 | =cut | ||
| 355 | |||
| 356 | sub printHash | ||
| 357 | { | ||
| 358 | my $ref = shift; | ||
| 359 | my %hash = %$ref; | ||
| 360 | foreach my $key(keys %hash) | ||
| 361 | { | ||
| 362 | print "\n $key => $hash{$key}"; | ||
| 363 | } | ||
| 364 | } | ||
| 365 | |||
| 366 | #printHoH(\%ParentInfo); | ||
| 367 | |||
| 368 | |||
| 369 | |||
| 370 | =head1 SEE ALSO | ||
| 371 | |||
| 372 | GetUserData.pm Query.pm ws-getAllowabletPath.pl GetParents.pm | ||
| 373 | |||
| 374 | =cut | ||
| 375 | |||
| 376 | =head1 AUTHORS | ||
| 377 | |||
| 378 | Mugdha Choudhari, University of Minnesota Duluth | ||
| 379 | E<lt>chou0130 at d.umn.eduE<gt> | ||
| 380 | |||
| 381 | Ted Pedersen, University of Minnesota Duluth | ||
| 382 | E<lt>tpederse at d.umn.eduE<gt> | ||
| 383 | |||
| 384 | |||
| 385 | |||
| 386 | |||
| 387 | =head1 COPYRIGHT | ||
| 388 | |||
| 389 | Copyright (C) 2011, Mugdha Choudhari, Ted Pedersen | ||
| 390 | |||
| 391 | This program is free software; you can redistribute it and/or modify | ||
| 392 | it under the terms of the GNU General Public License as published by | ||
| 393 | the Free Software Foundation; either version 2 of the License, or (at | ||
| 394 | your option) any later version. | ||
| 395 | |||
| 396 | This program is distributed in the hope that it will be useful, but | ||
| 397 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 398 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
| 399 | General Public License for more details. | ||
| 400 | |||
| 401 | You should have received a copy of the GNU General Public License | ||
| 402 | along with this program; if not, write to | ||
| 403 | The Free Software Foundation, Inc., | ||
| 404 | 59 Temple Place - Suite 330, | ||
| 405 | Boston, MA 02111-1307, USA. | ||
| 406 | |||
| 407 | =cut | ||
| 408 | |||
| 409 | #---------------------------------PERLDOC ENDS HERE--------------------------------------------------------------- | ||
| 410 | |||
| 411 | |||
| 412 | |||
| 413 | 1; |