| 1 | |||
| 2 | =head1 NAME | ||
| 3 | |||
| 4 | WebService::UMLSKS::FormGraph - Form a graph by accepting parents and siblings from UMLS. | ||
| 5 | |||
| 6 | =head1 SYNOPSIS | ||
| 7 | |||
| 8 | =head2 Basic Usage | ||
| 9 | |||
| 10 | use WebService::UMLSKS::FormGraph; | ||
| 11 | use WebService::UMLSKS::GetUserData; | ||
| 12 | |||
| 13 | # Creating object of class GetUserData | ||
| 14 | my $g = WebService::UMLSKS::GetUserData->new; | ||
| 15 | |||
| 16 | $t1 = valid input CUI1; | ||
| 17 | $t2 = valid input CUI2; | ||
| 18 | $service = $g->getUserDetails($verbose); | ||
| 19 | @sources,@relations,@directions,@attributes = read from configuration; | ||
| 20 | $allowable_pattern_regex = read from pattern file; | ||
| 21 | $test_flag = 1 for testing else 0; | ||
| 22 | |||
| 23 | my $return_val = | ||
| 24 | form_graph-> form_graph($t1,$t2,$service, $verbose, \@sources, \@relations,\@directions | ||
| 25 | ,\@attributes,$allowable_pattern_regex,$test_flag); | ||
| 26 | |||
| 27 | =head1 DESCRIPTION | ||
| 28 | |||
| 29 | This module forms a graph of concepts connected to input concepts. It accepts the list of | ||
| 30 | parents, children and siblings from GetNeighbors module. This module calls | ||
| 31 | GetAllowablePaths module and finds the shortest allowable path between the input | ||
| 32 | CUIs or concepts. It then calculates the semantic relatedness between the concepts | ||
| 33 | using the shortest allowable path information. | ||
| 34 | |||
| 35 | =head1 SUBROUTINES | ||
| 36 | |||
| 37 | The subroutines are as follows: | ||
| 38 | |||
| 39 | =cut | ||
| 40 | |||
| 41 | ############################################################################### | ||
| 42 | ########## CODE STARTS HERE ################################################# | ||
| 43 | |||
| 44 | # This module has package FormGraph | ||
| 45 | |||
| 46 | # Author : Mugdha Choudhari | ||
| 47 | |||
| 48 | # Description : this module makes a graph stored in form of hash of hash and | ||
| 49 | # calculates the semantic relatedness value between the input concepts. | ||
| 50 | |||
| 51 | #use lib "/home/mugdha/UMLS-HSO/UMLS-HSO/WebService-UMLSKS-Similarity/lib"; | ||
| 52 | use warnings; | ||
| 53 | use SOAP::Lite; | ||
| 54 | use strict; | ||
| 55 | no warnings qw/redefine/; #http://www.perlmonks.org/?node_id=582220 | ||
| 56 | |||
| 57 | |||
| 58 | #use WebService::UMLSKS::GetAllowablePaths; changed name of getallowablepathsold | ||
| 59 | use WebService::UMLSKS::GetAllowablePaths; | ||
| 60 | use WebService::UMLSKS::GetNeighbors; | ||
| 61 | use WebService::UMLSKS::Query; | ||
| 62 | use WebService::UMLSKS::ConnectUMLS; | ||
| 63 | use WebService::UMLSKS::Similarity; | ||
| 64 | #use Proc::ProcessTable; | ||
| 65 | #use Graph::Directed; | ||
| 66 | |||
| 67 | |||
| 68 | package WebService::UMLSKS::FormGraph; | ||
| 69 | |||
| 70 | |||
| 71 | use Log::Message::Simple qw[msg error debug]; | ||
| 72 | |||
| 73 | my %node_cost = (); | ||
| 74 | my %Graph = (); | ||
| 75 | my $counter = 0; | ||
| 76 | my $const_C = 20; | ||
| 77 | my $const_k = 1 / 4; | ||
| 78 | my $absent = 0; | ||
| 79 | |||
| 80 | my %MetaCUIs = ( | ||
| 81 | 'C0332280' => 'Linkage concept', | ||
| 82 | 'C1274012' => 'Ambiguous concept', | ||
| 83 | 'C1274014' => 'Outdated concept', | ||
| 84 | 'C1276325' => 'Reason not stated concept', | ||
| 85 | 'C1274013' => 'Duplicate concept', | ||
| 86 | 'C1264758' => 'Inactive concept', | ||
| 87 | 'C1274015' => 'Erroneous concept', | ||
| 88 | 'C1274021' => 'Moved elsewhere', | ||
| 89 | 'C2733115' => 'Limited status concept', | ||
| 90 | 'C1299995' => 'Namespace concept', | ||
| 91 | 'C1285556' => 'Navigational concept', | ||
| 92 | 'C1298232' => 'Special concept', | ||
| 93 | ); | ||
| 94 | |||
| 95 | my @sources = (); | ||
| 96 | my @relations = (); | ||
| 97 | my @directions = (); | ||
| 98 | my @attributes = (); | ||
| 99 | |||
| 100 | my $source; | ||
| 101 | my $destination; | ||
| 102 | my $tflag; | ||
| 103 | my $verbose = 0; | ||
| 104 | |||
| 105 | |||
| 106 | # This sub creates a new object of FormGraph | ||
| 107 | |||
| 108 | =head2 new | ||
| 109 | |||
| 110 | This sub creates a new object of FormGraph. | ||
| 111 | |||
| 112 | =cut | ||
| 113 | |||
| 114 | sub new { | ||
| 115 | my $class = shift; | ||
| 116 | my $self = {}; | ||
| 117 | bless( $self, $class ); | ||
| 118 | return $self; | ||
| 119 | } | ||
| 120 | |||
| 121 | |||
| 122 | |||
| 123 | =head2 form_graph | ||
| 124 | |||
| 125 | This sub gets neighbors for the input concepts and forms graph. It also | ||
| 126 | calculates the semantic relatedness between the concepts. | ||
| 127 | |||
| 128 | =cut | ||
| 129 | |||
| 130 | sub form_graph | ||
| 131 | |||
| 132 | { | ||
| 133 | |||
| 134 | my $self = shift; | ||
| 135 | my $term1 = shift; | ||
| 136 | my $term2 = shift; | ||
| 137 | my $service = shift; | ||
| 138 | my $ver = shift; | ||
| 139 | my $s_ref = shift; | ||
| 140 | my $r_ref = shift; | ||
| 141 | my $d_ref = shift; | ||
| 142 | my $a_ref = shift; | ||
| 143 | my $regex = shift; | ||
| 144 | my $test_flag = shift; | ||
| 145 | my $sib_threshold = shift; | ||
| 146 | my $chd_threshold = shift; | ||
| 147 | |||
| 148 | #my $rel_attribute = "due_to"; | ||
| 149 | |||
| 150 | # Set the source and destination for use in other functions | ||
| 151 | |||
| 152 | $source = $term1; | ||
| 153 | $destination = $term2; | ||
| 154 | $tflag = $test_flag; | ||
| 155 | |||
| 156 | |||
| 157 | |||
| 158 | |||
| 159 | #my @candidate_siblings = (); | ||
| 160 | |||
| 161 | # If this is a testing mode, then create an output file | ||
| 162 | if($test_flag == 1) | ||
| 163 | { | ||
| 164 | open(OUTPUT,">>","output.txt") or die("Error: cannot open file 'output.txt'\n"); | ||
| 165 | |||
| 166 | } | ||
| 167 | |||
| 168 | $verbose = $ver; | ||
| 169 | |||
| 170 | # Set up the directions hash using the directions and relations arrays | ||
| 171 | my %Directions = (); | ||
| 172 | |||
| 173 | |||
| 174 | msg( "\n in form graph : regex: $regex", $verbose ); | ||
| 175 | |||
| 176 | @sources = @$s_ref; | ||
| 177 | @relations = @$r_ref; | ||
| 178 | @directions = @$d_ref; | ||
| 179 | |||
| 180 | for (my $i = 0 ; $i <= $#relations ; $i++){ | ||
| 181 | $Directions{$relations[$i]} = $directions[$i]; | ||
| 182 | } | ||
| 183 | |||
| 184 | #msg("\n in FormGraph",$verbose); | ||
| 185 | |||
| 186 | |||
| 187 | #printHash(\%Directions); | ||
| 188 | |||
| 189 | msg( "\n Sources used are : @sources", $verbose ); | ||
| 190 | |||
| 191 | msg( "\n Relations used are : @relations", $verbose ); | ||
| 192 | msg( "\n Directions used are : @directions", $verbose ); | ||
| 193 | |||
| 194 | %node_cost = (); | ||
| 195 | %Graph = (); | ||
| 196 | |||
| 197 | msg( "\nin FormGraph Term1 : $term1 , Term2: $term2", $verbose ); | ||
| 198 | |||
| 199 | # Creating GetParents object to get back the parents of input terms. | ||
| 200 | |||
| 201 | my @queue = (); | ||
| 202 | |||
| 203 | my $current_available_cost = 100000; | ||
| 204 | my $pcost = 10; | ||
| 205 | my $ccost = 10; | ||
| 206 | my $scost = 30; | ||
| 207 | my @parents = (); | ||
| 208 | my @sib = (); | ||
| 209 | my @children = (); | ||
| 210 | $node_cost{$term1} = 0; | ||
| 211 | $node_cost{$term2} = 0; | ||
| 212 | |||
| 213 | push( @queue, $term1 ); | ||
| 214 | push( @queue, $term2 ); | ||
| 215 | |||
| 216 | $Graph{$source} = {}; | ||
| 217 | $Graph{$destination} = {}; | ||
| 218 | |||
| 219 | |||
| 220 | my $read_parents = WebService::UMLSKS::GetNeighbors->new; | ||
| 221 | |||
| 222 | |||
| 223 | my $get_paths = WebService::UMLSKS::GetAllowablePaths->new; | ||
| 224 | |||
| 225 | my $cost_upto_current_node = 0; | ||
| 226 | my $current_node = ""; | ||
| 227 | my @visited = (); | ||
| 228 | my @current_shortest_path = (); | ||
| 229 | my $final_cost; | ||
| 230 | my $counter = 0; | ||
| 231 | my $change_in_direction = 0; | ||
| 232 | my @path_direction = (); | ||
| 233 | |||
| 234 | # my $g = Graph::Directed->new; | ||
| 235 | my $sibcount = 20; | ||
| 236 | my $chdcount = 20; | ||
| 237 | my $sd = 0; | ||
| 238 | |||
| 239 | use Time::HiRes qw(usleep ualarm gettimeofday tv_interval); | ||
| 240 | |||
| 241 | my $beforequeue = [gettimeofday]; | ||
| 242 | |||
| 243 | |||
| 244 | msg("Child threshold : $chd_threshold and sibling threshold : $sib_threshold", $verbose); | ||
| 245 | |||
| 246 | #until queue is empty | ||
| 247 | |||
| 248 | while ( $#queue != -1 ) { | ||
| 249 | |||
| 250 | msg("\nsize of queue : $#queue", $verbose); | ||
| 251 | |||
| 252 | my $inqueue = [gettimeofday]; | ||
| 253 | $sd++; | ||
| 254 | #print "inside while loop of queue , before poping element memory: ". memory_usage()/1024/1024 ."\n"; | ||
| 255 | |||
| 256 | @parents = (); | ||
| 257 | @sib = (); | ||
| 258 | @children = (); | ||
| 259 | printQueue( \@queue ); | ||
| 260 | |||
| 261 | #printHoH(\%Graph); | ||
| 262 | |||
| 263 | my $current_node = shift(@queue); | ||
| 264 | $counter++; | ||
| 265 | push( @visited, $current_node ); | ||
| 266 | #msg( "\n visited : @visited", $verbose ); | ||
| 267 | my $cost_upto_current_node = $node_cost{$current_node}; | ||
| 268 | #msg( | ||
| 269 | #"\n current node : $current_node and cost till here : $cost_upto_current_node", | ||
| 270 | # $verbose | ||
| 271 | #); | ||
| 272 | if ( $cost_upto_current_node >= $current_available_cost - 10 || $cost_upto_current_node >= 150) { | ||
| 273 | msg( "\n ########\nIgnore node as it would lead to longer path", | ||
| 274 | $verbose ); | ||
| 275 | next; | ||
| 276 | } | ||
| 277 | |||
| 278 | |||
| 279 | msg("\n QUERYING $current_node", $verbose); | ||
| 280 | msg("\nsize of queue : $#queue", $verbose); | ||
| 281 | |||
| 282 | my %subgraph = %Graph; | ||
| 283 | |||
| 284 | #msg("\n current node $current_node has a allowable shortest path from either source | ||
| 285 | #or destination , so bring its neighbors from UMLS and them them to queue" , $verbose); | ||
| 286 | |||
| 287 | my $neighbors_hash_ref = | ||
| 288 | call_getconceptproperties( $current_node, $service ); | ||
| 289 | if ( $neighbors_hash_ref eq 'undefined' | | ||
| 290 | $neighbors_hash_ref eq 'empty' ) | ||
| 291 | { | ||
| 292 | msg("\n no Info for $current_node",$verbose); | ||
| 293 | next; | ||
| 294 | } | ||
| 295 | my $gcp_time = tv_interval($inqueue); | ||
| 296 | msg("\n after getConceptprop call : $gcp_time secs", $verbose); | ||
| 297 | |||
| 298 | #prints*"memory after calling webservice for $current_node: ". memory_usage()/1024/1024 ."\n"; | ||
| 299 | |||
| 300 | #use Time::HiRes qw(usleep ualarm gettimeofday tv_interval); | ||
| 301 | |||
| 302 | my $before_get_neighbors = [gettimeofday]; | ||
| 303 | |||
| 304 | |||
| 305 | my $neighbors_info_ref = | ||
| 306 | $read_parents->read_object( $neighbors_hash_ref, $current_node, $verbose,\%Directions,$a_ref); | ||
| 307 | |||
| 308 | #print "memory after calling read_object for $current_node: ". memory_usage()/1024/1024 ."\n"; | ||
| 309 | |||
| 310 | undef $neighbors_hash_ref; | ||
| 311 | |||
| 312 | #print "\n neighbors_hahs_ref after undef $neighbors_hash_ref"; | ||
| 313 | |||
| 314 | #print "memory after undef neighbors_hash: ". memory_usage()/1024/1024 ."\n"; | ||
| 315 | |||
| 316 | my $getneibor_time = tv_interval($before_get_neighbors); | ||
| 317 | msg("\n after get neighbors call : $getneibor_time secs", $verbose); | ||
| 318 | |||
| 319 | |||
| 320 | my $updateHOH_nodecost = [gettimeofday]; | ||
| 321 | |||
| 322 | if ( $neighbors_info_ref eq 'empty' ) | ||
| 323 | { | ||
| 324 | msg("\n no desired neighbors for $current_node",$verbose); | ||
| 325 | next; | ||
| 326 | } | ||
| 327 | |||
| 328 | if ( defined $neighbors_info_ref && @$neighbors_info_ref ) { | ||
| 329 | |||
| 330 | # For the graph using the parents, children and siblings of the term. | ||
| 331 | my @n = @$neighbors_info_ref; | ||
| 332 | |||
| 333 | |||
| 334 | undef $neighbors_info_ref; | ||
| 335 | |||
| 336 | #print "memory after undef neighbors info: ". memory_usage()/1024/1024 ."\n"; | ||
| 337 | my $p_ref = shift(@n); | ||
| 338 | my $c_ref = shift(@n); | ||
| 339 | my $s_ref = shift(@n); | ||
| 340 | |||
| 341 | undef @n; | ||
| 342 | |||
| 343 | if ( $p_ref ne 'empty' ) { | ||
| 344 | @parents = @{$p_ref}; | ||
| 345 | } | ||
| 346 | |||
| 347 | if ( $c_ref ne 'empty' ) { | ||
| 348 | @children = @{$c_ref}; | ||
| 349 | } | ||
| 350 | |||
| 351 | if ( $s_ref ne 'empty' ) { | ||
| 352 | @sib = @{$s_ref}; | ||
| 353 | } | ||
| 354 | |||
| 355 | if($current_node eq $source || $current_node eq $destination) | ||
| 356 | { | ||
| 357 | if($#sib > $sib_threshold || $#children > $chd_threshold) | ||
| 358 | { | ||
| 359 | print STDERR "final output :-500<>$term1<>$term2\n"; | ||
| 360 | |||
| 361 | exit; | ||
| 362 | |||
| 363 | } | ||
| 364 | |||
| 365 | } | ||
| 366 | |||
| 367 | #$sibcount = $#sib; # keep all the neighbors | ||
| 368 | |||
| 369 | msg("\n number of parents : $#parents", $verbose); | ||
| 370 | |||
| 371 | msg( "\n parents of $current_node : @parents", $verbose ); | ||
| 372 | for(my $par = 0 ; $par < $#parents ; $par++) | ||
| 373 | { | ||
| 374 | # msg("$parents[$par] [$Concept{$parents[$par]}", $verbose); | ||
| 375 | } | ||
| 376 | |||
| 377 | msg("\n number of siblings : $#sib", $verbose); | ||
| 378 | |||
| 379 | msg( "\n siblings of $current_node: @sib ", $verbose ); | ||
| 380 | for(my $par = 0 ; $par < $#sib ; $par++) | ||
| 381 | { | ||
| 382 | # msg("$sib[$par] [$Concept{$sib[$par]}", $verbose); | ||
| 383 | } | ||
| 384 | |||
| 385 | msg("\n number of children : $#children", $verbose); | ||
| 386 | |||
| 387 | msg( "\n children of $current_node: @children", $verbose ); | ||
| 388 | for(my $par = 0 ; $par < $#children ; $par++) | ||
| 389 | { | ||
| 390 | # msg("$children[$par] [$Concept{$children[$par]}", $verbose); | ||
| 391 | } | ||
| 392 | |||
| 393 | |||
| 394 | |||
| 395 | |||
| 396 | |||
| 397 | unless($current_node eq $source || $current_node eq $destination){ | ||
| 398 | |||
| 399 | |||
| 400 | |||
| 401 | |||
| 402 | if($#sib > $sib_threshold || $#children > $chd_threshold) | ||
| 403 | { | ||
| 404 | # msg( "\n parents of $current_node : @parents", $verbose ); | ||
| 405 | |||
| 406 | |||
| 407 | # msg( "\n siblings of $current_node: @sib ", $verbose ); | ||
| 408 | |||
| 409 | |||
| 410 | # msg( "\n children of $current_node: @children", $verbose ); | ||
| 411 | |||
| 412 | msg("\n should ignore $current_node as it would explode the graph",$verbose); | ||
| 413 | |||
| 414 | print STDERR "final output :-50<>$term1<>$term2\n"; | ||
| 415 | #next; | ||
| 416 | exit; | ||
| 417 | |||
| 418 | } | ||
| 419 | |||
| 420 | |||
| 421 | |||
| 422 | } | ||
| 423 | |||
| 424 | |||
| 425 | |||
| 426 | # Check if sibcount is greater than actual #siblings, if yes, | ||
| 427 | # take actual siblings. | ||
| 428 | #if($sibcount > $#sib){ | ||
| 429 | $sibcount = $#sib; | ||
| 430 | #} | ||
| 431 | #if($chdcount > $#children){ | ||
| 432 | $chdcount = $#children; | ||
| 433 | #} | ||
| 434 | |||
| 435 | |||
| 436 | foreach my $p (@parents) { | ||
| 437 | unless ( $p ~~ %MetaCUIs ) { | ||
| 438 | $Graph{$current_node}{$p} = 'U'; | ||
| 439 | $Graph{$p}{$current_node} = 'D'; | ||
| 440 | #$g->add_edge($current_node,$p); | ||
| 441 | #$g->add_weighted_edge($p,$current_node, 2); | ||
| 442 | } | ||
| 443 | } | ||
| 444 | # foreach my $c (@children) { | ||
| 445 | if ( $#children != -1 ) { | ||
| 446 | foreach my $c (0 .. $chdcount) { | ||
| 447 | unless ( $children[$c] ~~ %MetaCUIs ) { | ||
| 448 | |||
| 449 | $Graph{$current_node}{$children[$c]} = 'D'; | ||
| 450 | $Graph{$children[$c]}{$current_node} = 'U'; | ||
| 451 | #$g->add_edge($current_node,$c); | ||
| 452 | #$g->add_weighted_edge($c,$current_node, 1); | ||
| 453 | } | ||
| 454 | } | ||
| 455 | } | ||
| 456 | # } | ||
| 457 | if ( $#sib != -1 ) { | ||
| 458 | foreach my $s (0 .. $sibcount) { | ||
| 459 | |||
| 460 | unless ( $sib[$s] ~~ %MetaCUIs ) { | ||
| 461 | |||
| 462 | unless(exists $Graph{$current_node}{$sib[$s]}){ | ||
| 463 | $Graph{$current_node}{$sib[$s]} = 'H'; | ||
| 464 | } | ||
| 465 | |||
| 466 | unless(exists $Graph{$sib[$s]}{$current_node}){ | ||
| 467 | #$Graph{$sib[$s]}{$current_node} = 3 ; | ||
| 468 | $Graph{$sib[$s]}{$current_node} = 'H' ; | ||
| 469 | } | ||
| 470 | # $g->add_edge($current_node,$s); | ||
| 471 | #$g->add_weighted_edge($s,$current_node, 3); | ||
| 472 | |||
| 473 | } | ||
| 474 | } | ||
| 475 | } | ||
| 476 | } | ||
| 477 | |||
| 478 | #my %Concept = %$WebService::UMLSKS::GetNeighbors::ConceptInfo_ref; | ||
| 479 | |||
| 480 | |||
| 481 | #print "memory after forming graph for $current_node: ". memory_usage()/1024/1024 ."\n"; | ||
| 482 | |||
| 483 | |||
| 484 | if ( $#parents == -1 && $#sib == -1 && $#children == -1 ) { | ||
| 485 | msg("\n no neighbors at all",$verbose); | ||
| 486 | undef @parents; | ||
| 487 | undef @children; | ||
| 488 | undef @sib; | ||
| 489 | next; | ||
| 490 | } | ||
| 491 | else { | ||
| 492 | if ( $#parents != -1 ) { | ||
| 493 | foreach my $parent (@parents) { | ||
| 494 | #msg( "\n parent is : $parent", $verbose ); | ||
| 495 | unless ( $parent ~~ %MetaCUIs ) { | ||
| 496 | unless ( $parent ~~ @visited ) { | ||
| 497 | #msg("\n parent $parent not visited"); | ||
| 498 | my $total_cost_till_parent = | ||
| 499 | $cost_upto_current_node + $pcost; | ||
| 500 | if ( $parent ~~ %node_cost ) { | ||
| 501 | #msg("\n $parent is already in node cost hash"); | ||
| 502 | if ( $node_cost{$parent} > | ||
| 503 | $total_cost_till_parent ) | ||
| 504 | { | ||
| 505 | # msg("\n changing value of $parent in node cost hash",$verbose); | ||
| 506 | $node_cost{$parent} = | ||
| 507 | $total_cost_till_parent; | ||
| 508 | } | ||
| 509 | } | ||
| 510 | else { | ||
| 511 | #msg("\n parent $parent not in node hash, so add to hash and push in queue", $verbose); | ||
| 512 | $node_cost{$parent} = $total_cost_till_parent; | ||
| 513 | push( @queue, $parent ); | ||
| 514 | |||
| 515 | } | ||
| 516 | } | ||
| 517 | } | ||
| 518 | |||
| 519 | } | ||
| 520 | |||
| 521 | } | ||
| 522 | |||
| 523 | my $check = 0; | ||
| 524 | if ( $#sib != -1 ) { | ||
| 525 | for my $s (0 .. $sibcount) { | ||
| 526 | |||
| 527 | #msg("\t $sib[$s]",$verbose); | ||
| 528 | unless ( $sib[$s] ~~ %MetaCUIs ) { | ||
| 529 | unless ($sib[$s] ~~ @visited ) { | ||
| 530 | |||
| 531 | #msg ("\n sibling $sib not visited",$verbose); | ||
| 532 | my $total_cost_till_sib = | ||
| 533 | $cost_upto_current_node + $scost; | ||
| 534 | if ( $sib[$s] ~~ %node_cost ) { | ||
| 535 | |||
| 536 | # msg( "\n $sib is already in node cost hash",$verbose); | ||
| 537 | if ( $node_cost{$sib[$s]} > $total_cost_till_sib ) { | ||
| 538 | |||
| 539 | # msg("\n changing value of $sib in node cost hash",$verbose); | ||
| 540 | $node_cost{$sib[$s]} = $total_cost_till_sib; | ||
| 541 | } | ||
| 542 | } | ||
| 543 | else { | ||
| 544 | |||
| 545 | #msg("\n sibling $sib not in node hash, so add to hash and push in queue",$verbose); | ||
| 546 | $node_cost{$sib[$s]} = $total_cost_till_sib; | ||
| 547 | push( @queue, $sib[$s] ); | ||
| 548 | #$check++; | ||
| 549 | } | ||
| 550 | } | ||
| 551 | |||
| 552 | } | ||
| 553 | |||
| 554 | |||
| 555 | } | ||
| 556 | } | ||
| 557 | |||
| 558 | |||
| 559 | |||
| 560 | if ( $#children != -1 ) { | ||
| 561 | foreach my $child (@children) { | ||
| 562 | # msg( "\n child is : $child", $verbose ); | ||
| 563 | unless ( $child ~~ %MetaCUIs ) { | ||
| 564 | unless ( $child ~~ @visited ) { | ||
| 565 | # msg("\n child $child not visited"); | ||
| 566 | my $total_cost_till_child = | ||
| 567 | $cost_upto_current_node + $ccost; | ||
| 568 | if ( $child ~~ %node_cost ) { | ||
| 569 | # msg("\n $child is already in node cost hash"); | ||
| 570 | if ( $node_cost{$child} > | ||
| 571 | $total_cost_till_child ) | ||
| 572 | { | ||
| 573 | # msg( | ||
| 574 | #"\n changing value of $child in node cost hash", | ||
| 575 | # $verbose | ||
| 576 | # ); | ||
| 577 | $node_cost{$child} = $total_cost_till_child; | ||
| 578 | } | ||
| 579 | } | ||
| 580 | else { | ||
| 581 | # msg( | ||
| 582 | #"\n child $child not in node hash, so add to hash and push in queue", | ||
| 583 | # $verbose | ||
| 584 | # ); | ||
| 585 | $node_cost{$child} = $total_cost_till_child; | ||
| 586 | push( @queue, $child ); | ||
| 587 | |||
| 588 | } | ||
| 589 | } | ||
| 590 | } | ||
| 591 | |||
| 592 | } | ||
| 593 | |||
| 594 | } | ||
| 595 | |||
| 596 | } | ||
| 597 | |||
| 598 | my $graph_t = tv_interval($updateHOH_nodecost); | ||
| 599 | msg("\n Graph formation node cost update took : $graph_t secs\n",$verbose); | ||
| 600 | #print "memory after updating node cost hash: ". memory_usage()/1024/1024 ."\n"; | ||
| 601 | @queue = (); | ||
| 602 | foreach | ||
| 603 | my $key ( sort { $node_cost{$a} <=> $node_cost{$b} } keys %node_cost ) | ||
| 604 | { | ||
| 605 | unless ( $key ~~ @visited ) { | ||
| 606 | push( @queue, $key ); | ||
| 607 | } | ||
| 608 | } | ||
| 609 | |||
| 610 | |||
| 611 | msg("\nsize of queue after adding neighbors: $#queue", $verbose); | ||
| 612 | |||
| 613 | |||
| 614 | |||
| 615 | #my %subgraph = %Graph; | ||
| 616 | %subgraph = %Graph; | ||
| 617 | |||
| 618 | |||
| 619 | # Check if a shortest allowable path exists between source and destination | ||
| 620 | my $get_path_info_result = | ||
| 621 | $get_paths->get_shortest_path_info( \%subgraph, $term1, $term2, | ||
| 622 | $verbose, $regex ); | ||
| 623 | |||
| 624 | #print "memory after calling get paths: ". memory_usage()/1024/1024 ."\n"; | ||
| 625 | undef %subgraph; | ||
| 626 | %subgraph = (); | ||
| 627 | |||
| 628 | #print "memory after undef subgraph: ". memory_usage()/1024/1024 ."\n"; | ||
| 629 | if ( $get_path_info_result != -1 && $get_path_info_result != -2 ) { | ||
| 630 | my @path_info = @$get_path_info_result; | ||
| 631 | @current_shortest_path = @{ shift(@path_info) }; | ||
| 632 | $current_available_cost = shift(@path_info); | ||
| 633 | $change_in_direction = shift(@path_info); | ||
| 634 | @path_direction = @{ shift(@path_info)}; | ||
| 635 | $final_cost = $current_available_cost; | ||
| 636 | |||
| 637 | my $continue_searching = 0; | ||
| 638 | |||
| 639 | # CHANGED ON 24 AUG TO CHECK | ||
| 640 | # recommented on 25 aug, as it is taking lot of time | ||
| 641 | #foreach my $key (keys %Directions){ | ||
| 642 | # if($Directions{$key} eq "H") | ||
| 643 | # { | ||
| 644 | # msg("\n This test has horizontal relation so, finding better path",$verbose); | ||
| 645 | # $continue_searching = 1; | ||
| 646 | # } | ||
| 647 | #} | ||
| 648 | #.... | ||
| 649 | |||
| 650 | #if($continue_searching == 0){ #.. | ||
| 651 | last; | ||
| 652 | #}#... | ||
| 653 | |||
| 654 | |||
| 655 | |||
| 656 | } | ||
| 657 | if($get_path_info_result == -2) | ||
| 658 | { | ||
| 659 | # Stop seraching for shortest path as the path length has already increased | ||
| 660 | # the threshold value. | ||
| 661 | |||
| 662 | if(@current_shortest_path) | ||
| 663 | { | ||
| 664 | msg( "\n Stopped searching as the path length exceeds the threshold value", $verbose); | ||
| 665 | last; | ||
| 666 | } | ||
| 667 | else | ||
| 668 | { | ||
| 669 | msg( "\n Stopped searching as the path length exceeds the threshold value", $verbose); | ||
| 670 | if($test_flag == 1) | ||
| 671 | { | ||
| 672 | print OUTPUT "0<>$term1<>$term2\n"; | ||
| 673 | } | ||
| 674 | last; | ||
| 675 | } | ||
| 676 | |||
| 677 | |||
| 678 | } | ||
| 679 | |||
| 680 | |||
| 681 | } | ||
| 682 | |||
| 683 | my $t0_t1 = tv_interval($beforequeue); | ||
| 684 | msg("\n while loop took : $t0_t1 secs\n",$verbose); | ||
| 685 | |||
| 686 | #print "memory after while loop ends: ". memory_usage()/1024/1024 ."\n"; | ||
| 687 | if (@current_shortest_path) { | ||
| 688 | |||
| 689 | undef %Graph; | ||
| 690 | |||
| 691 | undef %node_cost; | ||
| 692 | |||
| 693 | my %Concept = %$WebService::UMLSKS::GetNeighbors::ConceptInfo_ref; | ||
| 694 | |||
| 695 | |||
| 696 | undef ${WebService::UMLSKS::GetNeighbors::ConceptInfo_ref}; | ||
| 697 | |||
| 698 | my $initial_relatedness = $const_C - ($final_cost/10); | ||
| 699 | |||
| 700 | msg( "\n IR : $initial_relatedness", $verbose ); | ||
| 701 | |||
| 702 | |||
| 703 | if($change_in_direction == -1){ | ||
| 704 | $change_in_direction = 0; | ||
| 705 | } | ||
| 706 | my $semantic_relatedness = $initial_relatedness - | ||
| 707 | (($const_k * $initial_relatedness) * $change_in_direction); | ||
| 708 | |||
| 709 | print "\n Final shortest path :"; | ||
| 710 | |||
| 711 | |||
| 712 | for my $n (0 .. $#current_shortest_path) { | ||
| 713 | if($n < $#current_shortest_path){ | ||
| 714 | print "$Concept{$current_shortest_path[$n]} ($current_shortest_path[$n]) ($path_direction[$n])->"; | ||
| 715 | } | ||
| 716 | else | ||
| 717 | { | ||
| 718 | print "$Concept{$current_shortest_path[$n]} ($current_shortest_path[$n])"; | ||
| 719 | } | ||
| 720 | |||
| 721 | |||
| 722 | } | ||
| 723 | |||
| 724 | msg( "\n Final shortest path : ", $verbose ); | ||
| 725 | foreach my $n (@current_shortest_path) { | ||
| 726 | msg( "->$Concept{$n} ($n)", $verbose ); | ||
| 727 | } | ||
| 728 | |||
| 729 | undef %Concept; | ||
| 730 | #print "memory after undef hash concept: ". memory_usage()/1024/1024 ."\n"; | ||
| 731 | print "\n Final path cost : $final_cost"; | ||
| 732 | msg( "\n Final path cost : $final_cost", $verbose ); | ||
| 733 | |||
| 734 | print "\n Changes in Direction : $change_in_direction"; | ||
| 735 | msg( "\n Changes in Direction : $change_in_direction", $verbose ); | ||
| 736 | |||
| 737 | print "\n Semantic relatedness(hso) : $semantic_relatedness\n"; | ||
| 738 | msg( "\n Semantic relatednes(hso) : $semantic_relatedness", $verbose ); | ||
| 739 | |||
| 740 | my @months = qw(Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec); | ||
| 741 | my @weekDays = qw(Sun Mon Tue Wed Thu Fri Sat Sun); | ||
| 742 | my ($second, $minute, $hour, $dayOfMonth, $month, $yearOffset, $dayOfWeek, $dayOfYear, $daylightSavings) = localtime(); | ||
| 743 | my $year = 1900 + $yearOffset; | ||
| 744 | my $theTime = "$hour:$minute:$second, $weekDays[$dayOfWeek] $months[$month] $dayOfMonth, $year"; | ||
| 745 | msg ("\n $theTime",$verbose); | ||
| 746 | if($test_flag == 1) | ||
| 747 | { | ||
| 748 | print OUTPUT "$semantic_relatedness<>$term1<>$term2\n"; | ||
| 749 | print STDERR "final output :$semantic_relatedness<>$term1<>$term2\n"; | ||
| 750 | } | ||
| 751 | |||
| 752 | |||
| 753 | |||
| 754 | } | ||
| 755 | else | ||
| 756 | |||
| 757 | { | ||
| 758 | undef %Graph; | ||
| 759 | undef %node_cost; | ||
| 760 | # Check if this is testing mode and if the CUI does not exist. | ||
| 761 | if($test_flag == 1 && $absent != 1) | ||
| 762 | { | ||
| 763 | print OUTPUT "-1<>$term1<>$term2\n"; | ||
| 764 | print STDERR "final output :-1<>$term1<>$term2\n"; | ||
| 765 | } | ||
| 766 | print "\n No shortest allowable path found between the input terms/CUIs\n"; | ||
| 767 | } | ||
| 768 | |||
| 769 | |||
| 770 | if($test_flag == 1){ | ||
| 771 | close OUTPUT; | ||
| 772 | } | ||
| 773 | |||
| 774 | #msg("memory at end of form graph: ". memory_usage()/1024/1024 ."\n",$verbose); | ||
| 775 | |||
| 776 | } | ||
| 777 | |||
| 778 | =head2 printQueue | ||
| 779 | |||
| 780 | This subroutines prints the current contents of queue | ||
| 781 | |||
| 782 | =cut | ||
| 783 | |||
| 784 | sub printQueue { | ||
| 785 | my $q_ref = shift; | ||
| 786 | my @queue = @$q_ref; | ||
| 787 | #msg( ("Current Queue is: "), $verbose ); | ||
| 788 | foreach my $ele (@queue) { | ||
| 789 | #msg( " $ele, $node_cost{$ele}", $verbose ); | ||
| 790 | } | ||
| 791 | } | ||
| 792 | |||
| 793 | =head2 call_getconceptproperties | ||
| 794 | |||
| 795 | This subroutines queries webservice getConceptProperties | ||
| 796 | |||
| 797 | =cut | ||
| 798 | |||
| 799 | sub call_getconceptproperties { | ||
| 800 | |||
| 801 | my $cui = shift; | ||
| 802 | my $service = shift; | ||
| 803 | my $parents_ref; | ||
| 804 | |||
| 805 | $counter ++; | ||
| 806 | #open(COUNT,">>","count.txt") or die("Error: cannot open file 'count.txt'\n"); | ||
| 807 | |||
| 808 | |||
| 809 | #print COUNT "\n call $counter : $cui "; | ||
| 810 | # Creating object of query and passing the method name along with parameters. | ||
| 811 | |||
| 812 | my $query = WebService::UMLSKS::Query->new; | ||
| 813 | |||
| 814 | # Creating Connect object to call sub get_pt while forming a query. | ||
| 815 | |||
| 816 | my $c = WebService::UMLSKS::ConnectUMLS->new; | ||
| 817 | |||
| 818 | #print "\n calling ws for cui $cui"; | ||
| 819 | $service->readable(1); | ||
| 820 | my $return_ref = ""; | ||
| 821 | |||
| 822 | |||
| 823 | $return_ref = $query->runQuery( | ||
| 824 | $service, $cui, | ||
| 825 | 'getConceptProperties', | ||
| 826 | { | ||
| 827 | casTicket => $c->get_pt(), | ||
| 828 | |||
| 829 | # use SOAP::Data->type in order to prevent | ||
| 830 | # UTF-8 strings from being encoded into base64 | ||
| 831 | # http://cookbook.soaplite.com/#internationalization%20and%20encoding | ||
| 832 | CUI => SOAP::Data->type( string => $cui ), | ||
| 833 | language => 'ENG', | ||
| 834 | release => '2010AB', | ||
| 835 | SABs => [ (@sources) ], | ||
| 836 | includeConceptAttrs => 'false', | ||
| 837 | includeSemanticTypes => 'false', | ||
| 838 | includeTerminology => 'false', | ||
| 839 | includeSuppressibles => 'false', | ||
| 840 | includeRelations => 'true', | ||
| 841 | relationTypes => [(@relations)], | ||
| 842 | #relationTypes => ['PAR','RN'], | ||
| 843 | }, | ||
| 844 | ); | ||
| 845 | |||
| 846 | if ( $return_ref eq 'undefined' ) { | ||
| 847 | print "\n The CUI/term does not exist"; | ||
| 848 | undef $return_ref; | ||
| 849 | return 'undefined'; | ||
| 850 | } | ||
| 851 | elsif ( $return_ref eq 'empty' ) { | ||
| 852 | undef $return_ref; | ||
| 853 | if($cui eq $source || $cui eq $destination){ | ||
| 854 | #print "\n No information found for $cui in current Source/s"; | ||
| 855 | |||
| 856 | if($tflag == 1) | ||
| 857 | { | ||
| 858 | $absent = 1; | ||
| 859 | open(OUT,">>","output.txt") or die("Error: cannot open file 'output.txt'\n"); | ||
| 860 | print OUTPUT "-1<>$source<>$destination\n"; | ||
| 861 | print STDERR "final output :-1<>$source<>$destination\n"; | ||
| 862 | close OUT; | ||
| 863 | } | ||
| 864 | |||
| 865 | } | ||
| 866 | |||
| 867 | return 'empty'; | ||
| 868 | } | ||
| 869 | else { | ||
| 870 | |||
| 871 | return $return_ref; | ||
| 872 | } | ||
| 873 | |||
| 874 | # print "\nhash returned by ws : $parents_ref"; | ||
| 875 | |||
| 876 | } | ||
| 877 | |||
| 878 | =head2 printHoH | ||
| 879 | |||
| 880 | This subroutines prints the current contents of hash of hash | ||
| 881 | |||
| 882 | =cut | ||
| 883 | |||
| 884 | sub printHoH { | ||
| 885 | |||
| 886 | my $hoh = shift; | ||
| 887 | my %hoh = %$hoh; | ||
| 888 | |||
| 889 | msg( "\nin printHoH : Graph is :", $verbose ); | ||
| 890 | foreach my $ngram ( keys %hoh ) { | ||
| 891 | msg( "\n******************************************", $verbose ); | ||
| 892 | msg( "\n" . $ngram . "{", $verbose ); | ||
| 893 | foreach my $word ( keys %{ $hoh{$ngram} } ) { | ||
| 894 | msg( "\n", $verbose ); | ||
| 895 | msg( $word . "=>" . $hoh{$ngram}{$word}, $verbose ); | ||
| 896 | } | ||
| 897 | msg( "\n}", $verbose ); | ||
| 898 | |||
| 899 | } | ||
| 900 | |||
| 901 | } | ||
| 902 | |||
| 903 | undef %node_cost; | ||
| 904 | undef %Graph; | ||
| 905 | undef @sources; | ||
| 906 | undef @relations; | ||
| 907 | undef @directions; | ||
| 908 | |||
| 909 | 1; | ||
| 910 | |||
| 911 | #-------------------------------PERLDOC STARTS HERE------------------------------------------------------------- | ||
| 912 | |||
| 913 | |||
| 914 | |||
| 915 | =head1 SEE ALSO | ||
| 916 | |||
| 917 | ValidateTerm.pm GetUserData.pm Query.pm ws-getUMLSInfo.pl FormGraph.pm GetAllowablePath.pm | ||
| 918 | |||
| 919 | =cut | ||
| 920 | |||
| 921 | =head1 AUTHORS | ||
| 922 | |||
| 923 | Mugdha Choudhari, University of Minnesota Duluth | ||
| 924 | E<lt>chou0130 at d.umn.eduE<gt> | ||
| 925 | |||
| 926 | Ted Pedersen, University of Minnesota Duluth | ||
| 927 | E<lt>tpederse at d.umn.eduE<gt> | ||
| 928 | |||
| 929 | |||
| 930 | |||
| 931 | |||
| 932 | =head1 COPYRIGHT | ||
| 933 | |||
| 934 | Copyright (C) 2011, Mugdha Choudhari, Ted Pedersen | ||
| 935 | |||
| 936 | This program is free software; you can redistribute it and/or modify | ||
| 937 | it under the terms of the GNU General Public License as published by | ||
| 938 | the Free Software Foundation; either version 2 of the License, or (at | ||
| 939 | your option) any later version. | ||
| 940 | |||
| 941 | This program is distributed in the hope that it will be useful, but | ||
| 942 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 943 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
| 944 | General Public License for more details. | ||
| 945 | |||
| 946 | You should have received a copy of the GNU General Public License | ||
| 947 | along with this program; if not, write to | ||
| 948 | The Free Software Foundation, Inc., | ||
| 949 | 59 Temple Place - Suite 330, | ||
| 950 | Boston, MA 02111-1307, USA. | ||
| 951 | |||
| 952 | =cut | ||
| 953 | |||
| 954 | #---------------------------------PERLDOC ENDS HERE--------------------------------------------------------------- |