now I have also the outgoing net, which was simpler but not very simple

[breadcrumbs.git] / src / lib / Bcd / Data / Trust.pm

package Bcd::Data::Trust;

# This file is part of the breadcrumbs daemon (bcd).
# Copyright (C) 2007 Pasqualino Ferrentino

# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
# 02110-1301, USA.

# Contact: lino.ferrentino@yahoo.it (in Italian, English or German).

use strict;
use warnings;

use Bcd::Data::Users;

use constant{
    GET_TRUSTS_FROM_USER => "Trust_get_trusts_from_user",
    GET_ALFA_BIAS_FROM_USER => "Trust_get_alfa_bias_from_user",
    GET_ALL_USERS_IN_THIS_ANT_NEST => "Trust_get_all_users_in_this_ant_nest",

    INSERT_NEW_TRUST               => 
        qq{insert into trusts values (? , ? , ? , ? )},

    INSERT_NEW_TRUST_BOOKING       => "Trust_insert_new_trust_booking",
    SELECT_TRUST_BOOKING           => "Trust_select_trust_booking",
    DELETE_TRUST_BOOKING           => "Trust_delete_trust_booking",

    UPDATE_FIRST_TRUST             => "Trust_update_first_trust",
    UPDATE_SECOND_TRUST            => "Trust_update_second_trust",

    SELECT_TRUST_DIRECT            => "Trust_select_trust_direct",
    SELECT_TRUST_BACKUP            => "Trust_select_trust_backup",
    UPDATE_TRUST_BACKUP            => "Trust_update_trust_backup",
    INSERT_TRUST_BACKUP            => "Trust_insert_trust_backup",
    SELECT_ALL_BACKUPPED_TRUSTS    => "Trust_select_all_backupped_trusts",
    DELETE_TRUST_BACKUPS           => "Trust_delete_trust_backups",
};

=head1

    This method should return the backupped trusts

=cut

sub get_user_backupped_trusts {
    my ($self, $stash, $user) = @_;

    my $st = $stash->get_statement(SELECT_ALL_BACKUPPED_TRUSTS, $self);
    $st->bind_param(1, $user);
    $st->execute();

    my $row;
    my %backupped_trusts;
    while (defined($row = $st->fetch())){

        my $old_trust   = $row->[2];
        my $other_user  = $row->[1];

        $backupped_trusts{$other_user} = $old_trust;
    }

    return \%backupped_trusts;
}

=head1
    
    This method should simply commit the trust changes

=cut
sub commit_trust_changes{
    my ($self, $stash, $user) = @_;

    #I simply delete the backups...
    my $st = $stash->get_statement(DELETE_TRUST_BACKUPS, $self);
    $st->bind_param(1, $user);
    $st->execute();
}

=head1

    This method should rollback the trust changes made by a certain user.

=cut
sub rollback_trust_changes{
    my ($self, $stash, $user) = @_;

    #I should select the user which should have the trust rollbacked.
    #first of all I should take all the backupped trust of this user.

    my $st = $stash->get_statement(SELECT_ALL_BACKUPPED_TRUSTS, $self);
    $st->bind_param(1, $user);
    $st->execute();

    my $row;
    while (defined($row = $st->fetch())){

        my $am_i_second = $row->[3];
        my $old_trust   = $row->[2];
        my $other_user  = $row->[1];

        my $st;

        if ($am_i_second){
            $st = $stash->get_statement(UPDATE_SECOND_TRUST, $self);
            $st->bind_param(1, $old_trust);
            $st->bind_param(2, $other_user);
            $st->bind_param(3, $user);
        } else {
            $st = $stash->get_statement(UPDATE_FIRST_TRUST, $self);
            $st->bind_param(1, $old_trust);
            $st->bind_param(2, $user);
            $st->bind_param(3, $other_user);
        }

        $st->execute();
        
    }

    $st = $stash->get_statement(DELETE_TRUST_BACKUPS, $self);
    $st->bind_param(1, $user);
    $st->execute();
}

