| 7 |
* from 1 to n |
* from 1 to n |
| 8 |
*/ |
*/ |
| 9 |
|
|
| 10 |
// $Id: ranking.module,v 1.19 2009/07/27 23:25:43 anarcat Exp $ |
// $Id: ranking.module,v 1.20 2009/07/30 22:16:32 anarcat Exp $ |
| 11 |
|
|
| 12 |
/** |
/** |
| 13 |
* Implementation of hook_help() |
* Implementation of hook_help() |
| 47 |
*/ |
*/ |
| 48 |
function ranking_decisions_algorithms() { |
function ranking_decisions_algorithms() { |
| 49 |
return array('instant runoff' => t('Instant run-off voting, also known as IVR or Alternative Voting, is an algorithm by which the candidate having the least ballots gets its votes redistributed to the other candidates. See <a href="http://en.wikipedia.org/wiki/Instant-runoff_voting">Instant runoff voting on Wikipedia</a> for more information.'), |
return array('instant runoff' => t('Instant run-off voting, also known as IVR or Alternative Voting, is an algorithm by which the candidate having the least ballots gets its votes redistributed to the other candidates. See <a href="http://en.wikipedia.org/wiki/Instant-runoff_voting">Instant runoff voting on Wikipedia</a> for more information.'), |
| 50 |
'borda count' => t('Borda count is an algorithm by which each candidate gets a number of points assigned based on the number of candidates standing. See the <a href="http://en.wikipedia.org/wiki/Borda_count">Borda count article on Wikipedia</a> for more information.')); |
'borda count' => t('Borda count is an algorithm by which each candidate gets a number of points assigned based on the number of candidates standing. See the <a href="http://en.wikipedia.org/wiki/Borda_count">Borda count article on Wikipedia</a> for more information.'), |
| 51 |
|
'condorcet' => t('Condorcet finds the one candidate who would beat all other candidates in all possible two-person races. In this implementation, ties are broken using Schulze method. See the <a href="http://en.wikipedia.org/wiki/Schulze_method">Schulze method article on Wikipedia</a> for more information.')); |
| 52 |
} |
} |
| 53 |
|
|
| 54 |
/** |
/** |
| 128 |
|
|
| 129 |
$output = ''; |
$output = ''; |
| 130 |
|
|
| 131 |
// If no one has voted, $results = array() and thus is empty |
if ($node->algorithm == 'condorcet') { // Use this display method only if using condorcet. |
| 132 |
if (!empty($results)) { |
$rows[0][] = ""; |
| 133 |
|
$options = count($node->choice); |
| 134 |
$output .= t('Results: ') .'<ol>'; |
for ($i = 1; $i<=$options; $i++) { |
| 135 |
|
$rows[0][] = array('data' => check_plain($node->choice[$i]['label']), 'header' => 1); |
| 136 |
|
} |
| 137 |
|
for ($i = 1; $i<=$options; $i++) { |
| 138 |
|
$rows[$i][0] = array('data' => check_plain($node->choice[$i]['label']), 'header' => 1); |
| 139 |
|
for ($j = 1; $j<=$options; $j++) { |
| 140 |
|
if ($i==$j) { |
| 141 |
|
$rows[$i][$j] = "N/A"; |
| 142 |
|
} else { |
| 143 |
|
if ($results->matrix[$i][$j]) { |
| 144 |
|
$rows[$i][$j] = $results->matrix[$i][$j]; |
| 145 |
|
} else { |
| 146 |
|
$rows[$i][$j] = 0; |
| 147 |
|
} |
| 148 |
|
} |
| 149 |
|
} |
| 150 |
|
} |
| 151 |
|
|
| 152 |
|
$output .= theme_table(array(), $rows, array(), "The number in a given square is the number of times the row was preferred to the column."); |
| 153 |
|
|
| 154 |
for ($i = 0; $i < count($results->ranking); $i++) { |
// Display the outcome of the Schulze count. |
| 155 |
$output .= '<li> '; |
$output .= '<p>Results</p><ul>'; |
| 156 |
|
for ($i=1; $i<=count($results->ranking); $i++) { |
| 157 |
|
$output .= "<li><em>Round ". $i ."</em>: ". $results->ranking[$i][0] .": "; |
| 158 |
$first_one = TRUE; |
$first_one = TRUE; |
| 159 |
|
for ($j=1; $j<count($results->ranking[$i]); $j++) { |
| 160 |
|
if (!$first_one) {$output .= ", ";} |
| 161 |
|
$output .= check_plain($node->choice[$results->ranking[$i][$j]]['label']); |
| 162 |
|
$first_one=FALSE; |
| 163 |
|
} |
| 164 |
|
$output .= "</li>"; |
| 165 |
|
} |
| 166 |
|
$output .= "</ul>"; |
| 167 |
|
} else { |
| 168 |
|
|
| 169 |
|
// If no one has voted, $results = array() and thus is empty |
| 170 |
|
if (!empty($results)) { |
| 171 |
|
|
| 172 |
|
$output .= t('Results: ') .'<ol>'; |
| 173 |
|
|
| 174 |
|
for ($i = 0; $i < count($results->ranking); $i++) { |
| 175 |
|
$output .= '<li> '; |
| 176 |
|
$first_one = TRUE; |
| 177 |
|
|
| 178 |
|
// Loop through all choices with this ranking |
| 179 |
|
foreach ($results->ranking[$i]['choices'] as $choice) { |
| 180 |
|
$output .= ($first_one? '' : ', ') . check_plain($node->choice[$choice]['label']); |
| 181 |
|
$first_one = FALSE; |
| 182 |
|
} |
| 183 |
|
|
| 184 |
// Loop through all choices with this ranking |
// Show the ranking's score if it exists (depends on algorithm) |
| 185 |
foreach ($results->ranking[$i]['choices'] as $choice) { |
if (isset($results->ranking[$i]['viewscore'])) { |
| 186 |
$output .= ($first_one? '' : ', ') . check_plain($node->choice[$choice]['label']); |
$output .= ' ('. $results->ranking[$i]['viewscore'] .')'; |
|
$first_one = FALSE; |
|
|
} |
|
|
|
|
|
// Show the ranking's score if it exists (depends on algorithm) |
|
|
if (isset($results->ranking[$i]['viewscore'])) { |
|
|
$output .= ' ('. $results->ranking[$i]['viewscore'] .')'; |
|
|
} |
|
|
$output .= '</li>'; |
|
|
} |
|
|
$output .= '</ol>'; |
|
|
|
|
|
if (user_access('inspect all votes') && isset($results->matrix)) { |
|
|
$header[0] = "Rounds"; |
|
|
$round = 1; |
|
|
if (count($results->matrix) > 0) { |
|
|
foreach ($results->matrix as $a_round) { |
|
|
$header[$round] = $round; |
|
|
$round++; |
|
| 187 |
} |
} |
| 188 |
|
$output .= '</li>'; |
| 189 |
} |
} |
| 190 |
|
$output .= '</ol>'; |
| 191 |
|
|
| 192 |
|
if (user_access('inspect all votes') && isset($results->matrix)) { |
| 193 |
|
$header[0] = "Rounds"; |
| 194 |
|
$round = 1; |
| 195 |
|
if (count($results->matrix) > 0) { |
| 196 |
|
foreach ($results->matrix as $a_round) { |
| 197 |
|
$header[$round] = $round; |
| 198 |
|
$round++; |
| 199 |
|
} |
| 200 |
|
} |
| 201 |
|
|
| 202 |
$round = 1; |
$round = 1; |
| 203 |
$i = 0; |
$i = 0; |
| 204 |
if (count($results->matrix) > 0) { |
if (count($results->matrix) > 0) { |
| 205 |
foreach ($results->matrix as $a_round) { |
foreach ($results->matrix as $a_round) { |
| 206 |
foreach ($node->choice as $key => $choicename) { |
foreach ($node->choice as $key => $choicename) { |
| 207 |
$rows[$i][0] = $choicename['label']; |
$rows[$i][0] = $choicename['label']; |
| 208 |
$rows[$i][$round] = count($a_round[$key]); |
$rows[$i][$round] = count($a_round[$key]); |
| 209 |
$i++; |
$i++; |
| 210 |
|
} |
| 211 |
|
$i=0; |
| 212 |
|
$round++; |
| 213 |
} |
} |
|
$i=0; |
|
|
$round++; |
|
| 214 |
} |
} |
| 215 |
|
$output .= theme('table', $header, $rows); |
| 216 |
} |
} |
|
$output .= theme('table', $header, $rows); |
|
| 217 |
} |
} |
| 218 |
} |
} // end condorcet else. |
| 219 |
return $output; |
return $output; |
| 220 |
} |
} |
| 221 |
|
|
| 312 |
} |
} |
| 313 |
|
|
| 314 |
// Check that multiple choices are not set to the same value |
// Check that multiple choices are not set to the same value |
| 315 |
foreach ($setvalues as $val => $count) { |
if ($node->algorithm != "condorcet") { // condorcet uses ties. |
| 316 |
if ($val != 0 && $count > 1) { |
foreach ($setvalues as $val => $count) { |
| 317 |
form_set_error('choice', t('Multiple choices given the rank of @val.', array('@val' => $val))); |
if ($val != 0 && $count > 1) { |
| 318 |
$ok = FALSE; |
form_set_error('choice', t('Multiple choices given the rank of @val.', array('@val' => $val))); |
| 319 |
|
$ok = FALSE; |
| 320 |
|
} |
| 321 |
} |
} |
| 322 |
} |
} // end condorcet if. |
| 323 |
|
|
| 324 |
|
|
| 325 |
return $ok; |
return $ok; |
| 346 |
if ($node->algorithm == 'borda count') { |
if ($node->algorithm == 'borda count') { |
| 347 |
return _decisions_calculate_bordacount($node); |
return _decisions_calculate_bordacount($node); |
| 348 |
} |
} |
| 349 |
else { |
else if ($node->algorithm == 'instant runoff') { |
| 350 |
return _decisions_calculate_instantrunoff($node); |
return _decisions_calculate_instantrunoff($node); |
| 351 |
} |
} |
| 352 |
|
else { |
| 353 |
|
return _decisions_calculate_condorcet($node); |
| 354 |
|
} |
| 355 |
} |
} |
| 356 |
|
|
| 357 |
/** |
/** |
| 662 |
return $result_obj; |
return $result_obj; |
| 663 |
|
|
| 664 |
} |
} |
| 665 |
|
|
| 666 |
|
/** |
| 667 |
|
* Calculate the results using condorcet voting. |
| 668 |
|
* |
| 669 |
|
* @param $node |
| 670 |
|
* The node object for the current decision |
| 671 |
|
* |
| 672 |
|
* @return |
| 673 |
|
* Should return an object that include the following attributes |
| 674 |
|
* -matrix: 2d array listing the aggregate preferences |
| 675 |
|
* -ranking : 2d array listing the results of the Schulze count. |
| 676 |
|
* -total_votes : the total number of voters who participated |
| 677 |
|
*/ |
| 678 |
|
function _decisions_calculate_condorcet ($node) { |
| 679 |
|
$votes = _decisions_votes($node); |
| 680 |
|
|
| 681 |
|
if (count($votes) == 0) { |
| 682 |
|
// no votes yet |
| 683 |
|
return array(); |
| 684 |
|
} |
| 685 |
|
|
| 686 |
|
// aggregate votes by user (uid if logged in, IP if anonymous) |
| 687 |
|
// in ascending order of value |
| 688 |
|
$user_votes = array(); |
| 689 |
|
|
| 690 |
|
foreach ($votes as $vote) { |
| 691 |
|
if ($vote['uid'] == 0) { |
| 692 |
|
// anonymous user |
| 693 |
|
$key = $vote['vote_source']; |
| 694 |
|
} |
| 695 |
|
else { |
| 696 |
|
// logged-in user |
| 697 |
|
$key = $vote['uid']; |
| 698 |
|
} |
| 699 |
|
|
| 700 |
|
$user_votes[$key][$vote['tag']] = $vote['value']; // TAG and Value had to be reversed here to allow for ties. |
| 701 |
|
} |
| 702 |
|
|
| 703 |
|
$choice_votes = array(); |
| 704 |
|
|
| 705 |
|
$total_choices = count($node->choice); |
| 706 |
|
$total_votes = count($user_votes); |
| 707 |
|
|
| 708 |
|
// Loop through each user's vote |
| 709 |
|
foreach ($user_votes as $uid => $user_vote) { |
| 710 |
|
// Create an array of choice ranks, so we don't look for any of them more than once. |
| 711 |
|
$choice_ranks = array(); |
| 712 |
|
// Go through all the node choices, and find their ranking. |
| 713 |
|
for ($choice = 1; $choice <= $total_choices; $choice++) { |
| 714 |
|
$ranking = 256; // default value applied to anything that isn't ranked. Tied for last. Problem if there were more than 256 options. |
| 715 |
|
if (array_key_exists($choice, $user_vote)) { $ranking = $user_vote[$choice]; } // Pull the ranking from the vote. |
| 716 |
|
$choice_ranks[$choice] = 0 - $ranking; // We inverse the numerical values so a high ranking is bad, negatives work fine. |
| 717 |
|
} |
| 718 |
|
// Loop through to compare every choice. |
| 719 |
|
for ($choice_A = 1; $choice_A <= $total_choices-1; $choice_A++) { |
| 720 |
|
// Loop through all choices to which choice_A has not been compared, excluding itself. |
| 721 |
|
for ($choice_B = $choice_A+1; $choice_B <= $total_choices; $choice_B++) { |
| 722 |
|
// Figure out where to put the points. |
| 723 |
|
if ($choice_ranks[$choice_A]>$choice_ranks[$choice_B]) { |
| 724 |
|
// Indicate A beat B |
| 725 |
|
$choice_votes[$choice_A][$choice_B] = $choice_votes[$choice_A][$choice_B] + 1; |
| 726 |
|
$choice_votes[$choice_B][$choice_A] = $choice_votes[$choice_B][$choice_A] + 0; |
| 727 |
|
} else if ($choice_ranks[$choice_B]>$choice_ranks[$choice_A]) { |
| 728 |
|
// Indicate B beat A |
| 729 |
|
$choice_votes[$choice_B][$choice_A] = $choice_votes[$choice_B][$choice_A] + 1; |
| 730 |
|
$choice_votes[$choice_A][$choice_B] = $choice_votes[$choice_A][$choice_B] + 0; |
| 731 |
|
} else { |
| 732 |
|
// Indicate a Tie |
| 733 |
|
$choice_votes[$choice_B][$choice_A] = $choice_votes[$choice_B][$choice_A] + 0.5; |
| 734 |
|
$choice_votes[$choice_A][$choice_B] = $choice_votes[$choice_A][$choice_B] + 0.5; |
| 735 |
|
} // end if |
| 736 |
|
} // end for |
| 737 |
|
} // end for |
| 738 |
|
} // end foreach |
| 739 |
|
|
| 740 |
|
//Return the results. |
| 741 |
|
$result_obj->matrix = $choice_votes; |
| 742 |
|
$result_obj->ranking = _decisions_shultz($choice_votes); |
| 743 |
|
$result_obj->total_votes = $total_votes; |
| 744 |
|
return $result_obj; |
| 745 |
|
} |
| 746 |
|
|
| 747 |
|
function _compare_beatpaths($a, $b) { |
| 748 |
|
return strcmp($b[2],$a[2]); |
| 749 |
|
} |
| 750 |
|
|
| 751 |
|
/** |
| 752 |
|
* Determine the shultz method winner from a pairwise matrix. |
| 753 |
|
* |
| 754 |
|
* @param $matrix; |
| 755 |
|
* A pair-wise matrix of results. |
| 756 |
|
* |
| 757 |
|
* @return |
| 758 |
|
* Should return an array appropriate for the condorcet display method. |
| 759 |
|
* |
| 760 |
|
* Note: There is another heuristic where strongest |
| 761 |
|
* beatpaths are locked in, and weaker beatpaths that conflict with them are ignored. |
| 762 |
|
* From my understanding, that would eliminate entirely the need for the second half of the |
| 763 |
|
* Floyd-Warshall algorithm. |
| 764 |
|
* I think that would be much faster to implement and run, but I would want to satisfy myself that |
| 765 |
|
* the results were the same either way, so I went for the hard way first. |
| 766 |
|
*/ |
| 767 |
|
function _decisions_shultz($matrix) { |
| 768 |
|
$ranking = array(); |
| 769 |
|
$candidates = count($matrix); |
| 770 |
|
// Create a matrix of path strengths. Based on the Floyd-Warshall algorithm. |
| 771 |
|
$strongest_paths = array(); |
| 772 |
|
for ($i = 1; $i<=$candidates; $i++) { |
| 773 |
|
for ($j = 1; $j<=$candidates; $j++) { |
| 774 |
|
if ($i!=$j) { |
| 775 |
|
if ($matrix[$i][$j]>$matrix[$j][$i]) { |
| 776 |
|
$strongest_paths[$i][$j] = $matrix[$i][$j]; |
| 777 |
|
} else { |
| 778 |
|
$strongest_paths[$i][$j] = 0; |
| 779 |
|
} |
| 780 |
|
} |
| 781 |
|
} |
| 782 |
|
} |
| 783 |
|
for ($i = 1; $i<=$candidates; $i++) { |
| 784 |
|
for ($j = 1; $j<=$candidates; $j++) { |
| 785 |
|
if ($i != $j) { |
| 786 |
|
for ($k = 1; $k<=$candidates; $k++) { |
| 787 |
|
if (($j!=$k) && ($i != $k)) { |
| 788 |
|
$strongest_paths[$j][$k] = max ($strongest_paths[$j][$k], min ($strongest_paths[$j][$i], $strongest_paths[$i][$k])); |
| 789 |
|
} |
| 790 |
|
} |
| 791 |
|
} |
| 792 |
|
} |
| 793 |
|
} |
| 794 |
|
// Create an array of for,against,strength values from the strongest_paths array to allow sorting. |
| 795 |
|
$beatpath = array(); |
| 796 |
|
for ($i = 1; $i<=$candidates; $i++) { |
| 797 |
|
for ($j = 1; $j<=$candidates; $j++) { |
| 798 |
|
if ($i!=$j && $strongest_paths[$i][$j] != 0) { |
| 799 |
|
$beatpath[] = array($i, $j, $strongest_paths[$i][$j]); |
| 800 |
|
} |
| 801 |
|
} |
| 802 |
|
} |
| 803 |
|
// sort the array so that we're starting with the strongest links. |
| 804 |
|
usort($beatpath,"_compare_beatpaths"); |
| 805 |
|
|
| 806 |
|
$round_count = 0; |
| 807 |
|
$original_candidates = $candidates; |
| 808 |
|
$orig_beatpath = count($beatpath); |
| 809 |
|
$pathed_out = array(); // 1 indicates that the candidate has been pathed out. 2 indicates their beatpaths have been removed. |
| 810 |
|
while ($candidates>1 && count($beatpath)>0) { |
| 811 |
|
// Find if there are any candidates that have been pathed out. |
| 812 |
|
// Pathed out means that A has a path to beat B, but B has no path to beat A, so B is eliminated. |
| 813 |
|
$round_count++; |
| 814 |
|
if ($round_count > $original_candidates) { // We have a problem. |
| 815 |
|
$broken = TRUE; |
| 816 |
|
break; |
| 817 |
|
} |
| 818 |
|
for ($i=1; $i<$original_candidates; $i++) { |
| 819 |
|
for ($j=$i+1; $j<=$original_candidates; $j++) { |
| 820 |
|
$forward = FALSE; |
| 821 |
|
$reverse = FALSE; |
| 822 |
|
for ($k=0; $k<count($beatpath); $k++){ |
| 823 |
|
if (($beatpath[$k][0] == $i) && ($beatpath[$k][1] == $j)) { |
| 824 |
|
$forward = TRUE; |
| 825 |
|
} |
| 826 |
|
if (($beatpath[$k][1] == $i) && ($beatpath[$k][0] == $j)) { |
| 827 |
|
$reverse = TRUE; |
| 828 |
|
} |
| 829 |
|
} |
| 830 |
|
if ($forward == TRUE && $reverse == FALSE) { |
| 831 |
|
$pathed_out[$j] = 1; |
| 832 |
|
} |
| 833 |
|
if ($forward == FALSE && $reverse == TRUE) { |
| 834 |
|
$pathed_out[$i] = 1; |
| 835 |
|
} |
| 836 |
|
} |
| 837 |
|
} |
| 838 |
|
$pathed_out_count = 0; |
| 839 |
|
for ($i=1; $i<=$original_candidates; $i++) { |
| 840 |
|
if ($pathed_out[$i] == 1) {$pathed_out_count++;} |
| 841 |
|
} |
| 842 |
|
if ($pathed_out_count>0) { // Some candidate was eliminated this round. |
| 843 |
|
// Remove all of the beatpaths associated with them. |
| 844 |
|
$ranking[$round_count][] = "Eliminated"; |
| 845 |
|
for ($i=1; $i<=$original_candidates; $i++) { |
| 846 |
|
if ($pathed_out[$i] == 1) { |
| 847 |
|
$ranking[$round_count][] = $i; |
| 848 |
|
$candidates--; |
| 849 |
|
for ($j=0; $j<$orig_beatpath; $j++) { |
| 850 |
|
if (($beatpath[$j][0]) == $i || ($beatpath[$j][1] == $i)) { |
| 851 |
|
unset($beatpath[$j]); |
| 852 |
|
} |
| 853 |
|
} |
| 854 |
|
$pathed_out[$i] = 2; |
| 855 |
|
} |
| 856 |
|
} |
| 857 |
|
} else { // No candidates were eliminated this round. There is a Cyclical Tie. |
| 858 |
|
// Drop all the beatpaths tied for weakest. |
| 859 |
|
$index = count($beatpath)-1; |
| 860 |
|
$value = $beatpath[$index][2]; |
| 861 |
|
do { |
| 862 |
|
unset($beatpath[$index]); |
| 863 |
|
$new = $beatpath[$index-1][2]; |
| 864 |
|
$index--; |
| 865 |
|
} while ($new == $value); |
| 866 |
|
$ranking[$round_count][] = "Cyclical Tie"; |
| 867 |
|
} |
| 868 |
|
} |
| 869 |
|
// Everyone left is tied for the win. |
| 870 |
|
$round_count++; |
| 871 |
|
$ranking[$round_count][] = "Winner"; |
| 872 |
|
for ($i=1; $i<=$original_candidates; $i++) { |
| 873 |
|
if (!$pathed_out[$i]) { |
| 874 |
|
$ranking[$round_count][] = $i; |
| 875 |
|
$winner_count++; |
| 876 |
|
} |
| 877 |
|
} |
| 878 |
|
if ($winner_count>1) { |
| 879 |
|
$ranking[$round_count][0] = "Tie for Win"; |
| 880 |
|
} |
| 881 |
|
return $ranking; |
| 882 |
|
} |
Parent Directory
| 
Revision Log
| 
Revision Graph
| 
Patch