lib/WebService/UMLSKS/GetAllowablePaths.pm untested

filter: Statementstmt 0.0% 0 / 137 Branchbran 0.0% 0 / 18 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 0.0% 0 / 12 Podpod 0.0% 0 / 5 totaltotal 0.0% 0 / 172 CC 10 SCAR 34.0
CC
10
Cov
0%
get_shortest_path_info
72.0
getCost
12.0
new
2.0
CRAP 30.1
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;