=head1

    This method should change a trust, making a backup, just in case
    If a backup exists already it is overwritten

=cut

sub change_trust{
    my ($self, $stash, $user_1, $user_2, $new_trust) = @_;

    #first of all I get the old trust.
    my ($old_trust, $am_i_second) = $self->_get_trust_between($stash, $user_1, $user_2);

    #ok, now I should create a backup, or update it if exists already
    $self->_create_or_update_trust_backup($stash, $user_1, $user_2, $old_trust, $am_i_second);
    
    #ok, now I can update the trust.

    my $st;
    
    if ($am_i_second){
        $st = $stash->get_statement(UPDATE_SECOND_TRUST, $self);
        $st->bind_param(1, $new_trust);
        $st->bind_param(2, $user_2);
        $st->bind_param(3, $user_1);
    } else {
        #I am first, so I can update with the right indices.
        $st = $stash->get_statement(UPDATE_FIRST_TRUST, $self);
        $st->bind_param(1, $new_trust);
        $st->bind_param(2, $user_1);
        $st->bind_param(3, $user_2);
    }

    $st->execute();

    #ok, all done.
}

sub _create_or_update_trust_backup{
    my ($self, $stash, $user_1, $user_2, $old_trust, $is_user_second) = @_;

    #is there a backup?

    my $st = $stash->get_statement(SELECT_TRUST_BACKUP, $self);
    
    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);

    $st->execute();
    my $row = $st->fetchrow_arrayref();

    $st->finish();

    if (! defined ($row)){
        #no backup, insert
        $st = $stash->get_statement(INSERT_TRUST_BACKUP, $self);

        $st->bind_param(1, $user_1);
        $st->bind_param(2, $user_2);
        $st->bind_param(3, $old_trust);
        $st->bind_param(4, $is_user_second);

        $st->execute();

    } else {

        #The backup exists already, do nothing.

        #backup, update
#       $st = $stash->get_statement(UPDATE_TRUST_BACKUP, $self);

#       $st->bind_param(1, $old_trust);
#       $st->bind_param(2, $user_1);
#       $st->bind_param(3, $user_2);

#       $st->execute();
    }
}

sub _get_trust_between{
    my ($self, $stash, $user_1, $user_2) = @_;

    my $am_i_second = 0;
    my $trust;

    my $st = $stash->get_statement(SELECT_TRUST_DIRECT, $self);
    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);

    $st->execute();
    my $row = $st->fetchrow_arrayref();

    if ( ! defined($row)){
        $am_i_second = 1;

        $st->finish();
        $st->bind_param(1, $user_2);
        $st->bind_param(2, $user_1);

        $st->execute();
        $row = $st->fetchrow_arrayref();

        $trust = $row->[3];
    } else {

        $trust = $row->[2];
    }

    $st->finish();
    return ($trust, $am_i_second);
}


=head1

    This method should simply see if there is already a booking

=cut
sub exists_booking_between{
    my ($self, $stash, $user_1, $user_2) = @_;

    my $st = $stash->get_statement(SELECT_TRUST_BOOKING, $self);
    
    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);
    $st->execute();

    my $row = $st->fetchrow_arrayref();
    
    $st->finish();

    if ( defined($row)){
        return 1;
    } else {
        return 0;
    }

}

=head1 create_new_trust
    This method should create a new trust between two users. The
    booking must already be existing
=cut

sub create_new_trust{
    #please note the inversion...
    my ($self, $stash, $user_2, $user_1, $trust) = @_;

    my $st = $stash->get_statement(SELECT_TRUST_BOOKING, $self);
    
    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);
    $st->execute();

    my $row = $st->fetchrow_arrayref();

    my $trust_u1_u2 = $row->[2];
    $st->finish();

    #ok, now I can insert a new trust
    $self->create_trust_between
        ($stash, $user_1, $user_2, $trust_u1_u2, $trust);

    #and I can delete the booking...

    $st = $stash->get_statement(DELETE_TRUST_BOOKING, $self);
    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);
    $st->execute();
}

