"; PrintPairwiseMatrix( $nOptions, $matrix ); } for ( $x = 0; $x < $nOptions; $x++ ) $winners[$x] = 1; $defeats = ComputeDefeatsMatrix( $nOptions, $matrix ); if ( $verbosity == "everything" || $verbosity == "some" ) { echo "
The defeats matrix was:
"; PrintPairwiseMatrix( $nOptions, $defeats ); } for ( $x = 0; $x < $nOptions; $x++ ) { for ( $y = 0; $y < $nOptions; $y++ ) { $kept[$x][$y] = 0; $considered[$x][$y] = 0; if ( $defeats[$x][$y] > 0 ) $tie[$x][$y] = 1; else $tie[$x][$y] = 0; } } if ( $verbosity == "everything" || $verbosity == "some" ) echo "
"; // first pass // vertices that don't cycle back to themselves // have defeats we can keep FloydsAlgorithm( $nOptions, $tie ); if ( $verbosity == "everything" ) { echo "The first pass Floyd results:
"; PrintFloydMatrix( $nOptions, $tie ); } for ( $x = 0; $x < $nOptions; $x++ ) { for ( $y = 0; $y < $nOptions; $y++ ) { if ( $defeats[$x][$y] > 0 ) { if ( $tie[$y][$y] == 0 ) { $kept[$x][$y] = 1; $considered[$x][$y] = 1; $winners[$y] = 0; if ( $verbosity == "everything" || $verbosity == "some" ) echo "Now Keeping: " . $x . " defeats " . $y . "
"; } } } } if ( $verbosity == "everything" ) { echo "
The first pass results were:
"; PrintPairwiseMatrix( $nOptions, $kept ); } SortUnconsideredDefeats( $defeats, $considered, $matrix, $nOptions, $sortedDefeats, $nSortedDefeats ); if ( $verbosity == "everything" ) { echo "
Remaining defeats to consider:
"; for ( $x = 0; $x < $nSortedDefeats; $x++ ) { $defeatLine = sprintf( "defeat #%3s: %3s defeated %3s - Strength: %7s - Margin: %7s", $x, $sortedDefeats[$x]['x'], $sortedDefeats[$x]['y'], $sortedDefeats[$x]['strength'], $sortedDefeats[$x]['margin'] ); echo $defeatLine . "
"; } } while ( count( $sortedDefeats ) > 0 ) { // Add in the already kept defeats $tie = $kept; // find the next set of defeats to check cycles for $startDefeat = array_pop( $sortedDefeats ); $consideringDefeats[0] = $startDefeat; $tie[$startDefeat['x']][$startDefeat['y']] = 1; $considered[$startDefeat['x']][$startDefeat['y']] = 1; $lastDefeat = end( $sortedDefeats ); while ( count( $sortedDefeats ) > 0 && $lastDefeat['strength'] == $startDefeat['strength'] && $lastDefeat['margin'] == $startDefeat['margin'] ) { $defeat = array_pop( $sortedDefeats ); array_push( $consideringDefeats, $defeat ); $tie[$defeat['x']][$defeat['y']] = 1; $considered[$defeat['x']][$defeat['y']] = 1; $lastDefeat = end( $sortedDefeats ); } if ( $verbosity == "everything" ) { echo "
Now Considering:
"; foreach( $consideringDefeats as $defeat ) { $defeatLine = sprintf( "defeat: %3s defeated %3s - Strength: %7s - Margin: %7s", $defeat['x'], $defeat['y'], $defeat['strength'], $defeat['margin'] ); echo $defeatLine . "
"; } echo "
Checking cycles on:
"; PrintPairwiseMatrix( $nOptions, $tie ); } FloydsAlgorithm( $nOptions, $tie ); if ( $verbosity == "everything" ) { echo "
Floyd result:
"; PrintFloydMatrix( $nOptions, $tie ); } if ( $verbosity == "everything" || $verbosity == "some" ) echo "
"; foreach( $consideringDefeats as $defeat ) { $x = $defeat['x']; $y = $defeat['y']; if ( $tie[$y][$x] == 0 ) { $kept[$x][$y] = 1; $winners[$y] = 0; if ( $verbosity == "everything" || $verbosity == "some" ) { $keepingLine = sprintf( "Now Keeping: %3s defeated %3s", $x, $y ); echo $keepingLine . "
"; } } } if ( $verbosity == "everything" ) { echo "
Kept Matrix:
"; PrintPairwiseMatrix( $nOptions, $kept ); echo "
Considered Matrix:
"; PrintPairwiseMatrix( $nOptions, $considered ); } // Clear the $consideringDefeats foreach( $consideringDefeats as $defeat ) array_pop( $consideringDefeats ); } $winResult = "WIN-" . implode( "-", $winners ); return $winResult; } function DefeatCompare( $a, $b ) { $result = 0; if ( $a['strength'] < $b['strength'] ) $result = -1; else if ( $a['strength'] > $b['strength'] ) $result = 1; else if ( $a['margin'] < $b['margin'] ) $result = -1; else if ( $a['margin'] > $b['margin'] ) $result = 1; return $result; } function SortUnconsideredDefeats( $defeats, $considered, $matrix, $nOptions, &$sortedDefeats, &$nSortedDefeats ) { $nSortedDefeats = 0; // Extract the defeats for ( $x = 0; $x < $nOptions; $x++ ) { for ( $y = 0; $y < $nOptions; $y++ ) { if ( $defeats[$x][$y] > 0 && $considered[$x][$y] == 0 ) { $sortedDefeats[$nSortedDefeats]['x'] = $x; $sortedDefeats[$nSortedDefeats]['y'] = $y; $sortedDefeats[$nSortedDefeats]['strength'] = $defeats[$x][$y]; $sortedDefeats[$nSortedDefeats]['margin'] = $matrix[$x][$y] - $matrix[$y][$x]; $nSortedDefeats++; } } } if ( $nSortedDefeats > 0 ) $sortResult = usort( $sortedDefeats, "DefeatCompare" ); } ?>