PSET3 - Tideman - Locking pairs

Question

I'm looking for a little help to check my logic on this problem set. Lock function schould: Starting with the strongest pair , go through the pairs (pairs[]) of candidates in order(from strongest to weakest victory) and “lock in” each pair to the candidate graph, so long as locking in that pair does not create a cycle in the graph. "Lock in" means filling 2d array (bool locked[][]) with "true" value. When candidate A wins with candidate B program sholud do locked[A][B]=true;. My code "lock's first pair(pairs[0]). Then goes to the next pair(pairs[1]) and check's if loser of this pair (pairs[1].loser) is not the same to the winner of previous pair (pairs[0].winner). if not it locks current pair (pairs[1]). And so on. Program check's all previous winners and compares them to current loser. From check50 i get info like: :( lock_pairs locks all pairs when no cycles lock_pairs did not lock all pairs :) lock_pairs skips final pair if it creates cycle :( lock_pairs skips middle pair if it creates a cycle lock_pairs did not correctly lock all non-cyclical pairs I just dont have the clue what is wrong here.

Mu code:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
int counter;
locked[pairs[0].winner][pairs[0].loser] = true;
for (int i = 1; i < pair_count; i++)
{
    counter = 0;
    for (int j = 0; j < i; j++)
    {
        if (pairs[i].loser == pairs[j].winner)
        {
            counter++;
        }
        else
        {

        }
    }
    if ( counter != 0)
    {

    }
    else
    {
        locked[pairs[i].winner][pairs[i].loser] = true;
        printf("locked[%i][%i] = %d \n", pairs[i].winner, pairs[i].loser, locked[pairs[i].winner] 
[pairs[i].loser]);
    }

}
for (int a = 0; a< candidate_count; a++)
{
    for (int b = 0; b < candidate_count; b++)
    {
        printf("locked[%i][%i] = %d \n", a, b, locked[a][b]);
    }
}

return;

Answer 1

I think you're making this more complicated than you need to. All you need to do for lock_pairs is to locked[pairs[i].winner][pairs[i].loser] = true; if and only if the relation does not make a circle.

What exactly does"constitute a circle" mean? This is explained very well by the course itself. More info right there

So, it'd be ideal to have a recursive function that checks whether or not a relation makes a circle, something like-

// Recursive function to check if entry makes a circle
bool makes_circle(int cycle_start, int loser)
{
    if (loser == cycle_start)
    {
        // If the current loser is the cycle start
        // The entry makes a circle
        return true;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[loser][i])
        {
            if (makes_circle(cycle_start, i))
            {
                // Forward progress through the circle
                return true;
            }
        }
    }
    return false;
}

Notice that cycle_start is constant throughout the entire recursion - this is the pairs[i].winner from your main function - this is what you need to keep track of

So your lock_pairs would now look far simpler-

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs()
{
    for (int i = 0; i < pair_count; i++)
    {
        if (!makes_circle(pairs[i].winner, pairs[i].loser))
        {
            // Lock the pair unless it makes a circle
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}