=head1 create_new_trust_booking
    This method simply creates a new trust 
=cut

sub create_new_trust_booking{
    my ($self, $stash, $user_1, $user_2, $trust) = @_;

    my $st = $stash->get_statement(INSERT_NEW_TRUST_BOOKING, $self);

    $st->bind_param(1, $user_1);
    $st->bind_param(2, $user_2);
    $st->bind_param(3, $trust);

    $st->execute();
}

sub is_valid_trust{
    my ($self, $trust) = @_;

    #the trust is simply a number from (0,1];
    #zero is NOT a valid trust, because the log of zero is not existing...
    if (($trust <= 0) or ($trust > 1)){
        return 0;
    } else {
        return 1; #all ok.
    }
}

sub is_valid_trust_bb{

    my ($self, $trust) = @_;

    #the trust in bb is simply a number < 100.

    if ($trust > 100){
        return 0;
    } else {
        return 1; #all ok.
    }
}

sub populate_the_stash{
    my ($self, $db_stash) = @_;

    my $sql = qq{select * from trusts where u1=? or u2=?};
    my $sth = $db_stash->get_connection()->prepare( $sql );
    $db_stash->insert_statement(GET_TRUSTS_FROM_USER, $sth);

    #MAYBE THESE TWO COMMANDS SHOULD BE MOVED TO THE USERS MODULE
    $sql = qq{select alfa, bias from users where id=?};
    $sth = $db_stash->get_connection()->prepare( $sql );
    $db_stash->insert_statement(GET_ALFA_BIAS_FROM_USER, $sth);

    $sql = qq{select id, users_state from users where id_ant_nest=?};
    $sth = $db_stash->get_connection()->prepare( $sql );
    $db_stash->insert_statement(GET_ALL_USERS_IN_THIS_ANT_NEST, $sth);

    #$sql = 
    #$db_stash->record_this_statement(INSERT_NEW_TRUST, $sql);

    $sql = qq{insert into trusts_bookings values (? , ? , ? )};
    $db_stash->record_this_statement(INSERT_NEW_TRUST_BOOKING, $sql);

    #here you have an "and" and not an "or" because you know which user is first!
    $sql = qq{select * from trusts_bookings where u1=? and u2=?};
    $db_stash->record_this_statement(SELECT_TRUST_BOOKING, $sql);

    $sql = qq{DELETE from trusts_bookings where u1=? and u2=?};
    $db_stash->record_this_statement(DELETE_TRUST_BOOKING, $sql);

    $sql = qq{UPDATE trusts set trust_u1_u2=? where u1=? and u2=?};
    $db_stash->record_this_statement(UPDATE_FIRST_TRUST, $sql);

    $sql = qq{UPDATE trusts set trust_u2_u1=? where u1=? and u2=?};
    $db_stash->record_this_statement(UPDATE_SECOND_TRUST, $sql);

    $sql = qq{SELECT * from trusts where u1=? AND u2=?};
    $db_stash->record_this_statement(SELECT_TRUST_DIRECT, $sql);

    $sql = qq{SELECT * from trusts_backups where u1=? and u2=?};
    $db_stash->record_this_statement(SELECT_TRUST_BACKUP, $sql);

    $sql = qq{SELECT * from trusts_backups where u1=?};
    $db_stash->record_this_statement(SELECT_ALL_BACKUPPED_TRUSTS, $sql);

    $sql = qq{INSERT INTO trusts_backups VALUES(?, ?, ? , ?)};
    $db_stash->record_this_statement(INSERT_TRUST_BACKUP, $sql);

    $sql = qq{UPDATE trusts_backups set old_trust_u1_u2=? where u1=? AND u2=?};
    $db_stash->record_this_statement(UPDATE_TRUST_BACKUP, $sql);

    $sql = qq{DELETE FROM trusts_backups where u1=?};
    $db_stash->record_this_statement(DELETE_TRUST_BACKUPS, $sql);
    
}

