";
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" );
}
?>