diff options
| -rw-r--r-- | NEWS | 2 | ||||
| -rw-r--r-- | URPM/Resolve.pm | 67 | ||||
| -rw-r--r-- | t/sort_graph.t | 68 |
3 files changed, 116 insertions, 21 deletions
@@ -1,3 +1,5 @@ +- fix bug in sort_graph (used by build_transaction_set) + Version 1.79 - 3 September 2007, by Pascal "Pixel" Rigaux - fix bug in sort_graph (used by build_transaction_set) diff --git a/URPM/Resolve.pm b/URPM/Resolve.pm index 629e5b5..6820995 100644 --- a/URPM/Resolve.pm +++ b/URPM/Resolve.pm @@ -1268,13 +1268,39 @@ sub reverse_multi_hash { sub sort_graph { my ($nodes, $edges) = @_; + #require Data::Dumper; + #warn Data::Dumper::Dumper($nodes, $edges); + my %nodes_h = map { $_ => 1 } @$nodes; - my (%examined, %added, @sorted); + my (%loops, %added, @sorted); + + my $merge_loops = sub { + my ($l1, $l2) = @_; + my $l = [ @$l1, @$l2 ]; + $loops{$_} = $l foreach @$l; + $l; + }; + my $add_loop = sub { + my (@ids) = @_; + my ($main, @other) = uniq(grep { $_ } map { $loops{$_} } @ids); + $main ||= []; + if (@other) { + $main = $merge_loops->($main, $_) foreach @other; + } + foreach (grep { !$loops{$_} } @ids) { + $loops{$_} ||= $main; + push @$main, $_; + my @l_ = uniq(@$main); + @l_ == @$main or die ''; + } +# warn "# loops: ", join(' ', map { join('+', @$_) } uniq(values %loops)), "\n"; + }; my $recurse; $recurse = sub { my ($id, @ids) = @_; +# warn "# recurse $id @ids\n"; - my ($loop_ahead, %loop); + my $loop_ahead; foreach my $p_id (@{$edges->{$id}}) { if ($p_id == $id) { # don't care @@ -1284,40 +1310,42 @@ sub sort_graph { my $begin = 1; my @l = grep { $begin &&= $_ != $p_id } @ids; $loop_ahead = 1; - @loop{$p_id, $id, @l} = undef; - } elsif (!exists $examined{$p_id}) { - $examined{$p_id} = undef; - my @l = $recurse->($p_id, $id, @ids); - if (@l) { - @loop{@l} = undef; - #- we would need to compute loop_ahead. we will do it below only once, and if not already set + $add_loop->($p_id, $id, @l); + } elsif ($loops{$p_id}) { + my $take; + if (my @l = grep { $take ||= $loops{$_} && $loops{$_} == $loops{$p_id} } reverse @ids) { + $loop_ahead = 1; +# warn "# loop to existing one $p_id, $id, @l\n"; + $add_loop->($p_id, $id, @l); } + } else { + $recurse->($p_id, $id, @ids); + #- we would need to compute loop_ahead. we will do it below only once, and if not already set } } - if (!$loop_ahead && grep { exists $loop{$_} } @ids) { + if (!$loop_ahead && $loops{$id} && grep { exists $loops{$_} && $loops{$_} == $loops{$id} } @ids) { $loop_ahead = 1; } if (!$loop_ahead) { #- it's now a leaf or a loop we're done with - my @toadd = %loop ? keys %loop : $id; + my @toadd = $loops{$id} ? @{$loops{$id}} : $id; $added{$_} = undef foreach @toadd; +# warn "# adding ", join('+', @toadd), " for $id\n"; push @sorted, [ uniq(grep { $nodes_h{$_} } @toadd) ]; - (); - } else { - #- still looping, going up - keys %loop; } }; !exists $added{$_} and $recurse->($_) foreach @$nodes; - check_graph_is_sorted(\@sorted, $edges) or die "sort_graph failed"; +# warn "# result: ", join(' ', map { join('+', @$_) } @sorted), "\n"; + check_graph_is_sorted(\@sorted, $nodes, $edges) or die "sort_graph failed"; + @sorted; } sub check_graph_is_sorted { - my ($sorted, $edges) = @_; + my ($sorted, $nodes, $edges) = @_; my $i = 1; my %nb; @@ -1326,8 +1354,11 @@ sub check_graph_is_sorted { $i++; } my $nb_errors = 0; - my $error = sub { $nb_errors++; warn "$_[0]\n" }; + my $error = sub { $nb_errors++; warn "error: $_[0]\n" }; + foreach my $id (@$nodes) { + $nb{$id} or $error->("missing $id in sort_graph list"); + } foreach my $id (keys %$edges) { my $id_i = $nb{$id} or next; foreach my $req (@{$edges->{$id}}) { diff --git a/t/sort_graph.t b/t/sort_graph.t index 7f2a305..73750c4 100644 --- a/t/sort_graph.t +++ b/t/sort_graph.t @@ -1,14 +1,76 @@ #!/usr/bin/perl use strict; -use Test::More tests => 1; +use Test::More 'no_plan'; use URPM; my ($list_unsorted, $requires); +$list_unsorted = [ 0, 1, 2 ]; +$requires = { 2 => [ 1 ], 1 => [ 0 ], 0 => [ 1, 2 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0, 1, 2, 3, 4 ]; +$requires = { '0' => [], '1' => [ 2, 3 ], '2' => [ 4 ], '3' => [ 4 ], '4' => [ 1, 0 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0, 3, 4, 5, 6, 10 ]; +$requires = { '0' => [ 4 ], '3' => [ 5 ], '4' => [ 6, 5 ], '5' => [ 10 ], '6' => [ 10, 3 ], '10' => [ 6 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0, 1, 2, 3, 4 ]; +$requires = { '0' => [ 0 ], '1' => [ 4 ], '2' => [], '3' => [ 3 ], '4' => [ 0, 2 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0, 1, 2, 3, 4 ]; +$requires = { '0' => [], '1' => [ 3, 1 ], '2' => [ 2 ], '3' => [ 3 ], '4' => [ 1, 2 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0, 1, 2, 3, 4 ]; +$requires = { '0' => [ 3, 4 ], '1' => [ 0, 3 ], '2' => [], '3' => [ 4 ], '4' => [ 0, 3 ] }; +check_it($list_unsorted, $requires, 0); + $list_unsorted = [ 92, 94, 133, 137, 5826, 5828, 5830, 5831, 5836, 5839, 5842, 5844, 5845, 5848, 5849, 5851, 5856, 5859, 5864, 5873, 5882, 5883, 5890, 5892, 5894, 5895, 5897, 5900, 5913, 5915, 5916, 5917, 5924, 5925, 5926, 5928, 5929, 5932, 5936, 5937, 5938, 5943, 5948, 5953, 5955, 5956, 5959, 5960, 5961, 5962, 5964, 5968, 5969, 5970, 5974, 6008, 6009, 6010, 6012, 6110, 6115, 6119, 6120, 6127, 6129, 6132, 6135, 6164, 6165, 6166, 16841, 16842, 16844, 16845, 16890, 17009, 17011, 17013, 17156, 17157, 17169 ]; $requires = { '17011' => [], '5883' => [], '5956' => [ 5955, 5839, 5959, 5964 ], '5897' => [], '5953' => [ 5936, 5943 ], '5894' => [ 5839 ], '17013' => [ 6135 ], '5936' => [ 5943 ], '5826' => [], '6135' => [ 5839 ], '16845' => [ 5839 ], '5974' => [ 5974, 5839, 5964 ], '5851' => [ 5856, 5849 ], '6115' => [], '92' => [ 5839, 5925, 94 ], '6010' => [ 6008, 6009, 6010 ], '5882' => [], '5970' => [ 5955, 5839, 5969 ], '16841' => [], '5926' => [ 5953, 5936, 5926, 6009, 5943, 5928 ], '17156' => [ 17157, 17156 ], '5848' => [ 5856 ], '6008' => [ 6009, 5839, 6008, 6010 ], '5842' => [ 5839, 5844 ], '16844' => [ 16845, 16841, 16842, 5839 ], '16842' => [], '5955' => [ 5970 ], '6119' => [ 6119 ], '133' => [ 5839 ], '6009' => [ 6008, 6009, 6010 ], '5831' => [], '5839' => [ 5839 ], '6165' => [ 5839 ], '5830' => [], '5960' => [ 5839, 5962 ], '5932' => [ 5953, 5936, 6009, 5932, 5938, 5943, 5928 ], '5924' => [ 5839 ], '5828' => [], '5959' => [ 5969 ], '5890' => [ 5897 ], '17169' => [ 17157 ], '5937' => [ 5936, 5943 ], '137' => [ 133, 5839, 5925 ], '5895' => [], '5892' => [], '6110' => [ 5839 ], '6127' => [], '5900' => [], '5948' => [ 5953, 5936, 6009, 5932, 5937, 5948, 5929, 5938, 5943, 5928 ], '6120' => [], '5929' => [ 5936, 5943 ], '5961' => [ 5839 ], '5964' => [ 5956, 5970, 5839 ], '6164' => [ 6119, 6120, 6164 ], '5925' => [ 5924 ], '5844' => [ 5842, 5844 ], '5864' => [], '17157' => [ 5839, 17156, 17157 ], '5969' => [], '5962' => [ 6009, 5839, 5962 ], '5913' => [ 6115, 5839, 5917 ], '5968' => [ 5970, 5839, 5959 ], '5915' => [], '6166' => [ 5839, 6165 ], '6132' => [ 5839, 6129 ], '6129' => [ 5839, 6127, 6132 ], '5938' => [ 5936, 5943 ], '5836' => [], '5943' => [ 5953, 5936, 6009, 5937, 5948, 5929, 5928 ], '5856' => [ 5897 ], '5873' => [], '5917' => [ 5839, 5856, 5917, 5849 ], '17009' => [], '94' => [ 5839 ], '5859' => [ 5856 ], '16890' => [], '5845' => [ 5851, 5848, 5856, 5849 ], '5928' => [ 5953, 5936, 5926, 6009, 5943, 5928 ], '5916' => [ 5915 ], '5849' => [ 5856 ], '6012' => [ 6012 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 53, 56, 118, 189, 223, 284, 286, 304, 396, 397, 403, 442, 480, 544, 556, 596, 607, 692, 729, 758, 764, 772, 778, 798, 829, 838, 840, 865, 917, 1019, 1112, 1149, 1191, 1192, 1232, 1275, 1292, 1316, 1319, 1364, 1411, 1415, 1422, 1487, 1508, 1583, 1719, 1769, 1787, 1827, 1855, 1884, 1894, 2001, 2136, 2139, 2243, 2244, 2355, 2387, 2516, 2597, 2603, 2669, 2694, 2727, 2746, 2818, 2820, 2826, 2845, 2861, 2869, 2932, 2992, 3002, 3016, 3037, 3069, 3079, 3151, 3173, 3272, 3273, 3275, 3280, 3289, 3293, 3314, 3327, 3568, 3569, 3602, 3659, 3662, 3665, 3667, 3669, 3672, 3675, 3682, 3934, 3935, 3936, 3971, 3973, 3980, 4053, 4060, 4150, 4161, 4350, 4400, 4402, 4426, 4428, 4430, 4438, 4439, 4444, 4446, 4635, 4636, 4637, 4638, 4639, 4640, 4656, 4657, 4673, 4681, 4685, 4686, 4687, 4691, 4715, 4793, 5060, 5070, 5079, 5198, 5199, 5250, 5327, 5329, 5330, 5331, 5333, 5334, 5342, 5401, 5404, 5407, 5409, 5423, 5442, 5486, 5487, 5494, 5499, 5501, 5616, 5618, 5664, 5685, 5688, 5775, 5777, 5778, 6166, 6178, 6305, 8295, 9859, 10199, 10649, 10651, 10659, 11879, 22012 ]; +$requires = { '5423' => [ 5442 ], '118' => [ 5060 ], '3934' => [ 764 ], '5250' => [], '2818' => [], '2746' => [ 1019, 764 ], '2992' => [ 5327, 1884, 4636, 917, 2603, 56, 5334 ], '3002' => [ 3069 ], '5327' => [ 3934, 2746, 5327, 1884, 4636, 1019, 397, 764, 758, 829, 2603, 4681, 5331, 1232, 5777, 5334, 1719 ], '798' => [ 3273, 2861 ], '3037' => [ 3037, 2820, 838 ], '5688' => [ 5327, 1884, 4636, 2603, 5334 ], '1884' => [ 3934, 764, 4402, 5777, 2861 ], '2516' => [ 917, 596, 2826, 56, 607, 1112, 4444 ], '2001' => [ 4060, 442, 284, 5333, 1894, 396, 5329, 4640 ], '5664' => [], '1364' => [ 5250, 1364, 4060, 917, 5401, 2243, 5407, 1411 ], '5494' => [ 480, 5501 ], '4715' => [ 3151 ], '5499' => [ 764, 865, 2387, 1232, 3973 ], '3273' => [], '4636' => [ 3934, 1884, 4636, 764, 5198, 4638, 4639, 5777, 2861, 5775 ], '1019' => [ 764 ], '4060' => [ 4060, 4053 ], '4439' => [ 1364, 4060, 3682, 2932, 729, 3665, 403, 2845, 3672, 3327, 3569, 4444 ], '397' => [ 764, 1232 ], '764' => [ 5501, 5486 ], '865' => [ 764, 2387, 3973 ], '5342' => [ 4715, 11879, 4635, 4673, 53 ], '5060' => [], '3936' => [], '3314' => [], '8295' => [], '3682' => [ 3665, 3662, 3569 ], '5198' => [ 3934, 764, 5777, 2861 ], '10649' => [ 5331, 6166 ], '4685' => [ 4687, 4686 ], '3272' => [], '11879' => [], '442' => [ 798, 1884, 3273, 442, 5778, 3935, 396, 4400 ], '4638' => [], '5778' => [ 798, 3273, 5777, 3327, 5775 ], '2932' => [ 2932 ], '1855' => [ 607, 1112 ], '2387' => [ 3973 ], '1191' => [ 5494, 1019, 5487, 480, 396 ], '3016' => [ 2746, 1191, 480, 396 ], '5404' => [ 5409 ], '284' => [ 4060, 2603 ], '5442' => [], '2136' => [ 5327, 1884, 2516, 4636, 764, 2387, 917, 596, 2603, 5409, 3293, 3973, 56, 5334, 1415, 4444 ], '2869' => [ 5494, 1232, 5487, 480, 396 ], '5070' => [ 5060 ], '4402' => [], '729' => [ 1364, 4060, 56 ], '917' => [ 917, 5401, 1411 ], '3568' => [ 764, 2387, 3973, 5501, 5486 ], '3980' => [ 5327, 1884, 4636, 4635, 2603, 5334 ], '4635' => [], '3675' => [], '758' => [ 3934, 764, 1232 ], '829' => [ 764, 1232 ], '4687' => [ 1192, 6305 ], '596' => [ 917, 596, 544 ], '5330' => [ 5423, 3934, 2746, 5327, 1884, 4636, 1019, 397, 764, 5442, 4402, 758, 829, 2603, 4681, 1232, 1319, 5777, 5334, 5501, 5486, 4161, 2861, 1719 ], '223' => [ 1855, 223, 2727, 1112 ], '772' => [], '5401' => [], '4657' => [ 4657 ], '3289' => [ 2001, 4060, 442, 5404, 284, 3293, 5333, 5329, 4640 ], '4350' => [], '5685' => [ 5688, 10649 ], '3151' => [ 5499, 764 ], '3069' => [], '3667' => [ 3675, 3659, 3662 ], '1149' => [ 2869, 829, 480, 396 ], '3935' => [ 3934, 480, 396 ], '4673' => [ 10659, 4150, 10651 ], '2603' => [ 772 ], '2243' => [], '4053' => [], '1487' => [ 5327, 1884, 2516, 4636, 764, 5060, 2387, 2136, 917, 596, 2603, 2355, 5409, 3293, 3973, 56, 4426, 5334, 4444 ], '3659' => [ 3675 ], '2694' => [ 764, 2387, 3973 ], '4681' => [ 3934, 1019, 764 ], '1769' => [ 118, 764, 865, 5060, 2387, 4402, 1769, 1232, 3602, 5777, 3973, 3173, 5079, 2861 ], '2826' => [ 2516, 5342, 917, 596, 56, 607, 1112, 4444 ], '778' => [ 397, 2869, 480, 396 ], '4639' => [ 3934, 5664, 4636, 764, 5198, 5777, 4656, 5501, 5486, 2861 ], '4430' => [ 5423, 5327, 1884, 4636, 5442, 2603, 5334, 5618 ], '5407' => [ 4060, 5401 ], '2355' => [ 5327, 1884, 2516, 4636, 10649, 2136, 917, 596, 2603, 1487, 5409, 3293, 56, 4426, 5334, 3280, 4444 ], '5409' => [], '5331' => [ 5330, 5334 ], '10199' => [], '3293' => [ 5327, 1884, 4636, 3314, 5330, 2603, 5409, 3293, 1894, 5334, 3280 ], '4446' => [], '1232' => [ 764, 5501 ], '2820' => [ 2820 ], '4637' => [], '3602' => [ 5060 ], '1192' => [ 5775 ], '1275' => [ 2820 ], '4438' => [ 2992, 5342, 917, 3568, 3675, 4446, 3669, 56, 1827, 3662, 4444 ], '556' => [ 5060, 3173 ], '22012' => [ 8295, 442, 5407, 1275, 1787, 189, 1292, 5333, 1422, 1508, 4400, 1316, 4640, 840, 4793 ], '1787' => [ 3037, 1275, 1292 ], '1319' => [ 5423, 5442, 1319, 286, 3275 ], '189' => [ 5494, 865, 5487, 480, 692, 396, 3971 ], '2597' => [ 5250, 1364, 4060, 4439, 442, 5404, 284, 2136, 729, 3289, 5333, 692, 396, 3971, 1415, 2845, 5329, 1316, 3327, 4640 ], '1292' => [ 3037, 1275 ], '5487' => [ 480, 5486 ], '5333' => [ 3934, 2746, 5327, 1884, 4636, 4060, 1019, 397, 764, 442, 5778, 1191, 3016, 284, 2869, 4402, 758, 829, 5330, 1149, 3935, 2603, 4681, 778, 1232, 5333, 5777, 4691, 3079, 396, 5334, 5501, 5486, 5329, 2861, 4640, 1719, 2669 ], '5777' => [ 2861, 5775 ], '480' => [ 5494, 189 ], '1894' => [ 5327, 1884, 4636, 764, 2603, 1894, 1583, 5334 ], '4691' => [ 1191, 3935, 4681, 480, 396 ], '3079' => [ 2869, 758, 3935, 480, 396 ], '692' => [ 2387, 480, 3971 ], '3973' => [], '5199' => [ 798, 3273, 5198, 5778, 3935, 480, 396 ], '3669' => [ 3675 ], '304' => [ 4636, 2603, 304, 5334, 2861 ], '1583' => [], '396' => [ 5494, 764, 5487, 480 ], '3173' => [], '1422' => [ 2694, 692, 396, 3971 ], '3665' => [ 3675 ], '56' => [ 2992, 917 ], '2139' => [ 2139 ], '9859' => [ 9859 ], '5616' => [ 2818, 3936, 3272, 10199, 2139, 5618 ], '4426' => [ 4430 ], '5334' => [ 764, 5060, 4402, 5334, 5079 ], '6178' => [], '10659' => [], '4656' => [ 5664, 4657 ], '1508' => [ 5250, 1364, 4060, 4439, 442, 5404, 284, 5070, 729, 3289, 1487, 2355, 2597, 5333, 692, 396, 3971, 2845, 4428, 5329, 1316, 3327, 4640 ], '4400' => [ 3273, 4402 ], '1827' => [], '6305' => [ 5775 ], '5501' => [], '838' => [ 3037, 2820 ], '5486' => [], '403' => [ 4060, 3569 ], '3971' => [ 480, 3973 ], '3662' => [ 3675, 3667 ], '286' => [ 5423, 5442 ], '2845' => [ 1364, 4060, 596, 2845, 544, 3327 ], '1415' => [ 5327, 1884, 2516, 4636, 2136, 917, 596, 2603, 5409, 5331, 3293, 56, 5334, 3280, 4444 ], '5618' => [ 5616, 5618 ], '2727' => [ 607 ], '3672' => [ 4060, 3669, 3665 ], '544' => [ 917, 596 ], '4150' => [ 4350, 556, 304, 9859, 2861, 2244 ], '4161' => [ 5423, 5060, 5442, 4402, 1319, 4161, 5079 ], '10651' => [], '5079' => [ 5060, 5079 ], '3280' => [ 5327, 1884, 4636, 2603, 5334 ], '53' => [], '6166' => [], '4428' => [ 4060, 4426, 3569 ], '607' => [], '5329' => [ 4060, 396, 5334, 5329 ], '1112' => [ 1855, 607, 1112 ], '3275' => [], '1316' => [ 5250, 2516, 1364, 4060, 4439, 729, 223, 2826, 2845, 2727 ], '2861' => [], '3327' => [ 3273 ], '4640' => [ 3934, 798, 1884, 3273, 4636, 4060, 764, 5198, 442, 4638, 5778, 4402, 3935, 4637, 5777, 5199, 396, 5501, 5486, 2861, 3327, 4640 ], '4686' => [ 5423, 5060, 5442, 4402, 1319, 5777, 4161, 5079 ], '840' => [ 118, 764, 865, 5060, 4685, 2387, 4402, 1769, 1232, 3602, 5777, 3973, 3173, 5501, 5486, 5079, 2861 ], '3569' => [], '4444' => [ 3002, 917, 3675, 4446, 4438, 3669, 56, 6178, 3662, 5618, 4444 ], '1719' => [ 1019, 764, 1232 ], '1411' => [ 917, 5401 ], '5775' => [ 5777, 2861 ], '2244' => [ 4402 ], '4793' => [], '2669' => [ 1191, 2869, 480, 396, 1719 ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 5625, 6155, 6156, 6157, 6158, 6172, 6180, 6186, 6190, 6192, 6199, 6201, 6202, 6204, 6206, 6210, 6215, 6221, 6222, 6223, 6224, 6226, 6229, 6233, 6234, 6236, 6238, 6239, 6243, 6244, 6250, 6254, 6255, 6256, 6257, 6258, 6259, 6261, 6263, 6265, 6266, 6267, 6269, 6270, 6271, 6272, 6273, 6274, 6275, 6278, 6279, 6284, 6285, 6286, 6287, 6288, 6289, 6290, 6291, 6292, 6293, 6294, 6296, 6298, 6299, 6300, 6301, 6302, 6303, 6304, 6305, 6306, 6307, 6309, 6310, 6311, 6312, 6314, 6315, 6316, 6317, 6318, 6319, 6320, 6321, 6322, 6324, 6325, 6326, 6327, 6328, 6329, 6330, 6331, 6332, 6333, 6334, 6335, 6336, 6337, 6338, 6339, 6341, 6342, 6343, 6344, 6346, 6347, 6348, 6349, 6350, 6376, 6377, 6379, 6380, 6385, 6387, 6388, 6390, 6394, 6400, 6402, 6403, 6404, 6405, 6412, 6414, 6416, 6417, 6418, 6419, 6420, 6426, 6427, 6429, 6430, 6436, 6439, 6444, 6451, 6454, 6459, 6462, 6464, 6466, 6469, 6472, 6477, 6478, 6479, 6480, 6481, 6483, 6484, 6485, 6489, 6491, 6493, 6495, 6497, 6500, 6501, 6502, 6518, 6519, 6521, 6522, 6523, 6524, 6527, 6528, 6530, 6531, 6533, 6534, 6535, 6536, 6537, 6538, 6540, 6541, 6542, 6546, 6547, 6548, 16770, 16772, 16774, 16775, 16779, 16780, 16783, 16786, 16788, 16789, 16790, 16793, 16794, 16795, 16799, 16802, 16803, 16804, 16805, 16864, 16869, 16871, 16873, 16874, 16875, 16878, 16879, 16913, 16927, 16928, 16957, 16958, 16959, 16960, 16961, 16962, 16963, 16964, 16965, 16966, 16967, 16968, 16969, 16970, 16971, 16972, 16974, 16975, 16976, 16977, 16978, 16979, 16980, 16981, 16982, 16983, 16984, 16985, 16986, 16987, 16988, 16989, 16990, 16992 ]; +$requires = { '16977' => [ '16972', '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6261' => [ '6500', '6481' ], '16775' => [ '16774', '16979', '16970', '16969', '16976', '16803', '6500', '16981', '16986', '6481' ], '6347' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6256' => [ '6287', '6284', '6274', '6273', '6257', '6278', '6271', '6269', '6288', '6286', '6275', '6289', '6272', '6254' ], '16873' => [ '16873' ], '16965' => [ '16969' ], '6535' => [ '6377', '6500', '6524', '6481' ], '6270' => [ '6279', '6548', '6519' ], '6497' => [ '6481' ], '16967' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '16774' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '16799' => [ '16783', '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6501' => [ '6484' ], '16793' => [ '16969', '16981', '16790' ], '16783' => [ '16969' ], '6518' => [ '6489', '6481' ], '6293' => [ '6293', '6300' ], '6333' => [ '6342', '6346', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6349, 6347, 6344, 6334, 6328, 6332 ], '16794' => [ '16979', '16989', '16970', '16969', '6500', '16981', '16986', '6481' ], '6222' => [ '6292', '6223', '6377', '6300' ], '16984' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '16927' => [ '16928', '6377', '6500', '6481' ], '6531' => [ '6535', '6306', '6480', '6527', '6158', '6377', '6500', '6521', '6524', '6481' ], '6405' => [ '6416' ], '16786' => [ '16979', '16795', '16970', '16969', '16976', '6500', '16981', '16986', '6481' ], '6541' => [ '6541', '6390', '6426' ], '6263' => [ '6292', '6267', '6342', '6266', '6300' ], '6341' => [ '6347', '6333', '6341', '6334', '6332', '6342', '6329', '6344', '6337', '6348', '6328', '6339', '6346', '6343', '6330', '6335', '6349' ], '16802' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6334' => [ '6334', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6342, 6328, 6332 ], '6290' => [ '6292', '6390', '6426', '6500', '6300', '6481' ], '6522' => [ '6531', '6527', '6537', '6536', '6523', '6534' ], '6527' => [ '6377', '6500', '6524', '6481' ], '16789' => [ '16969' ], '16982' => [ '16979', '16989', '16970', '16969', '6500', '16981', '16986', '6481' ], '6495' => [ '6489' ], '16804' => [ '16969', '6500', '6481' ], '16980' => [ '16979', '16989', '16970', '16969', '16976', '6500', '16981', '16986', '6481', '16961' ], '16928' => [ '16927' ], '16989' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6332' => [ '6342', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6190' => [ '6192' ], '6292' => [ '6292', '6298', '6300' ], '6298' => [ '6290', '6300' ], '6239' => [ '6484', '6501', '6483', '6480', '6489', '6158', '6416', '6462', '6500', '6155', '6481', '6417' ], '6267' => [ '6292', '6267', '6342', '6266', '6300' ], '6186' => [ '6376', '6292', '6298', '6186', '6300' ], '16958' => [ '16979', '16969', '6500', '16986', '6481' ], '6419' => [ '6342', '6339' ], '6394' => [ '6306', '6292', '6298', '6394', '6300', '6387' ], '6412' => [ '6430', '6390' ], '6204' => [ '6306', '6292', '6377', '6500', '6300', '6202', '6481' ], '6229' => [ '6233' ], '6342' => [ '6261', '6334', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6342, 6328, 6332 ], '6430' => [ '6426' ], '16795' => [ '16979', '16970', '16969', '16976', '6500', '16981', '16986', '6481' ], '6390' => [ '6426' ], '16779' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6533' => [ '6377', '6500', '6481' ], '6478' => [ '6500' ], '16970' => [ '16979', '16969', '6500', '16981', '16986', '6481' ], '16987' => [ '16969' ], '6329' => [ '6342', '6346', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6349, 6347, 6344, 6334, 6328, 6332 ], '6530' => [ '6377', '6500', '6481' ], '16869' => [ '16869' ], '16974' => [ '16979', '16989', '16970', '16969', '16976', '6500', '16981', '16986', '6481' ], '6226' => [ '5625' ], '6528' => [ '6377', '6500', '6481' ], '6344' => [ '6333', '6342', 6335, 6348, 6330, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6444' => [ '6292', '6300' ], '6156' => [ '6155' ], '6491' => [ '6484' ], '6337' => [ '6342', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6477' => [ '6485' ], '16957' => [ '16969' ], '6519' => [ '6489' ], '6348' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6328' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6266' => [ '6342' ], '16976' => [ '16979', '16989', '16970', '16969', '6500', '16981', '16986', '6481' ], '16990' => [ '16969' ], '6547' => [ '6489', '6481' ], '6537' => [ '6535', '6531', '6528', '6377', '6500', '6481' ], '6404' => [ '6403' ], '6388' => [ '6377' ], '6310' => [ '6320' ], '6466' => [ '6462' ], '16803' => [ '16774', '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '16983' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '6454' => [ '6439', '6292', '6377', '6300' ], '16874' => [ '6206' ], '6540' => [ '6541' ], '6244' => [ '6270', '6311', '5625', '6310', '6259', '6255' ], '16879' => [ '16869', '16879', '16864' ], '6299' => [ '6293', '6290', '6292', '6299', '6500', '6300', '6481' ], '16805' => [ '16965', '16972', '16979', '16989', '16970', '16969', '16976', '6500', '16981', '16986', '6481' ], '6339' => [ '6342', '6346', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6349, 6347, 6344, 6334, 6328, 6332 ], '6400' => [ '6394' ], '6221' => [ '6292', '6300', '6224' ], '16966' => [ '16979', '16969', '6500', '16986', '6481' ], '16964' => [ '16972' ], '16971' => [ '16979', '16969', '16990', '6500', '16986', '6481' ], '6300' => [ '6300' ], '6346' => [ '6342', '6339', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6202' => [ '6292', '6377', '6300', '6481' ], '6536' => [ '6535', '6531', '6377', '6500', '6521', '6481' ], '16975' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481' ], '16986' => [ '16979', '16969', '6500', '6481' ], '6385' => [ '6376' ], '16992' => [ '16972', '16979', '16982', '16989', '16970', '16969', '16976', '16985', '6500', '16981', '16986', '6481', '16961' ], '6538' => [ '6535', '6530', '6377', '6500', '6481' ], '6479' => [ '6483' ], '6343' => [ '6342', 6335, 6348, 6330, 6333, 6337, 6343, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6414' => [ '6417' ], '6523' => [ '6533', '6377', '6500', '6481' ], '6534' => [ '6535', '6531', '6377', '6500', '6481' ], '6234' => [ '6236' ], '6330' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6493' => [ '6480' ], '6521' => [ '6377', '6500', '6521', '6481' ], '6335' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '6524' => [ '6480', '6530', '6377', '6500', '6521', '6524', '6199', '6481' ], '16772' => [ '16775', '16774', '16979', '16970', '16969', '16976', '16803', '16983', '6500', '16981', '16986', '6481' ], '6349' => [ '6342', '6343', 6335, 6348, 6330, 6333, 6337, 6329, 6339, 6346, 6349, 6347, 6344, 6334, 6328, 6332 ], '16864' => [ '16871' ], '6258' => [ '6258' ], '16968' => [ '16977', '16960', '16972', '16979', '16982', '16980', '16989', '16958', '16970', '16987', '16974', '16969', '16957', '16976', '16983', '16985', '6500', '16964', '16981', '16986', '16992', '16968', '6481', '16961', '16988', '16963', '16959' ], '16878' => [ '16878' ], '16978' => [ '16979', '16989', '16970', '16969', '6500', '16981', '16986', '6481' ], '6502' => [ '6501', '6491' ], '6157' => [ '6158' ], '16788' => [ '16979', '16969', '6500', '16986', '6481' ], '16790' => [ '16969' ], '16770' => [ '16965', '16979', '16989', '16970', '16974', '16969', '16990', '16976', '16805', '6500', '16971', '16981', '16986', '6481' ], '6210' => [ '6306', '6210' ], '6379' => [ '6387' ], '6469' => [ '6427' ], '6259' => [ '6518', '6547' ], '6206' => [ '6206' ], '16961' => [ '16979', '16989', '16970', '16969', '6500', '16981', '16986', '6481' ], '16963' => [ '16979', '16969', '6500', '16986', '6481' ], '6250' => [ '6256', '6244' ], '16988' => [ '16969', '16985' ], '16959' => [ '16979', '16970', '16969', '6500', '16981', '16986', '6481', '16963' ] }; +check_it($list_unsorted, $requires, 0); + +$list_unsorted = [ 0 .. 10 ]; +check_it($list_unsorted, create_random($list_unsorted), 1) foreach 1 .. 10000; + + +sub check_it { + my ($list_unsorted, $requires, $dump_it) = @_; + + my @sorted = eval { URPM::sort_graph($list_unsorted, $requires) }; + ok(@sorted > 0); + + if (!@sorted && $dump_it) { + require Data::Dumper; + $Data::Dumper::Sortkeys = 1; + warn Data::Dumper::Dumper($list_unsorted, $requires); + warn "$@\n"; + exit 1; + } +} + + +sub create_random { + my ($list_unsorted) = @_; + my %requires; -eval { URPM::sort_graph($list_unsorted, $requires) }; -ok(!$@); + foreach my $i (@$list_unsorted) { + my $nb = int(rand(1) * 2.8); + push @{$requires{$i}}, grep { $_ != $i } uniq(map { int(rand @$list_unsorted) } 1 .. $nb); + } + \%requires; +} +sub uniq { my %l; $l{$_} = 1 foreach @_; grep { delete $l{$_} } @_ } |