sub create_trust_between{
    my ($self, $stash, $first, $second, $first_trust, $second_trust) = @_;
    my $st = $stash->prepare_cached(INSERT_NEW_TRUST);

    $st->bind_param(1, $first);
    $st->bind_param(2, $second);
    $st->bind_param(3, $first_trust);
    $st->bind_param(4, $second_trust);
    $st->execute();
}

#this file is the main file for the calculation of the trust.

#this returns the decimal trust
sub get_trust_decimal{

    my ($self, $u_start, $u_end, $stash) = @_;

    #ok, first of all I calculate the path from $u_start to $u_end
    my $res;
    my $res_path;

    ($res, $res_path) = $self->get_path($u_start, $u_end, $stash);

    if ($res == 0){
        return 0; #no path, no trust
    }

    #ok, now I calculate the trust
    my $index = 0;
    my $trust = 1; #this is the initial trust.

    my ($alfa_cur,  $bias_cur);
    my ($alfa_next, $bias_next);

    ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($u_start, $stash);

    #I start from the <second> step (the first is simply the starting user)
    foreach(@{$res_path}[1..$#{$res_path}]){

        #take alfa and bias from user,
        ($alfa_next, $bias_next) = $self->_get_alfa_bias_for_user($_->[0], $stash);
                
        my $coefficient = exp(-$index/$bias_next * log(10));
        my $modified_trust = $alfa_cur * $_->[1];

        $modified_trust = 1 if ($modified_trust > 1);

        $trust *= $coefficient * $modified_trust;

        $alfa_cur = $alfa_next;

        #go on
        $index ++;
    }

    return $trust;
}

#This function calculates the trust from a user to another... in bBel
sub get_trust{
   my ($self, $u_start, $u_end, $stash) = @_;
   my $trust = $self->get_trust_decimal($u_start, $u_end, $stash);
   return bBel($trust);
}

#this function returns the trust in bBel.
sub bBel{
    my $trust = shift;

    #this is the base
    my $coefficient = $trust / 1e-10;

    my $bels = log ($coefficient) / log(10);

    return sprintf("%.2f", $bels * 10);
}

#this is the inverse, from bBel to decimal
sub dec_from_bBel{
    my $trust_bB = shift;

    my $coefficient = $trust_bB / 10;
    my $trust = exp ( $coefficient * log (10));
    $trust *= 1e-10;

    return $trust;
}

sub _get_alfa_bias_for_user{
    my ($self, $user, $stash) = @_;

    my $st = $stash->get_statement(GET_ALFA_BIAS_FROM_USER, $self);
    $st->bind_param(1, $user); #this is the id of the user
    $st->execute();

    my $alfa;
    my $bias;
    
    $st->bind_columns(undef, \$alfa, \$bias);
    $st->fetch();
    $st->finish();

    return ($alfa, $bias);
}

sub _get_maximum_reachable_set{
    my ($self, $user, $stash) = @_;

    #I simply return the set of all the ants which belongs to the same
    #ant nest of this user

    my %maximum_set;

    my $ant_nest_code = Bcd::Data::Users->get_ant_nest_for_this_user($user, $stash);

    #ok, now I should put the ant nests inside...
    my $st = $stash->get_statement(GET_ALL_USERS_IN_THIS_ANT_NEST, $self);
    $st->bind_param(1, $ant_nest_code);
    $st->execute();

    my $id_ant;
    my $state;
    $st->bind_columns(undef, \$id_ant, \$state);

    while(defined($st->fetch())){
        next if $state != Bcd::Constants::Users::NORMAL_ACTIVE_ANT;
        $maximum_set{$id_ant} = 1;
    }
    
    $st->finish();

    return \%maximum_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{
    my ($self, $stash, $u_start) = @_;

    #the set to reach is all the ant nest
    my $set_to_reach = $self->_get_maximum_reachable_set($u_start, $stash);

    #ok, then I start with myself
    #my ($alfa, $bias) = $self->_get_alfa_bias_for_user($u_start, $stash);

    #I can reach myself with no path, and the f is one
    my $current_incoming_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.
    my $current_level_set = {$u_start => 1,};

    #and then I will recurse....
    $self->_helper_recursive_for_incoming_trust
        ($stash, $current_level_set, $set_to_reach, $current_incoming_net, $cache_alfa_bias);

    return $current_incoming_net;

    
}

sub _helper_recursive_for_incoming_trust{
    my ($self, $stash, $current_level_set, $set_to_reach, $current_incoming_net, $cache_alfa_bias) = @_;

    #ok, let's do some work
    #print "_helper_recursive_for_incoming_trust: OK, ........ LET'S see this is the list: \n";
    #print Dumper($current_level_set);

    #end of recursion?
    if (scalar(keys(%{$set_to_reach})) == 0){
        #print "END OF RECURSION...\n";
        return;
    }

    #I should for all the users in the list calculate the MAXIMUM trust towards them, using the
    #current incoming net as a cache

    #I start with an empty map towards the next level
    #my $next_level_map = {};

    my %next_level_set;

    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_within_sets
            ($stash, $_, $current_incoming_net, $set_to_reach);

        foreach (@{$list_of_reachables}){
            #print "I can be reached by $_->[0], with trust $_->[1]\n";
            $self->_add_this_ant_to_the_incoming_net
                ($stash, $_->[0], $current_level_set, $current_incoming_net, $cache_alfa_bias);

            #this will participate in the next recursion step...
            $next_level_set{$_->[0]} = 1;
            #BUT it does not belong to the set_to_reach anymore
            delete $set_to_reach->{$_->[0]};
            
        }
    }

    #recurse inside the next level list...
    #sleep(1);
    $self->_helper_recursive_for_incoming_trust
        ($stash, \%next_level_set, $set_to_reach, $current_incoming_net, $cache_alfa_bias);
}

#taken courtesly from: http://www.stonehenge.com/merlyn/UnixReview/col30.html
sub deep_copy {
    my $this = shift;
    if (not ref $this) {
        $this;
    } elsif (ref $this eq "ARRAY") {
        [map deep_copy($_), @$this];
    } elsif (ref $this eq "HASH") {
        +{map { $_ => deep_copy($this->{$_}) } keys %$this};
    } 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) = @_;
    
    #ok, I should get all the trusts for this users contained in the current level list
    #then I should get the maximum. This will be the new incoming...
    my $destinations = $self->_get_all_destinations_from_user($user, $current_level_set, $stash);

    #ok, I have the destinations... now I could compute the trust for all this destinations
    #and then I take the maximum

    my ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($user, $stash);
    #I add this to the cache
    $cache_alfa_bias->{$user} = [$alfa_cur, $bias_cur];

    #I take the maximum trust
    my $maximum_trust = 0;
    #and the path which has given me the maximum
    my $maximum_path;

    #print "_add_this_ant_to_the_incoming_net: ok, I am $user\n";

    foreach(@{$destinations}){
        
        #print "I can reach $_->[0] with trust $_->[1]\n";

        #I have a tentative path
        my $path_to_destination = $current_incoming_net->{$_->[0]};

        #print "this is the old path......\n";
        #print Dumper($path_to_destination);

        #I should copy this path, a deep copy...
        my $tentative_path = deep_copy($path_to_destination);


        
        #ok, then I add myself to the destination, with my trust
        unshift (@{$tentative_path->[0]}, $user);
        unshift (@{$tentative_path->[1]}, $_->[1]);

        #print "this is the new tentative path......\n";
        #print Dumper($tentative_path);

        #I should compute now the trust on this tentative 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 ($trust > $maximum_trust){
            #print "AND IT WINS\n";
            $maximum_trust = $trust;
            $maximum_path = $tentative_path;
            $tentative_path->[2] = $trust;
        }

    }

    #ok, I can add this path to the incoming net
    $current_incoming_net->{$user} = $maximum_path;
}

