php - Problem in sorting non dominated pairs of a set of points

Question

I wrote non dominated sorting algorithm in php based on the NSGA II algorithm. The portion of the code is given below

function fast_non_dominated_sort($values1, $values2)
{
    
    $S= [];
    for($i=0; $i<sizeof($values1); $i++)
        $S[$i]= [];

    $front=[[]];
    $n= [];
    $rank= [];

    for($i=0;$i<sizeof($values1); $i++)
    {
        $n[$i]=0;
        $rank[$i]=0;
    }
    

    for($p=0;$p<sizeof($values1); $p++)
    {
        $S[$p]=[];
        $n[$p]=0;
        for($q=0;$q<sizeof($values1); $q++)
        {

            if(($values1[$p] > $values1[$q] && $values2[$p] > $values2[$q]) || ($values1[$p] >= $values1[$q] && $values2[$p] > $values2[$q]) || ($values1[$p] > $values1[$q] and $values2[$p] >= $values2[$q]))                                                                                              
                if(!in_array($q, $S[$p]))
                    array_push($S[$p], $q);


            elseif(($values1[$q] > $values1[$p] && $values2[$q] > $values2[$p]) || ($values1[$q] >= $values1[$p] && $values2[$q] > $values2[$p]) || ($values1[$q] > $values1[$p] && $values2[$q] >= $values2[$p]))
                $n[$p]=$n[$p]+1;

        }

        if($n[$p]==0)
        {
            $rank[$p]=0;
            if(!in_array($p, $front[0]))
                array_push($front[0], $p);
        }

    }
    
    
    $i=0;
    while($front[$i]!=[])
    {
        $Q=[];

        foreach($front[$i] as $p)
        {
            foreach($S[$p] as $q)
            {
                $n[$q]=$n[$q]-1;
                if($n[$q]==0)
                {
                    $rank[$q]=$i+1;
                    if(!in_array($q, $Q))
                        array_push($Q, $q);
                }   
            }
        }

        $i=$i+1;
        array_push($front, $Q);
    }

    unset($front[sizeof($front)-1]);
    return $front;
}


$x_values=[190, 180, 165, 160];
$y_values=[80, 85, 70, 22];


$result=fast_non_dominated_sort($x_values, $y_values);

The returned sorted points are [[0,1,2,3]]. However the result should have been [[0,1], [2], [3]]. Can anybody help me find out the bug in this code.

Any help is appreciated. For further clarifications drop a comment.

question from:https://stackoverflow.com/questions/65863083/problem-in-sorting-non-dominated-pairs-of-a-set-of-points

Answer 1

Here is a simpler demonstration to express why the lack of curly braces fundamentally alters your intended conditional logic:

Code: (Demo)

$lookup = [3, 4];
$array = [1, 2, 3, 3, 1];

foreach ($array as $i => $v) {
    echo "
iteration ($i): ";
    if ($v > 1)
        if (in_array($v, $lookup))
            echo "greater than 1 and in lookup";
    
    elseif ($v < 2)
        echo "less than 2";
}

echo "
---
";

foreach ($array as $i => $v) {
    echo "
iteration ($i): ";
    if ($v > 1) {
        if (in_array($v, $lookup)) {
            echo "greater than 1 and in lookup";
        }
    } elseif ($v < 2) {
        echo "less than 2";
    }
}

Output:

iteration (0): 
iteration (1): 
iteration (2): greater than 1 and in lookup
iteration (3): greater than 1 and in lookup
iteration (4): 
---

iteration (0): less than 2
iteration (1): 
iteration (2): greater than 1 and in lookup
iteration (3): greater than 1 and in lookup
iteration (4): less than 2

Notice that your elseif is treated as though it is the sibling of the if(in_array(...)) condition, despite your code tabbing expressing your desired logic to mean that it is the sibling of the parent if().

The moral of this story, never skip writing curly braces on any control structure. Please adopt the coding standards outlined in PSR-12.

---

I don't understand the required logic for your algorithm, but I will assume it is correct and refine your code to the best of my understanding.

Code: (Demo)

function fast_non_dominated_sort($values1, $values2)
{
    $size = count($values1);
    for ($i = 0; $i < $size; ++$i) {
        $S[]= [];
        $n[] = 0;
        $rank[] = 0;
    }
    $front=[[]];

    for ($p = 0; $p < $size; ++$p) {
        for ($q = 0; $q < $size; ++$q) {
            if (($values1[$p] >= $values1[$q] && $values2[$p] > $values2[$q])
                || ($values1[$p] > $values1[$q] and $values2[$p] >= $values2[$q])
            ) {
                if (!in_array($q, $S[$p])) {
                    $S[$p][] = $q;
                }
            } elseif(($values1[$q] >= $values1[$p] && $values2[$q] > $values2[$p])
                || ($values1[$q] > $values1[$p] && $values2[$q] >= $values2[$p])
            ) {
                ++$n[$p];
            }
        }

        if (!$n[$p]) {
            $rank[$p] = 0;
            if(!in_array($p, $front[0])) {
                $front[0][] = $p;
            }
        }
    }
    
    
    $i = 0;
    while ($front[$i]) {
        $Q = [];
        foreach ($front[$i] as $p) {
            foreach ($S[$p] as $q) {
                --$n[$q];
                if (!$n[$q]) {
                    $rank[$q] = $i + 1;
                    if (!in_array($q, $Q)) {
                        $Q[] = $q;
                    }
                }   
            }
        }

        ++$i;
        $front[] = $Q;
    }

    unset($front[sizeof($front) - 1]);
    return $front;
}


$x_values = [190, 180, 165, 160];
$y_values = [80, 85, 70, 22];


var_export(fast_non_dominated_sort($x_values, $y_values));

Output:

array (
  0 => 
  array (
    0 => 0,
    1 => 1,
  ),
  1 => 
  array (
    0 => 2,
  ),
  2 => 
  array (
    0 => 3,
  ),
)