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

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;
}
}
}

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;
}
• thank you so much it's working for me Aug 11 '20 at 5:29