sub compute_trust_on_this_path{
    my ($self, $tentative_path, $cache_alfa_bias) = @_;

    #print "{{{{{{{{{{{{{{{{{{{{{{{{{ compute_trust_on_this_path\n";
    #sleep(1);
    #print Dumper($tentative_path);
    #print Dumper($cache_alfa_bias);

    my $index = 0;
    my $trust = 1; #this is the initial trust.

    my $limit = scalar(@{$tentative_path->[0]})-2;
    #print "I will make a loop from 0 to $limit\n";
    for(0..$limit){

        my ($alfa_mine, $bias_next);

        #I take my alfa and the next bias
        my $u1 = $tentative_path->[0]->[$index];
        my $u2 = $tentative_path->[0]->[$index+1];
        #print "u1 = $u1 u2 = $u2  the index is $index and the loop var is $_\n";
        $alfa_mine = $cache_alfa_bias->{$tentative_path->[0]->[$index]}->[0];
        $bias_next = $cache_alfa_bias->{$tentative_path->[0]->[$index+1]}->[1];

        #print "I have alfa $alfa_mine and bias $bias_next\n";
        
        my $coefficient = exp(-$index/$bias_next * log(10));
        my $modified_trust = $alfa_mine * $tentative_path->[1]->[$_];

        $modified_trust = 1 if ($modified_trust > 1);

        $trust *= $coefficient * $modified_trust;

        #go on
        $index ++;
    }

    return $trust;
}

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);
    $st->execute();

    #ok, now I get all the paths... from user
    my $u1;
    my $u2; 
    my $t_u1_u2;
    my $t_u2_u1;
    $st->bind_columns(undef, \$u1, \$u2, \$t_u1_u2, \$t_u2_u1);

    my @paths = ();

    while ( defined($st->fetch()) ) {

        my @path;

        if ($u1 == $user){
            #ok, I am on the left, I am u1
            next if exists($reached_set->{$u2});
            next if !exists($set_to_reach->{$u2});

            push (@path, $u2);
            if ($ingoing == 1){
                push (@path, $t_u2_u1);
            } else {
                push (@path, $t_u1_u2);
            }
        } else {
            #I am on the right side, I am u2
            next if exists($reached_set->{$u1});
            next if !exists($set_to_reach->{$u1});

            push (@path, $u1);

            if ($ingoing == 1){
                push (@path, $t_u1_u2);
            } else {
                push (@path, $t_u2_u1);
            }
        }

        push(@paths, \@path);
    }
    $st->finish();

    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.
