in reply to find shortest path for each query from a CSV file
I could not resist but I will leave the testing to you. I also suspect you have circles in your data. Being lazy, I have also used some global variables.
use warnings; no warnings 'recursion'; use strict; <DATA>; # Skip the headers (first row). my %edges; my %kids; while (<DATA>) { chomp; my ($child, $parent, $likelihood) = split /\t/; $edges{$parent}{$child} = $likelihood; $kids{$child} = 1; } my $nkids = scalar keys %kids; my %pathes = ( Q => { path => [ 'Q' ], lh => [] } ); sub shortest_pathes { my( $end, $level ) = @_; return if $level > $nkids; return unless $edges{$end}; my @lh = @{$pathes{$end}{lh}}; my @path = @{$pathes{$end}{path}}; my @pre = keys %{$edges{$end}}; for( @pre ) { if( ( !exists $pathes{$_} ) or ( scalar @{$pathes{$_}{ +path}} > 1 + scalar @path ) ) { $pathes{$_} = { path => [ $_, @path ], lh => [ + $edges{$end}{$_}, @lh ] }; } } shortest_pathes( $_, $level+1 ) for @pre; } shortest_pathes 'Q', 0; delete $pathes{Q}; for (sort {substr($a,1) <=> substr($b,1)} keys %pathes) { print "$_\t"; print join "<-", @{$pathes{$_}{path}}; print "\t"; print join ".", @{$pathes{$_}{lh}}; print "\n"; } __DATA__ child, Parent, likelihood M7 Q P M54 M7 Pl M213 M54 E M206 M54 E M194 M54 E M53 M7 Pl M186 M53 Pl M194 M53 Pl M187 M53 E M204 M53 E M201 M53 E M202 M53 E M179 M53 E M13 M53 E M157 M53 E M173 M53 E M205 M53 E M195 M53 E M196 M53 E M197 M53 E M198 M53 E M57 M7 E M44 M7 E M61 M7 E M13 M7 E M50 M7 E M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M51 M7 E M174 M51 Pl M50 M51 Pl M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M173 M51 Pl M175 M51 E M176 M51 E M62 M7 E M55 M7 E M17 Q P M83 M17 Pl M54 M17 Pl M213 M54 E M206 M54 E M194 M54 E M84 M17 E M101 M17 E M98 M17 E M99 M17 E M76 M17 E M206 M76 P M278 M76 E M289 M76 E M13 M76 E M282 M76 E M283 M76 E M294 M76 E M285 M76 E M13 M17 E M88 M17 E M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M89 M17 E M174 M89 P M88 M89 P M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M326 M89 Pl M333 M89 E M335 M89 E M336 M89 E M283 M89 E M330 M89 E M331 M89 E M332 M89 E M102 M17 E M92 M17 E M93 M17 E M94 M17 E M95 M17 E M22 Q E M6 Q E M28 M6 P M115 M28 Pl M114 M28 Pl M112 M28 E M117 M28 E M113 M28 E M107 M28 E M33 M28 E M50 M28 E M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M51 M28 E M174 M51 Pl M50 M51 Pl M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M173 M51 Pl M175 M51 E M176 M51 E M7 M28 E M54 M7 Pl M213 M54 E M206 M54 E M194 M54 E M53 M7 Pl M186 M53 Pl M194 M53 Pl M187 M53 E M204 M53 E M201 M53 E M202 M53 E M179 M53 E M13 M53 E M157 M53 E M173 M53 E M205 M53 E M195 M53 E M196 M53 E M197 M53 E M198 M53 E M57 M7 E M44 M7 E M61 M7 E M13 M7 E M50 M7 E M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M51 M7 E M174 M51 Pl M50 M51 Pl M158 M50 P M157 M50 P M153 M50 Pl M162 M50 E M164 M50 E M165 M50 E M147 M50 E M159 M50 E M160 M50 E M161 M50 E M173 M51 Pl M175 M51 E M176 M51 E M62 M7 E M55 M7 E M36 M6 P M126 M36 Pl M115 M36 Pl M131 M36 E M132 M36 E M127 M36 E M138 M36 E M139 M36 E M120 M36 E M33 M36 E M88 M36 E M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M89 M36 E M174 M89 P M88 M89 P M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M326 M89 Pl M333 M89 E M335 M89 E M336 M89 E M283 M89 E M330 M89 E M331 M89 E M332 M89 E M134 M36 E M135 M36 E M136 M36 E M17 M36 E M83 M17 Pl M54 M17 Pl M213 M54 E M206 M54 E M194 M54 E M84 M17 E M101 M17 E M98 M17 E M99 M17 E M76 M17 E M206 M76 P M278 M76 E M289 M76 E M13 M76 E M282 M76 E M283 M76 E M294 M76 E M285 M76 E M13 M17 E M88 M17 E M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M89 M17 E M174 M89 P M88 M89 P M158 M88 P M306 M88 Pl M307 M88 Pl M317 M88 E M318 M88 E M319 M88 E M320 M88 E M282 M88 E M299 M88 E M311 M88 E M312 M88 E M313 M88 E M314 M88 E M315 M88 E M316 M88 E M326 M89 Pl M333 M89 E M335 M89 E M336 M89 E M283 M89 E M330 M89 E M331 M89 E M332 M89 E M102 M17 E M92 M17 E M93 M17 E M94 M17 E M95 M17 E M34 M6 E M35 M6 E Q M6 E M10 Q E M46 M10 P M216 M46 P M189 M46 P M244 M46 E M246 M46 E M247 M46 E M248 M46 E M249 M46 E M243 M46 E M70 M10 P M257 M70 Pl M216 M70 Pl M267 M70 E M265 M70 E M266 M70 E M250 M70 E M268 M70 E M269 M70 E M270 M70 E M261 M70 E M262 M70 E M263 M70 E M264 M70 E M72 M10 E M75 M10 E M71 M10 E M23 Q E M18 Q E
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^2: find shortest path for each query from a CSV file
by zing (Beadle) on Nov 22, 2013 at 10:53 UTC |