tideman cycle check example

Example: How to detect cycles tideman cs50

bool is_circle (bool locked_array[MAX][MAX], int candi_count)
{
    //check the basic case
    //if there is only one node of course it doesn't form a circle
    if (candi_count == 1)
    {
        return false;
    }

    //recursively check whether the smaller locked_array with n-1 candidate form a circle
    //if the smaller one have a circle
    //this mean a middle pair create a circle if added into the "locked" table
    if (!is_circle(locked_array, candi_count - 1))
    {
        //if the one-size smaller "locked" table doesn't have a circle
        //check whether adding a new candidate forms a circle

        //if there is a column that is all false's after adding a new candidate
        //then it must not introduce a circle in this step
        for (int j = 0; j < candi_count; j++)
        {
            //a indicator variable for check whether a column has a true value;
            bool true_in_column = false;

            for (int i = 0; i < candi_count; i++)
            {
                if (locked_array[i][j] == true)
                {
                    true_in_column = true;
                }
            }

            //if there is a column doesn't have a true value then not circle is create at this step
            if (true_in_column == false)
            {
                return false;
            }
        }

        //if we cannot find such a column then the graph represented by current locked array
        //must have a circle
        return true;

    }

    //the smaller "locked" table forms a circle
    else
    {
        return true;
    }

}

Tags:

Misc Example