sub get_reachable_users_from_user_trust_limited{
    my ($self, $u_start, $t_lim, $stash) = @_;

    #ok, I must search all the paths
    #the initial trust is one, the initial level is zero
    my %set_of_reachables;
    my $maximum_reachable_set; #this is the set of all the ants in this ant nest

    #first of all I get the ant nest of this user
    $maximum_reachable_set = $self->_get_maximum_reachable_set($u_start, $stash);

    my ($alfa, $bias) = $self->_get_alfa_bias_for_user($u_start, $stash);
    
    $self->helper_recursive_for_get_reachable_users
        ($u_start, $alfa, undef, 0, 1, $t_lim, \%set_of_reachables, $stash, $maximum_reachable_set);

    #I KNOW that I can reach myself, this is a bogus data...
    delete $set_of_reachables{$u_start};

    return \%set_of_reachables;
}

#this function returns the list of all the users with no limit in the
#ant nests which are reachable from the selected user
sub get_reachable_users_from_user_trust_no_limit{
    #I have the starting point and the trust limit
    my ($self, $u_start, $t_lim, $stash) = @_;

    #ok, I must search all the paths
    #the initial trust is one, the initial level is zero
    my %set_of_reachables;

    my ($alfa, $bias) = $self->_get_alfa_bias_for_user($u_start, $stash);

    $self->helper_recursive_for_get_reachable_users
        ($u_start, $alfa, undef, 0, 1, $t_lim, \%set_of_reachables, $stash, undef);

    #I KNOW that I can reach myself, this is a bogus data...
    delete $set_of_reachables{$u_start};

    return \%set_of_reachables;
}

