1

can anyone please help I got only one error which is:-

lock_pairs skips final pair if it creates cycle lock_pairs did not correctly lock all non-cyclical pairs

and this is my code

bool hash_cycle(int index, bool visited[])
{
    if(visited[index])
    {
        return true;
    }
    visited[index] = true;
    for(int i = 0; i < pair_count; i++)
    {
        if(locked[index][i] && hash_cycle(i, visited))
        {
            return true;
        }
    }
    return false;
}

bool cycle(int index)
{
    bool visited[pair_count];
    for (int i = 0; i < pair_count; i++)
    {
        visited[i] = false;
    }
    return hash_cycle(index, visited);
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        locked[pairs[i].winner][pairs[i].loser] = true;

        if (cycle(i))
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }
}



1

Instead of doing if(cycle[i]) do if(cycle(pairs[i].winner)). It should fix your problem because you are just calling a random iterator instead of the index of your respective candidate node.

Also, from my understanding, looping through pair_count results in out of bounds errors. For example, 5 candidates will generate more than 5 pairs (let's say 8 for example), however we are only interested in the 5 possible candidates. We do not have eight candidates and our adjacency matrix is still only 5x5.

I have attached my code in case it helps:

void lock_pairs(void)
{
    //lock edges
    for(int i = 0; i < pair_count; i++)
    {
        locked[pairs[i].winner][pairs[i].loser] = true;
        //check for cycle
        if(cycle(pairs[i].winner))
            locked[pairs[i].winner][pairs[i].loser] = false;
    }
}

//check for a cycle. Returns true or false.
bool cycle(int start_index)
{
    bool visited[candidate_count];
    for(int i = 0; i < candidate_count; ++i)
        visited[i] = false;
    return cycle_help(start_index, visited);
}

bool cycle_help(int index, bool visited[])
{
if(visited[index])
    return true;

visited[index] = true;

for(int i = 0; i < candidate_count; ++i)
{
    if(locked[index][i] && cycle_help(i, visited))
    {
            return true;
    }
}
return false;
}
| improve this answer | |
  • thank you so much it's working for me – Aman Singh Aug 11 at 5:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .