function _advpoll_calculate_instantrunoff in Advanced Poll 6.3

Same name and namespace in other branches

1. 5 modes/ranking.inc \_advpoll_calculate_instantrunoff()
2. 6 modes/ranking.inc \_advpoll_calculate_instantrunoff()
3. 6.2 modes/ranking.inc \_advpoll_calculate_instantrunoff()

Calculate the results using instant-runoff voting.

Parameters

$node: The node object for the current poll.

Return value

Should return an object that include the following attributes. -results : 2d array listing the aggregate preference, including ties -rounds : 2d array listing the per-choice vote count for each round and a status message indicating who was eliminated -totalVoters : the total number of voters who participated

1 call to _advpoll_calculate_instantrunoff()

advpoll_calculate_results_ranking in modes/ranking.inc

Calculate the results for a ranking poll based on the algorithm.

File

modes/ranking.inc, line 493

Handle ranking votes, e.g. choice A is preferred over choice B, which in turn is preferred over choice C.

Code

function _advpoll_calculate_instantrunoff($node) {
  $votes = array();

  // ORDER BY value ASC lets us ensure no gaps.
  $result = db_query("SELECT * FROM {votingapi_vote} v WHERE content_type = '%s' AND content_id = %d ORDER BY value ASC", 'advpoll', $node->nid);
  while ($vobj = db_fetch_object($result)) {
    $votes[] = $vobj;
  }
  if (count($votes) == 0) {

    // No votes yet.
    return array();
  }

  // Aggregate votes by user (uid if logged in, IP if anonymous)
  // in ascending order of value.
  $user_votes = array();
  foreach ($votes as $vote) {
    if ($vote->uid == 0) {

      // Anonymous user.
      $key = $vote->vote_source;
    }
    else {

      // Logged-in user.
      $key = $vote->uid;
    }

    // Note: relies on ORDER BY value ASC in vote-getting SQL query.
    // Otherwise a later vote might have a lower value.
    $user_votes[$key][] = $vote->tag;
  }
  $total_votes = count($user_votes);

  // Log of 1st-place votes per choice in each round.
  $round_log = array();

  // Gradually append candidates as they are eliminated; end with the winner.
  $reverse_ranking = array();

  // If we eliminate one choice per round and have n choices, we should
  // not be able to do more than n - 1 rounds.
  $max_rounds = count($node->choice);
  for ($round = 0; $round < $max_rounds; $round++) {

    // Initialize cur_round.
    $cur_round = array();
    $total_choices = count($node->choice);
    foreach ($node->choice as $key => $data) {
      $cur_round[$key] = array();
    }

    // Loop through each user.
    foreach ($user_votes as $key => $user_vote) {

      // $user_vote[0] contains the user's first remaining preference.
      $cur_round[$user_vote[0]][] = $key;
    }
    if ($round == 0) {

      // This is the first round.
      // Any choices with no first-place votes are considered eliminated.
      foreach ($cur_round as $key => $choice_votes) {
        if (count($choice_votes) == 0) {
          unset($cur_round[$key]);
          $reverse_ranking[0]['choices'][] = $key;
        }
      }
    }

    // Add the current round to the matrix.
    $round_log[] = $cur_round;

    // Calculate the min and max number of votes.
    $min_votes = -1;
    $max_votes = 0;

    // Number of choices that have already been discarded.
    $num_discarded = 0;

    // Examine the number of votes each choice received this round.
    foreach ($cur_round as $ch => $choice_votes) {
      $num_votes = count($choice_votes);
      if ($num_votes > $max_votes) {
        $max_votes = $num_votes;

        // Store current winner in case it has a majority.
        $cur_winner = $ch;
      }

      // This choice has already been eliminated (theoretically)
      // so don't count it as the minimum.
      if ($num_votes == 0) {
        $num_discarded++;

        // XXX: Probably don't need this variable any more
      }
      else {
        if ($num_votes != 0 && ($num_votes < $min_votes || $min_votes == -1)) {
          $min_votes = $num_votes;
        }
      }
    }

    // If one choice has a majority of remaining users it wins.
    // Note: we use count($user_votes) because some users may have incomplete
    // ballots and may have already had all of their choices eliminated.
    if ($max_votes > count($user_votes) / 2) {

      // Prune out the winning choice if it's still in there.
      if (isset($cur_round[$cur_winner])) {
        unset($cur_round[$cur_winner]);
      }

      // Keep computing until we figure out all final rankings.
      while (count($cur_round) > 0) {

        // Loop through non-winning choices.
        $current_place = array();
        $min = -1;
        foreach ($cur_round as $ch => $choice_votes) {

          // Choice has already been eliminated, just unset it.
          if (count($choice_votes) == 0) {
            unset($cur_round[$ch]);
          }
          else {
            if ($min == -1 || count($choice_votes) < $min) {

              // New minimum.
              $current_place = array(
                $ch,
              );
              $min = count($choice_votes);
            }
            else {
              if (count($choice_votes) == $min) {

                // Tied for minimum.
                $current_place[] = $ch;
              }
            }
          }
        }

        // current_place will be empty the first iteration if some
        // choices had no first-place votes and were eliminated
        // at the beginning.
        if (count($current_place) > 0) {
          $reverse_ranking[]['choices'] = $current_place;

          // Remove all choices that had the minimum.
          foreach ($current_place as $ch_key) {
            unset($cur_round[$ch_key]);
          }
        }
      }

      // Save a reversed version of the round log to help compute winnerPercent.
      $revmat = array_reverse($round_log);

      // The winner finally gets added
      $reverse_ranking[]['choices'] = array(
        $cur_winner,
      );
      $index = count($reverse_ranking) - 1;
      $reverse_ranking[$index]['raw_score'] = round(count($revmat[0][$cur_winner]) * 100 / count($user_votes), 1);
      $reverse_ranking[$index]['view_score'] = $reverse_ranking[$index]['raw_score'] . '%';
      $result_obj->matrix = $round_log;
      $result_obj->total_votes = $total_votes;
      $result_obj->ranking = array_reverse($reverse_ranking);
      return $result_obj;
    }

    // Since we're still here, no one has won, so eliminate one of the
    // choices with the lowest number of votes.
    // Find all choices with the minimum number of votes
    $min_choices = array();
    foreach ($cur_round as $ch => $choice_votes) {
      if (count($choice_votes) == $min_votes) {
        $min_choices[] = $ch;
      }
    }

    // Randomly select the choice to eliminate out of the available choices.
    // TODO: due to the randomness, this result must be cached after each vote.
    $round_loser = array_rand($min_choices);
    $reverse_ranking[]['choices'] = array(
      $min_choices[$round_loser],
    );

    // Loop through the users who voted for the loser and redistribute.
    foreach ($cur_round[$min_choices[$round_loser]] as $user_key) {

      // Remove their current first preference.
      array_shift($user_votes[$user_key]);

      // Keep eliminating first preference until we run out or find an choice
      // that hasn't been eliminated.
      while ($cur_round[$user_votes[$user_key][0]] == array() && count($user_votes[$user_key]) > 0) {
        array_shift($user_votes[$user_key]);
      }

      // If they have no more preferences, remove from list for simplicity.
      if (count($user_votes[$user_key]) == 0) {
        unset($user_votes[$user_key]);
      }
    }
  }

  // Loop detected. Signal user and record.
  drupal_set_message(t('Could not find a solution within @rounds iterations.', array(
    '@rounds' => $max_rounds,
  )));
  $result_obj->matrix = $round_log;
  $result_obj->total_votes = $total_votes;
  return $result_obj;
}