#this is the recursive core for the 
#get_reachable_users_from_user_trust_no_limit function

#this version does not detect cycles (but they cause no harm...)
sub helper_recursive_for_get_reachable_users{
    my ($self, $user, $alfa_prev, $user_from, 
        $level, $t_cur, $t_lim, $reachables, $stash, $max_reach_set) = @_;

    if (defined ($user_from)){
        #print "RECURSE FROM $user_from  user $user alfa $alfa_prev lev $level t_cur $t_cur \n";
    } else {
        #print "RECURSE FIRST.... user $user alfa $alfa_prev lev $level t_cur $t_cur \n";
    }

    #well myself is obviously reached, if I have found a maximum store it!
    if ( exists $reachables->{$user}){
        if ($reachables->{$user} < $t_cur){
            $reachables->{$user} = $t_cur;
        }
    } else {
        $reachables->{$user} = $t_cur;
    }


    #Ok, now I should get all the destinations for this user.
    my $destinations = $self->_get_all_destinations_from_user($user, $max_reach_set, $stash);

    #ok, now I make a cycle on all the nodes...
    foreach(@{$destinations}){

        #print "My destinations are:\n";
        #print Dumper($destinations);

        if (defined($user_from) && $_->[0] == $user_from){
            #print "                     I don't return!\n";
            next;
        }

        #I should get alfa and bias for this initial user
        my ($alfa_cur, $bias_cur) = $self->_get_alfa_bias_for_user($_->[0], $stash);
        
        #I should calculate the coefficient
        my $test_trust = $t_cur;

        #print "I am using alfa $alfa_prev bias $bias_cur\n";

        my $coefficient = exp(-$level/$bias_cur * log(10));
        my $modified_trust = $alfa_prev * $_->[1];
        $modified_trust = 1 if ($modified_trust > 1);

        $test_trust *= $coefficient * $modified_trust;

        if ( $test_trust > $t_lim ){
            #ok! I can recurse inside...
            #print "I can reach $_->[0] with trust $test_trust... ok\n";
            $self->helper_recursive_for_get_reachable_users
                ($_->[0], $alfa_cur, $user, $level+1, $test_trust, $t_lim, $reachables, $stash);
        } else {
            #print "I COULD reach $_->[0] with trust $test_trust... NO SUFFICIENT t lim is $t_lim\n";
        }
    }

}

sub get_path{
    my ($self, $u_start, $u_end, $stash) = @_;

    #I initialize the set of the visited nodes


    my $recursion_limit = 0;
    my $res;
    my $res_path;
    do{
        my %visited_nodes;
        my @first_step = ($u_start, 1);
        my @path = \@first_step; #I start from the user u_start...

        ($res, $res_path) =  $self->_get_path_recursive($u_start, $u_end, $stash, \%visited_nodes, \@path, 0, 
                                                        $recursion_limit);
        $recursion_limit ++;
    } until($res==1 || $res == 0);
    
    return ($res, $res_path);
}

sub exists_direct_trust_between{
   my ($self, $stash, $u_start, $u_end) = @_;
   #I simply must get a path with recursion limit = 1;

   my %visited_nodes;
   my @first_step = ($u_start, 1);
   my @path = \@first_step; #I start from the user u_start...

   my ($res, $res_path) =  
       $self->_get_path_recursive($u_start, $u_end, $stash, \%visited_nodes, \@path, 0, 1);

   #if I reached the end of recursion there is no direct path...
   return $res == 2 ? 0 : 1;
}

