| Index: trunk/extensions/SecurePoll/SecurePoll.i18n.php |
| — | — | @@ -154,6 +154,9 @@ |
| 155 | 155 | 'securepoll-no-upload' => 'No file was uploaded, cannot tally results.', |
| 156 | 156 | 'securepoll-dump-corrupt' => 'The dump file is corrupt and cannot be processed.', |
| 157 | 157 | 'securepoll-tally-upload-error' => 'Error tallying dump file: $1', |
| | 158 | + 'securepoll-pairwise-victories' => 'Pairwise victory matrix', |
| | 159 | + 'securepoll-strength-matrix' => 'Path strength matrix', |
| | 160 | + 'securepoll-ranks' => 'Final ranking', |
| 158 | 161 | ); |
| 159 | 162 | |
| 160 | 163 | /** Message documentation (Message documentation) |
| Index: trunk/extensions/SecurePoll/SecurePoll.php |
| — | — | @@ -79,6 +79,7 @@ |
| 80 | 80 | 'SecurePoll_XMLStore' => "$dir/includes/Store.php", |
| 81 | 81 | 'SecurePoll_Tallier' => "$dir/includes/Tallier.php", |
| 82 | 82 | 'SecurePoll_PluralityTallier' => "$dir/includes/Tallier.php", |
| | 83 | + 'SecurePoll_SchulzeTallier' => "$dir/includes/Tallier.php", |
| 83 | 84 | 'SecurePoll_TallyPage' => "$dir/includes/TallyPage.php", |
| 84 | 85 | 'SecurePoll_TranslatePage' => "$dir/includes/TranslatePage.php", |
| 85 | 86 | 'SecurePoll_Voter' => "$dir/includes/Voter.php", |
| Index: trunk/extensions/SecurePoll/includes/Tallier.php |
| — | — | @@ -1,7 +1,7 @@ |
| 2 | 2 | <?php |
| 3 | 3 | |
| 4 | 4 | abstract class SecurePoll_Tallier { |
| 5 | | - var $context, $question; |
| | 5 | + var $context, $question, $optionsById; |
| 6 | 6 | |
| 7 | 7 | abstract function addVote( $scores ); |
| 8 | 8 | abstract function getHtmlResult(); |
| — | — | @@ -23,7 +23,56 @@ |
| 24 | 24 | function __construct( $context, $question ) { |
| 25 | 25 | $this->context = $context; |
| 26 | 26 | $this->question = $question; |
| | 27 | + foreach ( $this->question->getOptions() as $option ) { |
| | 28 | + $this->optionsById[$option->getId()] = $option; |
| | 29 | + } |
| 27 | 30 | } |
| | 31 | + |
| | 32 | + function convertRanksToHtml( $ranks ) { |
| | 33 | + $s = "<table class=\"securepoll-results\">"; |
| | 34 | + $ids = array_keys( $ranks ); |
| | 35 | + foreach ( $ids as $i => $oid ) { |
| | 36 | + $rank = $ranks[$oid]; |
| | 37 | + $prevRank = isset( $ids[$i-1] ) ? $ranks[$ids[$i-1]] : false; |
| | 38 | + $nextRank = isset( $ids[$i+1] ) ? $ranks[$ids[$i+1]] : false; |
| | 39 | + if ( $rank === $prevRank || $rank === $nextRank ) { |
| | 40 | + $rank .= '*'; |
| | 41 | + } |
| | 42 | + |
| | 43 | + $option = $this->optionsById[$oid]; |
| | 44 | + $s .= "<tr>" . |
| | 45 | + Xml::element( 'td', array(), $rank ) . |
| | 46 | + Xml::element( 'td', array(), $option->parseMessage( 'text' ) ) . |
| | 47 | + "</tr>\n"; |
| | 48 | + } |
| | 49 | + $s .= "</table>"; |
| | 50 | + return $s; |
| | 51 | + } |
| | 52 | + |
| | 53 | + function convertRanksToText( $ranks ) { |
| | 54 | + $s = ''; |
| | 55 | + $ids = array_keys( $ranks ); |
| | 56 | + $colWidth = 6; |
| | 57 | + foreach ( $this->optionsById as $option ) { |
| | 58 | + $colWidth = max( $colWidth, $option->getMessage( 'text' ) ); |
| | 59 | + } |
| | 60 | + |
| | 61 | + foreach ( $ids as $i => $oid ) { |
| | 62 | + $rank = $ranks[$oid]; |
| | 63 | + $prevRank = isset( $ids[$i-1] ) ? $ranks[$ids[$i-1]] : false; |
| | 64 | + $nextRank = isset( $ids[$i+1] ) ? $ranks[$ids[$i+1]] : false; |
| | 65 | + if ( $rank === $prevRank || $rank === $nextRank ) { |
| | 66 | + $rank .= '*'; |
| | 67 | + } |
| | 68 | + |
| | 69 | + $option = $this->optionsById[$oid]; |
| | 70 | + $s .= str_pad( $rank, 6 ) . ' | ' . |
| | 71 | + $option->getMessage( 'text' ) . "\n"; |
| | 72 | + } |
| | 73 | + return $s; |
| | 74 | + } |
| | 75 | + |
| | 76 | + |
| 28 | 77 | } |
| 29 | 78 | |
| 30 | 79 | /** |
| — | — | @@ -59,9 +108,10 @@ |
| 60 | 109 | // Show the results |
| 61 | 110 | $s = "<table class=\"securepoll-results\">\n"; |
| 62 | 111 | |
| 63 | | - foreach ( $this->question->getOptions() as $option ) { |
| | 112 | + foreach ( $this->tally as $oid => $rank ) { |
| | 113 | + $option = $this->optionsById[$oid]; |
| 64 | 114 | $s .= '<tr><td>' . $option->getMessage( 'text' ) . "</td>\n" . |
| 65 | | - '<td>' . $this->tally[$option->getId()] . "</td>\n" . |
| | 115 | + '<td>' . $this->tally[$oid] . "</td>\n" . |
| 66 | 116 | "</tr>\n"; |
| 67 | 117 | } |
| 68 | 118 | $s .= "</table>\n"; |
| — | — | @@ -71,7 +121,8 @@ |
| 72 | 122 | function getTextResult() { |
| 73 | 123 | // Calculate column width |
| 74 | 124 | $width = 10; |
| 75 | | - foreach ( $this->question->getOptions() as $option ) { |
| | 125 | + foreach ( $this->tally as $oid => $rank ) { |
| | 126 | + $option = $this->optionsById[$oid]; |
| 76 | 127 | $width = max( $width, strlen( $option->getMessage( 'text' ) ) ); |
| 77 | 128 | } |
| 78 | 129 | if ( $width > 57 ) { |
| — | — | @@ -84,7 +135,8 @@ |
| 85 | 136 | if ( $qtext !== '' ) { |
| 86 | 137 | $s .= wordwrap( $qtext ) . "\n"; |
| 87 | 138 | } |
| 88 | | - foreach ( $this->question->getOptions() as $option ) { |
| | 139 | + foreach ( $this->tally as $oid => $rank ) { |
| | 140 | + $option = $this->optionsById[$oid]; |
| 89 | 141 | $otext = $option->getMessage( 'text' ); |
| 90 | 142 | if ( strlen( $otext ) > $width ) { |
| 91 | 143 | $otext = substr( $otext, 0, $width - 3 ) . '...'; |
| — | — | @@ -115,6 +167,8 @@ |
| 116 | 168 | abstract class SecurePoll_PairwiseTallier extends SecurePoll_Tallier { |
| 117 | 169 | var $optionIds = array(); |
| 118 | 170 | var $victories = array(); |
| | 171 | + var $abbrevs; |
| | 172 | + var $rowLabels = array(); |
| 119 | 173 | |
| 120 | 174 | function __construct( $context, $question ) { |
| 121 | 175 | parent::__construct( $context, $question ); |
| — | — | @@ -146,32 +200,284 @@ |
| 147 | 201 | } |
| 148 | 202 | return true; |
| 149 | 203 | } |
| | 204 | + |
| | 205 | + function getOptionAbbreviations() { |
| | 206 | + if ( is_null( $this->abbrevs ) ) { |
| | 207 | + $abbrevs = array(); |
| | 208 | + foreach ( $this->question->getOptions() as $option ) { |
| | 209 | + $text = $option->getMessage( 'text' ); |
| | 210 | + $parts = explode( ' ', $text ); |
| | 211 | + $initials = ''; |
| | 212 | + foreach ( $parts as $part ) { |
| | 213 | + if ( $part === '' || ctype_punct( $part[0] ) ) { |
| | 214 | + continue; |
| | 215 | + } |
| | 216 | + $initials .= $part[0]; |
| | 217 | + } |
| | 218 | + if ( isset( $abbrevs[$initials] ) ) { |
| | 219 | + $index = 2; |
| | 220 | + while ( isset( $abbrevs[$initials . $index] ) ) { |
| | 221 | + $index++; |
| | 222 | + } |
| | 223 | + $initials .= $index; |
| | 224 | + } |
| | 225 | + $abbrevs[$initials] = $option->getId(); |
| | 226 | + } |
| | 227 | + $this->abbrevs = array_flip( $abbrevs ); |
| | 228 | + } |
| | 229 | + return $this->abbrevs; |
| | 230 | + } |
| | 231 | + |
| | 232 | + function getRowLabels( $format = 'html' ) { |
| | 233 | + if ( !isset( $this->rowLabels[$format] ) ) { |
| | 234 | + $rowLabels = array(); |
| | 235 | + $abbrevs = $this->getOptionAbbreviations(); |
| | 236 | + foreach ( $this->question->getOptions() as $option ) { |
| | 237 | + if ( $format == 'html' ) { |
| | 238 | + $label = $option->parseMessage( 'text' ); |
| | 239 | + } else { |
| | 240 | + $label = $option->getMessage( 'text' ); |
| | 241 | + } |
| | 242 | + if ( $label !== $abbrevs[$option->getId()] ) { |
| | 243 | + $label .= ' (' . $abbrevs[$option->getId()] . ')'; |
| | 244 | + } |
| | 245 | + $rowLabels[$option->getId()] = $label; |
| | 246 | + } |
| | 247 | + $this->rowLabels[$format] = $rowLabels; |
| | 248 | + } |
| | 249 | + return $this->rowLabels[$format]; |
| | 250 | + } |
| | 251 | + |
| | 252 | + function convertMatrixToHtml( $matrix, $rankedIds ) { |
| | 253 | + $abbrevs = $this->getOptionAbbreviations(); |
| | 254 | + $rowLabels = $this->getRowLabels( 'html' ); |
| | 255 | + |
| | 256 | + $s = "<table class=\"securepoll-results\">"; |
| | 257 | + |
| | 258 | + # Corner box |
| | 259 | + $s .= "<tr>\n<th> </th>\n"; |
| | 260 | + |
| | 261 | + # Header row |
| | 262 | + foreach ( $rankedIds as $oid ) { |
| | 263 | + $s .= Xml::element( 'th', array(), $abbrevs[$oid] ) . "\n"; |
| | 264 | + } |
| | 265 | + $s .= "</tr>\n"; |
| | 266 | + |
| | 267 | + foreach ( $rankedIds as $oid1 ) { |
| | 268 | + # Header column |
| | 269 | + $s .= "<tr>\n"; |
| | 270 | + $s .= Xml::element( 'td', array( 'class' => 'securepoll-results-row-heading' ), |
| | 271 | + $rowLabels[$oid1] ); |
| | 272 | + # Rest of the matrix |
| | 273 | + foreach ( $rankedIds as $oid2 ) { |
| | 274 | + if ( isset( $matrix[$oid1][$oid2] ) ) { |
| | 275 | + $value = $matrix[$oid1][$oid2]; |
| | 276 | + } else { |
| | 277 | + $value = ''; |
| | 278 | + } |
| | 279 | + if ( is_array( $value ) ) { |
| | 280 | + $value = '(' . implode( ', ', $value ) . ')'; |
| | 281 | + } |
| | 282 | + $s .= Xml::element( 'td', array(), $value ) . "\n"; |
| | 283 | + } |
| | 284 | + $s .= "</tr>\n"; |
| | 285 | + } |
| | 286 | + $s .= "</table>"; |
| | 287 | + } |
| | 288 | + |
| | 289 | + function convertMatrixToText( $matrix, $rankedIds ) { |
| | 290 | + $abbrevs = $this->getOptionAbbreviations(); |
| | 291 | + $minWidth = 15; |
| | 292 | + $rowLabels = $this->getRowLabels( 'text' ); |
| | 293 | + |
| | 294 | + # Calculate column widths |
| | 295 | + $colWidths = array(); |
| | 296 | + foreach ( $abbrevs as $id => $abbrev ) { |
| | 297 | + if ( strlen( $abbrev ) < $minWidth ) { |
| | 298 | + $colWidths[$id] = $minWidth; |
| | 299 | + } else { |
| | 300 | + $colWidths[$id] = strlen( $abbrev ); |
| | 301 | + } |
| | 302 | + } |
| | 303 | + $headerColumnWidth = $minWidth; |
| | 304 | + foreach ( $rowLabels as $label ) { |
| | 305 | + $headerColumnWidth = max( $headerColumnWidth, strlen( $label ) ); |
| | 306 | + } |
| | 307 | + |
| | 308 | + # Corner box |
| | 309 | + $s = str_repeat( ' ', $headerColumnWidth ) . ' | '; |
| | 310 | + |
| | 311 | + # Header row |
| | 312 | + foreach ( $rankedIds as $oid ) { |
| | 313 | + $s .= str_pad( $abbrevs[$oid], $colWidths[$oid] ) . ' | '; |
| | 314 | + } |
| | 315 | + $s .= "\n"; |
| | 316 | + |
| | 317 | + # Divider |
| | 318 | + $s .= str_repeat( '-', $headerColumnWidth ) . '-+-'; |
| | 319 | + foreach ( $rankedIds as $oid ) { |
| | 320 | + $s .= str_repeat( '-', $colWidths[$oid] ) . '-+-'; |
| | 321 | + } |
| | 322 | + $s .= "\n"; |
| | 323 | + |
| | 324 | + foreach ( $rankedIds as $oid1 ) { |
| | 325 | + # Header column |
| | 326 | + $s .= str_pad( $rowLabels[$oid1], $headerColumnWidth ) . ' | '; |
| | 327 | + |
| | 328 | + # Rest of the matrix |
| | 329 | + foreach ( $rankedIds as $oid2 ) { |
| | 330 | + if ( isset( $matrix[$oid1][$oid2] ) ) { |
| | 331 | + $value = $matrix[$oid1][$oid2]; |
| | 332 | + } else { |
| | 333 | + $value = ''; |
| | 334 | + } |
| | 335 | + if ( is_array( $value ) ) { |
| | 336 | + $value = '(' . implode( ', ', $value ) . ')'; |
| | 337 | + } |
| | 338 | + $s .= str_pad( $value, $colWidths[$oid2] ) . ' | '; |
| | 339 | + } |
| | 340 | + $s .= "\n"; |
| | 341 | + } |
| | 342 | + return $s; |
| | 343 | + } |
| | 344 | + |
| 150 | 345 | } |
| 151 | 346 | |
| | 347 | + |
| | 348 | + |
| 152 | 349 | /** |
| | 350 | + * A tallier which gives a tie-breaking ranking of candidates (TBRC) by |
| | 351 | + * selecting random preferential votes |
| | 352 | + */ |
| | 353 | +abstract class SecurePoll_RandomPrefVoteTallier { |
| | 354 | + var $records, $random; |
| | 355 | + |
| | 356 | + function addVote( $vote ) { |
| | 357 | + $this->records[] = $vote; |
| | 358 | + } |
| | 359 | + |
| | 360 | + function getTBRCMatrix() { |
| | 361 | + $tbrc = array(); |
| | 362 | + $marked = array(); |
| | 363 | + |
| | 364 | + $random = $this->context->getRandom(); |
| | 365 | + $status = $random->open(); |
| | 366 | + if ( !$status->isOK() ) { |
| | 367 | + throw new MWException( "Unable to open random device for TBRC ranking" ); |
| | 368 | + } |
| | 369 | + |
| | 370 | + # Random ballot round |
| | 371 | + $numCands = count( $this->optionIds ); |
| | 372 | + $numPairsRanked = 0; |
| | 373 | + $numRecordsUsed = 0; |
| | 374 | + while ( $numRecordsUsed < count( $this->records ) |
| | 375 | + && $numPairsRanked < $numCands * $numCands ) |
| | 376 | + { |
| | 377 | + # Pick the record |
| | 378 | + $recordIndex = $random->getInt( $numCands - $numRecordsUsed ); |
| | 379 | + $ranks = $this->records[$recordIndex]; |
| | 380 | + $numRecordsUsed++; |
| | 381 | + |
| | 382 | + # Swap it to the end |
| | 383 | + $destIndex = $numCands - $numRecordsUsed; |
| | 384 | + $this->records[$recordIndex] = $this->records[$destIndex]; |
| | 385 | + $this->records[$destIndex] = $ranks; |
| | 386 | + |
| | 387 | + # Apply its rankings |
| | 388 | + foreach ( $this->optionIds as $oid1 ) { |
| | 389 | + if ( !isset( $ranks[$oid1] ) ) { |
| | 390 | + throw new MWException( "Invalid vote record, missing option $oid1" ); |
| | 391 | + } |
| | 392 | + foreach ( $this->optionIds as $oid2 ) { |
| | 393 | + if ( isset( $marked[$oid1][$oid2] ) ) { |
| | 394 | + // Already ranked |
| | 395 | + continue; |
| | 396 | + } |
| | 397 | + |
| | 398 | + if ( $oid1 == $oid2 ) { |
| | 399 | + # Same candidate, no win |
| | 400 | + $tbrc[$oid1][$oid2] = false; |
| | 401 | + } elseif ( $ranks[$oid1] < $ranks[$oid2] ) { |
| | 402 | + # oid1 win |
| | 403 | + $tbrc[$oid1][$oid2] = true; |
| | 404 | + } elseif ( $ranks[$oid2] < $ranks[$oid1] ) { |
| | 405 | + # oid2 win |
| | 406 | + $tbrc[$oid1][$oid2] = false; |
| | 407 | + } else { |
| | 408 | + # Tie, don't mark |
| | 409 | + continue; |
| | 410 | + } |
| | 411 | + $marked[$oid1][$oid2] = true; |
| | 412 | + $numPairsRanked++; |
| | 413 | + } |
| | 414 | + } |
| | 415 | + } |
| | 416 | + |
| | 417 | + # Random win round |
| | 418 | + if ( $numPairsRanked < $numCands * $numCands ) { |
| | 419 | + $randomRanks = $random->shuffle( $this->optionIds ); |
| | 420 | + foreach ( $randomRanks as $oidWin ) { |
| | 421 | + if ( $numPairsRanked >= $numCands * $numCands ) { |
| | 422 | + # Done |
| | 423 | + break; |
| | 424 | + } |
| | 425 | + foreach ( $this->optionIds as $oidOther ) { |
| | 426 | + if ( !isset( $marked[$oidWin][$oidOther] ) ) { |
| | 427 | + $tbrc[$oidWin][$oidOther] = true; |
| | 428 | + $marked[$oidWin][$oidOther] = true; |
| | 429 | + $numPairsRanked++; |
| | 430 | + } |
| | 431 | + if ( !isset( $marked[$oidOther][$oidWin] ) ) { |
| | 432 | + $tbrc[$oidOther][$oidWin] = false; |
| | 433 | + $marked[$oidOther][$oidWin] = true; |
| | 434 | + $numPairsRanked++; |
| | 435 | + } |
| | 436 | + } |
| | 437 | + } |
| | 438 | + } |
| | 439 | + |
| | 440 | + return $tbrc; |
| | 441 | + } |
| | 442 | +} |
| | 443 | + |
| | 444 | +/** |
| 153 | 445 | * This is the basic Schulze method with no tie-breaking. |
| 154 | 446 | */ |
| 155 | 447 | class SecurePoll_SchulzeTallier extends SecurePoll_PairwiseTallier { |
| 156 | | - var $strengths; |
| | 448 | + function getPathStrengths( $victories ) { |
| | 449 | + # This algorithm follows Markus Schulze, "A New Monotonic, Clone-Independent, Reversal |
| | 450 | + # Symmetric, and Condorcet-Consistent Single-Winner Election Method" and also |
| | 451 | + # http://en.wikipedia.org/w/index.php?title=User:MarkusSchulze/Statutory_Rules&oldid=303036893 |
| | 452 | + # |
| | 453 | + # Path strengths in the Schulze method are given by pairs of integers notated (a, b) |
| | 454 | + # where a is the strength in one direction and b is the strength in the other. We make |
| | 455 | + # a matrix of path strength pairs "p", giving the path strength of the row index beating |
| | 456 | + # the column index. |
| 157 | 457 | |
| 158 | | - function finishTally() { |
| 159 | | - # This algorithm follows Markus Schulze, "A New Monotonic, Clone-Independent, Reversal |
| 160 | | - # Symmetric, and Condorcet-Consistent Single-Winner Election Method" |
| 161 | | - |
| 162 | | - $this->strengths = array(); |
| | 458 | + # First the path strength matrix is populated with the "direct" victory count in each |
| | 459 | + # direction, i.e. the number of people who preferenced A over B, and B over A. |
| | 460 | + $strengths = array(); |
| 163 | 461 | foreach ( $this->optionIds as $oid1 ) { |
| 164 | 462 | foreach ( $this->optionIds as $oid2 ) { |
| 165 | 463 | if ( $oid1 === $oid2 ) { |
| 166 | 464 | continue; |
| 167 | 465 | } |
| 168 | | - if ( $this->victories[$oid1][$oid2] > $this->victories[$oid2][$oid1] ) { |
| 169 | | - $this->strengths[$oid1][$oid2] = $this->victories[$oid1][$oid2]; |
| 170 | | - } else { |
| 171 | | - $this->strengths[$oid1][$oid2] = 0; |
| 172 | | - } |
| | 466 | + $v12 = $victories[$oid1][$oid2]; |
| | 467 | + $v21 = $victories[$oid2][$oid1]; |
| | 468 | + #if ( $v12 > $v21 ) { |
| | 469 | + # Direct victory |
| | 470 | + $strengths[$oid1][$oid2] = array( $v12, $v21 ); |
| | 471 | + #} else { |
| | 472 | + # Direct loss |
| | 473 | + # $strengths[$oid1][$oid2] = array( 0, 0 ); |
| | 474 | + #} |
| 173 | 475 | } |
| 174 | 476 | } |
| 175 | 477 | |
| | 478 | + echo $this->convertMatrixToText( $strengths, $this->optionIds ) . "\n"; |
| | 479 | + |
| | 480 | + # Next (continuing the Floyd-Warshall algorithm) we calculate the strongest indirect |
| | 481 | + # paths. This part dominates the O(N^3) time order. |
| 176 | 482 | foreach ( $this->optionIds as $oid1 ) { |
| 177 | 483 | foreach ( $this->optionIds as $oid2 ) { |
| 178 | 484 | if ( $oid1 === $oid2 ) { |
| — | — | @@ -181,58 +487,106 @@ |
| 182 | 488 | if ( $oid1 === $oid3 || $oid2 === $oid3 ) { |
| 183 | 489 | continue; |
| 184 | 490 | } |
| 185 | | - $this->strengths[$oid2][$oid3] = max( |
| 186 | | - $this->strengths[$oid2][$oid3], |
| 187 | | - min( |
| 188 | | - $this->strengths[$oid2][$oid1], |
| 189 | | - $this->strengths[$oid1][$oid3] |
| 190 | | - ) |
| 191 | | - ); |
| | 491 | + $s21 = $strengths[$oid2][$oid1]; |
| | 492 | + $s13 = $strengths[$oid1][$oid3]; |
| | 493 | + $s23 = $strengths[$oid2][$oid3]; |
| | 494 | + if ( $this->isSchulzeWin( $s21, $s13 ) ) { |
| | 495 | + $temp = $s13; |
| | 496 | + } else { |
| | 497 | + $temp = $s21; |
| | 498 | + } |
| | 499 | + if ( $this->isSchulzeWin( $temp, $s23 ) ) { |
| | 500 | + $strengths[$oid2][$oid3] = $temp; |
| | 501 | + } |
| 192 | 502 | } |
| 193 | 503 | } |
| 194 | 504 | } |
| 195 | 505 | |
| 196 | | - # Calculate ranks |
| 197 | | - $this->ranks = array(); |
| 198 | | - $rankedOptions = $this->optionIds; |
| 199 | | - usort( $rankedOptions, array( $this, 'comparePair' ) ); |
| 200 | | - $rankedOptions = array_reverse( $rankedOptions ); |
| | 506 | + return $strengths; |
| | 507 | + } |
| | 508 | + |
| | 509 | + function convertStrengthMatrixToRanks( $strengths ) { |
| | 510 | + $unusedIds = $this->optionIds; |
| | 511 | + $ranks = array(); |
| 201 | 512 | $currentRank = 1; |
| 202 | | - foreach ( $rankedOptions as $i => $oid ) { |
| 203 | | - if ( $i > 0 && $this->comparePair( $rankedOptions[$i-1], $oid ) ) { |
| 204 | | - $currentRank = $i + 1; |
| | 513 | + |
| | 514 | + while ( count( $unusedIds ) ) { |
| | 515 | + $winners = array_flip( $unusedIds ); |
| | 516 | + foreach ( $unusedIds as $oid1 ) { |
| | 517 | + foreach ( $unusedIds as $oid2 ) { |
| | 518 | + if ( $oid1 == $oid2 ) { |
| | 519 | + continue; |
| | 520 | + } |
| | 521 | + $s12 = $strengths[$oid1][$oid2]; |
| | 522 | + $s21 = $strengths[$oid2][$oid1]; |
| | 523 | + if ( $this->isSchulzeWin( $s21, $s12 ) ) { |
| | 524 | + # oid1 is defeated by someone, not a winner |
| | 525 | + unset( $winners[$oid1] ); |
| | 526 | + break; |
| | 527 | + } |
| | 528 | + } |
| 205 | 529 | } |
| 206 | | - $this->ranks[$oid] = $currentRank; |
| | 530 | + if ( !count( $winners ) ) { |
| | 531 | + # No winners, everyone ties for this position |
| | 532 | + $winners = array_flip( $unusedIds ); |
| | 533 | + } |
| | 534 | + |
| | 535 | + # Now $winners is the list of candidates that tie for this position |
| | 536 | + foreach ( $winners as $oid => $unused ) { |
| | 537 | + $ranks[$oid] = $currentRank; |
| | 538 | + } |
| | 539 | + $currentRank += count( $winners ); |
| | 540 | + $unusedIds = array_diff( $unusedIds, array_keys( $winners ) ); |
| 207 | 541 | } |
| | 542 | + return $ranks; |
| 208 | 543 | } |
| 209 | 544 | |
| 210 | | - function comparePair( $i, $j ) { |
| 211 | | - if ( $i === $j ) { |
| 212 | | - return 0; |
| 213 | | - } |
| 214 | | - $sij = $this->strengths[$i][$j]; |
| 215 | | - $sji = $this->strengths[$j][$i]; |
| 216 | | - if ( $sij > $sji ) { |
| 217 | | - return 1; |
| 218 | | - } elseif ( $sji > $sij ) { |
| 219 | | - return -1; |
| 220 | | - } else { |
| 221 | | - return 0; |
| 222 | | - } |
| | 545 | + /** |
| | 546 | + * Determine whether Schulze's win relation "s1 >win s2" for path strength |
| | 547 | + * pairs s1 and s2 is satisfied. |
| | 548 | + * |
| | 549 | + * When applied to final path strengths instead of intermediate results, |
| | 550 | + * the paper notates this relation >D (greater than subscript D). |
| | 551 | + * |
| | 552 | + * The inequality in the second part is reversed because the first part |
| | 553 | + * refers to wins, and the second part refers to losses. |
| | 554 | + */ |
| | 555 | + function isSchulzeWin( $s1, $s2 ) { |
| | 556 | + return $s1[0] > $s2[0] || ( $s1[0] == $s2[0] && $s1[1] < $s2[1] ); |
| 223 | 557 | } |
| 224 | 558 | |
| | 559 | + function finishTally() { |
| | 560 | + $this->strengths = $this->getPathStrengths( $this->victories ); |
| | 561 | + $this->ranks = $this->convertStrengthMatrixToRanks( $this->strengths ); |
| | 562 | + } |
| | 563 | + |
| | 564 | + function getRanks() { |
| | 565 | + return $this->ranks; |
| | 566 | + } |
| | 567 | + |
| 225 | 568 | function getHtmlResult() { |
| 226 | | - return '<pre>' . $this->getTextResult() . '</pre>'; |
| | 569 | + global $wgOut; |
| | 570 | + $s = $wgOut->parse( '<h2>' . wfMsgNoTrans( 'securepoll-ranks' ) . "</h2>\n" ); |
| | 571 | + $s .= $this->convertRanksToHtml( $this->ranks ); |
| | 572 | + |
| | 573 | + $s = $wgOut->parse( '<h2>' . wfMsgNoTrans( 'securepoll-pairwise-victories' ) . "</h2>\n" ); |
| | 574 | + $rankedIds = array_keys( $this->ranks ); |
| | 575 | + $s .= $this->convertMatrixToHtml( $this->victories, $rankedIds ); |
| | 576 | + |
| | 577 | + $s .= $wgOut->parse( '<h2>' . wfMsgNoTrans( 'securepoll-strength-matrix' ) . "</h2>\n" ); |
| | 578 | + $s .= $this->convertMatrixToHtml( $this->strengths, $rankedIds ); |
| | 579 | + return $s; |
| 227 | 580 | } |
| 228 | 581 | |
| 229 | 582 | function getTextResult() { |
| 230 | | - return |
| 231 | | - "Victory matrix:\n" . |
| 232 | | - var_export( $this->victories, true ) . "\n\n" . |
| 233 | | - "Path strength matrix:\n" . |
| 234 | | - var_export( $this->strengths, true ) . "\n\n" . |
| 235 | | - "Ranks:\n" . |
| 236 | | - var_export( $this->ranks, true ) . "\n"; |
| | 583 | + $rankedIds = array_keys( $this->ranks ); |
| | 584 | + |
| | 585 | + return |
| | 586 | + wfMsg( 'securepoll-ranks' ) . "\n" . |
| | 587 | + $this->convertRanksToText( $this->ranks ) . "\n\n" . |
| | 588 | + wfMsg( 'securepoll-pairwise-victories' ). "\n" . |
| | 589 | + $this->convertMatrixToText( $this->victories, $rankedIds ) . "\n\n" . |
| | 590 | + wfMsg( 'securepoll-strength-matrix' ) . "\n" . |
| | 591 | + $this->convertMatrixToText( $this->strengths, $rankedIds ); |
| 237 | 592 | } |
| 238 | 593 | } |
| 239 | | - |
| Index: trunk/extensions/SecurePoll/cli/tallyDebian.php |
| — | — | @@ -0,0 +1,91 @@ |
| | 2 | +<?php |
| | 3 | + |
| | 4 | +require( dirname(__FILE__).'/cli.inc' ); |
| | 5 | + |
| | 6 | +if ( !isset( $args[0] ) ) { |
| | 7 | + echo "Usage: php tallyDebian.php <file>\n"; |
| | 8 | + exit( 1 ); |
| | 9 | +} |
| | 10 | + |
| | 11 | +$file = fopen( $args[0], 'r' ); |
| | 12 | +if ( !$file ) { |
| | 13 | + echo "Unable to open file \"$args[0]\" for input\n"; |
| | 14 | +} |
| | 15 | + |
| | 16 | +$votes = array(); |
| | 17 | +$numCands = 0; |
| | 18 | +while ( !feof( $file ) ) { |
| | 19 | + $line = fgets( $file ); |
| | 20 | + if ( $line === false ) { |
| | 21 | + break; |
| | 22 | + } |
| | 23 | + $line = trim( $line ); |
| | 24 | + if ( !preg_match( '/^V: ([0-9-]*)$/', $line, $m ) ) { |
| | 25 | + echo "Skipping unrecognised line $line\n"; |
| | 26 | + continue; |
| | 27 | + } |
| | 28 | + |
| | 29 | + $record = array(); |
| | 30 | + for ( $i = 0; $i < strlen( $m[1] ); $i++ ) { |
| | 31 | + $pref = substr( $m[1], $i, 1 ); |
| | 32 | + if ( $pref === '-' ) { |
| | 33 | + $record[$i] = 1000; |
| | 34 | + } else { |
| | 35 | + $record[$i] = intval( $pref ); |
| | 36 | + } |
| | 37 | + } |
| | 38 | + $votes[] = $record; |
| | 39 | + $numCands = max( $numCands, count( $record ) ); |
| | 40 | +} |
| | 41 | + |
| | 42 | +$options = array(); |
| | 43 | +for ( $i = 0; $i < $numCands - 1; $i++ ) { |
| | 44 | + $options[] = chr( ord( 'A' ) + $i ); |
| | 45 | +} |
| | 46 | +$options[] = 'X'; |
| | 47 | +$question = new SecurePoll_FakeQuestion( $options ); |
| | 48 | +$tallier = new SecurePoll_SchulzeTallier( false, $question ); |
| | 49 | +foreach ( $votes as $vote ) { |
| | 50 | + $tallier->addVote( $vote ); |
| | 51 | +} |
| | 52 | +$tallier->finishTally(); |
| | 53 | +echo $tallier->getTextResult(); |
| | 54 | + |
| | 55 | + |
| | 56 | + |
| | 57 | +class SecurePoll_FakeQuestion { |
| | 58 | + var $options; |
| | 59 | + |
| | 60 | + function __construct( $options ) { |
| | 61 | + $this->options = array(); |
| | 62 | + foreach ( $options as $i => $option ) { |
| | 63 | + $this->options[] = new SecurePoll_FakeOption( $i, $option ); |
| | 64 | + } |
| | 65 | + } |
| | 66 | + |
| | 67 | + function getOptions() { |
| | 68 | + return $this->options; |
| | 69 | + } |
| | 70 | +} |
| | 71 | + |
| | 72 | +class SecurePoll_FakeOption { |
| | 73 | + var $id, $name; |
| | 74 | + |
| | 75 | + function __construct( $id, $name ) { |
| | 76 | + $this->id = $id; |
| | 77 | + $this->name = $name; |
| | 78 | + } |
| | 79 | + |
| | 80 | + function getMessage( $key ) { |
| | 81 | + return $this->name; |
| | 82 | + } |
| | 83 | + |
| | 84 | + function parseMessage( $key ) { |
| | 85 | + return htmlspecialchars( $this->name ); |
| | 86 | + } |
| | 87 | + |
| | 88 | + function getId() { |
| | 89 | + return $this->id; |
| | 90 | + } |
| | 91 | +} |
| | 92 | + |
| Property changes on: trunk/extensions/SecurePoll/cli/tallyDebian.php |
| ___________________________________________________________________ |
| Name: svn:eol-style |
| 1 | 93 | + native |
| Index: trunk/extensions/SecurePoll/resources/SecurePoll.css |
| — | — | @@ -62,4 +62,6 @@ |
| 63 | 63 | .securepoll-results caption { |
| 64 | 64 | font-weight: bold; |
| 65 | 65 | } |
| 66 | | - |
| | 66 | +.securepoll-results-row-heading { |
| | 67 | + background: #f2f2f2; |
| | 68 | +} |