From 840a4fc787d962401b08113bd5bb866b07afe03f Mon Sep 17 00:00:00 2001 From: Pasqualino Ferrentino Date: Thu, 23 Aug 2007 14:55:18 +0200 Subject: [PATCH] now I have also the outgoing net, which was simpler but not very simple --- src/lib/Bcd/Data/Trust.pm | 193 ++++++++++++++++++++++++++++++++++++++++++---- src/t/TestTrust.pm | 21 +++++ 2 files changed, 197 insertions(+), 17 deletions(-) diff --git a/src/lib/Bcd/Data/Trust.pm b/src/lib/Bcd/Data/Trust.pm index 1016bed..0df02fa 100644 --- a/src/lib/Bcd/Data/Trust.pm +++ b/src/lib/Bcd/Data/Trust.pm @@ -536,6 +536,89 @@ sub _get_maximum_reachable_set{ } +#this function should be simpler than the incoming, because I go only forward... +sub get_outgoing_trust_net{ + my ($self, $stash, $u_start) = @_; + + #the reachable set is always the same, all the ant nest. + my $set_to_reach = $self->_get_maximum_reachable_set($u_start, $stash); + + #I can reach myself with no path, and the f is one + my $current_outgoing_net = { + $u_start => [[$u_start], [], 1 ], + }; + + my ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($u_start, $stash); + + my $cache_alfa_bias = { + $u_start => [$alfa_cur, $bias_cur], + }; + + #I have reached myself, so I can delete myself from the set + delete ($set_to_reach->{$u_start}); + + #the first level is only myself, from which I always start + my $current_level_set = {$u_start => 1,}; + + #and then I will recurse.... + $self->_helper_recursive_for_outgoing_trust + ($stash, $current_level_set, $set_to_reach, $current_outgoing_net, $cache_alfa_bias); + + return $current_outgoing_net; +} + +sub _helper_recursive_for_outgoing_trust{ + my ($self, $stash, $current_level_set, $set_to_reach, $current_outgoing_net, $cache_alfa_bias) = @_; + + #end of recursion? + if (scalar(keys(%{$set_to_reach})) == 0){ + return; + } + + #the idea is simple: just take all the destinations from the + #current level set which are not already inside the current + #incoming net. For each of them you compute the trust from the + #current level set and you take the maximum trust. + + #the next level set at first is empty. + my %next_level_set; + my %building_outgoing_net; + + foreach(keys(%{$current_level_set})){ + #print "I am $_ ! \n"; + my $user_from = $_; + #ok, I get all the destinations... + my $list_of_reachables = $self->_get_all_destinations_from_user_within_sets + ($stash, $_, $current_outgoing_net, $set_to_reach); + + + foreach (@{$list_of_reachables}){ + #print "I can reach $_->[0], with trust $_->[1]\n"; + + $self->_tentative_add_this_ant_to_the_outgoing_net + ($stash, $_->[0], $_->[1], $user_from, $current_outgoing_net, $cache_alfa_bias, + \%building_outgoing_net); + + #this ant will in any case participate in the next recursion step... + $next_level_set{$_->[0]} = 1; + } + } + + #I delete AFTER the loop the users, because they are needed inside the loop. + foreach(keys(%next_level_set)){ + delete $set_to_reach->{$_}; + } + + #I update the current outgoing net + foreach(keys(%building_outgoing_net)){ + $current_outgoing_net->{$_} = $building_outgoing_net{$_}; + } + + #recurse inside the next level set + $self->_helper_recursive_for_outgoing_trust + ($stash, \%next_level_set, $set_to_reach, $current_outgoing_net, $cache_alfa_bias); +} + #this function simply calculates the trust which other ants have in #this user. The incoming trust is ALWAYS limited to the ant nest sub get_incoming_trust_net{ @@ -549,7 +632,7 @@ sub get_incoming_trust_net{ #I can reach myself with no path, and the f is one my $current_incoming_net = { - $u_start => [[$u_start], [1], 1 ], + $u_start => [[$u_start], [], 1 ], }; my ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($u_start, $stash); @@ -597,7 +680,7 @@ sub _helper_recursive_for_incoming_trust{ foreach(keys(%{$current_level_set})){ #print "I am $_ ! \n"; #get all the origins which are already computed, so they belong to the set to reach... - my $list_of_reachables = $self->_get_all_origins_from_user + my $list_of_reachables = $self->_get_all_origins_from_user_within_sets ($stash, $_, $current_incoming_net, $set_to_reach); foreach (@{$list_of_reachables}){ @@ -631,6 +714,58 @@ sub deep_copy { } else { die "what type is $_?" } } +sub _tentative_add_this_ant_to_the_outgoing_net{ + my ($self, $stash, $user, $trust_to_user, $user_from, + $current_outgoing_net, $cache_alfa_bias, $building_outgoing_net) = @_; + + #I don't have to compute all the destinations or whatever, I need only the user + #from I come. + + #first of all, if this is the first time let's get the alpha bias for this user... + my $compare_needed = 1; + my $trust_to_win; + + if (! exists ($building_outgoing_net->{$user})){ + my ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($user, $stash); + $cache_alfa_bias->{$user} = [$alfa_cur, $bias_cur]; + + #I am the first, so in any case I win! + $compare_needed = 0; + #print "this is the first time for $user, no compare needed\n"; + } else { + $trust_to_win = $building_outgoing_net->{$user}->[2]; + #print "this is NOT THE FIRST time for $user, I must win $trust_to_win\n"; + } + + #ok, now I get the path which leads to the user from + my $path_to_user_from = $current_outgoing_net->{$user_from}; + #print "this is the old path......\n"; + #print Dumper($path_to_user_from); + + #I make a copy + my $tentative_path = deep_copy($path_to_user_from); + #print "this is the new path the trust is $trust_to_user\n"; + + #I push to the right, because I am going outside! + push (@{$tentative_path->[0]}, $user); + push (@{$tentative_path->[1]}, $trust_to_user); + + #print Dumper($tentative_path); + + #ok, I can compute the trust of this path.. + my $trust = $self->compute_trust_on_this_path($tentative_path, $cache_alfa_bias); + + #print "the trust complete of this path is: $trust\n"; + if ($compare_needed == 0 or $trust > $trust_to_win){ + #print "this trust WINS, or the compare was not needed!\n"; + $building_outgoing_net->{$user} = $tentative_path; + #and this is the winner to beat next time + $tentative_path->[2] = $trust; + } else { + #print "this trust LOOSES\n"; + } +} + sub _add_this_ant_to_the_incoming_net{ my ($self, $stash, $user, $current_level_set, $current_incoming_net, $cache_alfa_bias) = @_; @@ -732,9 +867,9 @@ sub compute_trust_on_this_path{ return $trust; } -sub _get_all_origins_from_user{ - my ($self, $stash, $user, $current_incoming_net, $set_to_reach) = @_; - +sub _get_all_paths_from_users_in_set_and_not_reached{ + my ($self, $stash, $user, $reached_set, $set_to_reach, $ingoing) = @_; + my $st = $stash->get_statement(GET_TRUSTS_FROM_USER, $self); $st->bind_param(1,$user); $st->bind_param(2,$user); @@ -747,33 +882,57 @@ sub _get_all_origins_from_user{ my $t_u2_u1; $st->bind_columns(undef, \$u1, \$u2, \$t_u1_u2, \$t_u2_u1); - my @origins = (); + my @paths = (); while ( defined($st->fetch()) ) { - my @orig; + my @path; if ($u1 == $user){ - #ok, I am on the left - #if the origin is already computed go next - next if exists($current_incoming_net->{$u2}); + #ok, I am on the left, I am u1 + next if exists($reached_set->{$u2}); next if !exists($set_to_reach->{$u2}); - push (@orig, $u2); - push (@orig, $t_u2_u1); + push (@path, $u2); + if ($ingoing == 1){ + push (@path, $t_u2_u1); + } else { + push (@path, $t_u1_u2); + } } else { - next if exists($current_incoming_net->{$u1}); + #I am on the right side, I am u2 + next if exists($reached_set->{$u1}); next if !exists($set_to_reach->{$u1}); - push (@orig, $u1); - push (@orig, $t_u1_u2); + push (@path, $u1); + + if ($ingoing == 1){ + push (@path, $t_u1_u2); + } else { + push (@path, $t_u2_u1); + } } - push(@origins, \@orig); + push(@paths, \@path); } $st->finish(); - return \@origins; + return \@paths; + +} + +sub _get_all_destinations_from_user_within_sets{ + my ($self, $stash, $user, $reached_set, $set_to_reach) = @_; + + return $self->_get_all_paths_from_users_in_set_and_not_reached + ($stash, $user, $reached_set, $set_to_reach, 0); +} + +sub _get_all_origins_from_user_within_sets{ + my ($self, $stash, $user, $reached_set, $set_to_reach) = @_; + + return $self->_get_all_paths_from_users_in_set_and_not_reached + ($stash, $user, $reached_set, $set_to_reach, 1); } #This functions returns the reachable set inside the ant nest. diff --git a/src/t/TestTrust.pm b/src/t/TestTrust.pm index 19abfc9..fb89f6f 100644 --- a/src/t/TestTrust.pm +++ b/src/t/TestTrust.pm @@ -186,6 +186,7 @@ sub test_trust{ $self->_test_get_trust(); $self->_test_incoming_net(); + $self->_test_outgoing_net(); #these tests MUST be run in sequence. $self->_test_new_booking(); @@ -196,6 +197,26 @@ sub test_trust{ $self->_test_get_backupped_trusts(); } +sub _test_outgoing_net{ + my $self = shift; + my $stash = $self->{stash}; + print "."; + + #print "_________________________ test outgoing net\n"; + my $outgoing_net; + $outgoing_net = Bcd::Data::Trust->get_outgoing_trust_net($stash, $user_ids[5]); + $self->assert_equals(8, scalar(keys(%{$outgoing_net}))); + #print Dumper($outgoing_net); + + my $trust_4 = $outgoing_net->{$user_ids[4]}; + $self->assert_str_equals("8.33853676860981e-06", $trust_4->[2]); + + my $trust_8 = $outgoing_net->{$user_ids[8]}; + $self->assert_str_equals("0.000245666165323859", $trust_8->[2]); + + #print "_________________________ test outgoing net END!\n"; +} + sub _test_incoming_net{ my $self = shift; -- 2.11.4.GIT