sub _get_all_destinations_from_user{
    my ($self, $user, $max_reach_set, $stash) = @_;

    my $st = $stash->get_statement(GET_TRUSTS_FROM_USER, $self);
    $st->bind_param(1,$user);
    $st->bind_param(2,$user);
    $st->execute();

    #ok, now I get all the paths... from user
    my $u1;
    my $u2; 
    my $t_u1_u2;
    my $t_u2_u1;
    $st->bind_columns(undef, \$u1, \$u2, \$t_u1_u2, \$t_u2_u1);

    my @destinations = ();

    while ( defined($st->fetch()) ) {

        my @dest;

        if ($u1 == $user){
            if ( defined($max_reach_set) && !exists($max_reach_set->{$u2})){
                next; #this ant does not belong to our maximum set
            }
            push (@dest, $u2);
            push (@dest, $t_u1_u2);
        } else {
            if ( defined($max_reach_set) && !exists($max_reach_set->{$u1})){
                next; #this ant does not belong to our maximum set
            }
            push (@dest, $u1);
            push (@dest, $t_u2_u1);
        }

        push(@destinations, \@dest);
    }
    $st->finish();

    return \@destinations;
}


use Data::Dumper;

#this function calculates the path from a user to another
#returns a list of ids... it is recursive, but maybe it is not
#very efficient.

#return 0 No_path 1 Ok 2 Reached recursion limit
sub _get_path_recursive{

    my ( $class, $u_start, $u_end, $stash, $visited_nodes, $path_so_far, $recursion_level, $recursion_limit) = @_;


#     print ">>>>>>>>>>>>> recursion u_start $u_start end $u_end level $recursion_level limit $recursion_limit\n";
#     print "nodes : ";
#     print Dumper($visited_nodes);
#     print "path so far : ";
#     print Dumper ($path_so_far);

    if ( $u_start == $u_end){
        return (1, $path_so_far); #ok, end of recursion.
    }

    if ($recursion_level >= $recursion_limit){
        #ok, I have reached the end of recursion
        #print "                                 END OF RECURSION... \n";
        return (2, $path_so_far);
    }

    $visited_nodes->{$u_start} = 1; #I visit this node...
    my $st = $stash->get_statement(GET_TRUSTS_FROM_USER, $class);
    $st->bind_param(1,$u_start);
    $st->bind_param(2,$u_start);
    $st->execute();

    #ok, now I get all the paths... from u_start...
    my $u1;
    my $u2; 
    my $t_u1_u2;
    my $t_u2_u1;
    $st->bind_columns(undef, \$u1, \$u2, \$t_u1_u2, \$t_u2_u1);

    my @destinations = ();
    my @trusts = ();

    while ( defined($st->fetch()) ) {

        if ($u1 == $u_start){
            if (exists ($visited_nodes->{$u2})){
                next;
            }
            push (@destinations, $u2);
            push (@trusts, $t_u1_u2);
        } else {
            if (exists ($visited_nodes->{$u1})){
                next;
            }
            push (@destinations, $u1);
            push (@trusts, $t_u2_u1);
        }
    }
    $st->finish();

    #print "Destinations from here:\n";
    #print Dumper(\@destinations);

    my $end_because_of_recursion_limit_flag = 0;

    my $index = 0;
    foreach(@destinations){
        #I try to reach every destination
        my $res;
        my $res_path;

        #test step
        my @test_step = ($_, $trusts[$index]);
        push(@{$path_so_far}, \@test_step);

        #let's try to reach the destination
        #print "pause press ENTER\n";
        #<STDIN>;
        ($res, $res_path) = $class->_get_path_recursive($_, $u_end, $stash, $visited_nodes, $path_so_far,
                                                        $recursion_level+1, $recursion_limit);


        if ($res == 1){
            #ok, end of recursion
            return ($res, $path_so_far);
        } elsif ($res == 2){
            $end_because_of_recursion_limit_flag = 1;
        }
            
        #no good...
        pop(@{$path_so_far});
        $index++;
    }


    #no success...
    delete $visited_nodes->{$u_start};
    if ($end_because_of_recursion_limit_flag == 0){
        #print "                          ***  KO DEAD END *** \n";
        return (0, $path_so_far);
    } else {
        #print "                          ***  KO BECAUSE OF RECURSION LIMIT *** \n";
        return (2, $path_so_far);
    }
}


1;