Some possible coding errors

Prof. Li, thanks for sharing your code. They are really helpful. I believe these are coding errors after comparison with CBS-H2-RTC.

In the following function:

int CBSHeuristic::minimumVertexCover(const vector<int>& CG)
{
    clock_t t = clock();
    int rst = 0;
    std::vector<bool> done(num_of_agents, false);
    for (int i = 0; i < num_of_agents; i++)
    {
        if (done[i])
            continue;
        std::vector<int> indices;
        indices.reserve(num_of_agents);
        std::queue<int> Q;
        Q.push(i);
        done[i] = true;
        while (!Q.empty())
        {
            int j = Q.front(); Q.pop();
            indices.push_back(j);
            for (int k = 0; k < num_of_agents; k++)
            {
                if (CG[j * num_of_agents + k] > 0 || CG[k * num_of_agents + j] > 0)
                {
                    if (!done[k])
                    {
                        Q.push(k);
                        done[k] = true;
                    }
                }
            }
        }
        if ((int) indices.size() == 1) //one node -> no edges -> mvc = 0
            continue;
        else if ((int)indices.size() == 2) // two nodes -> only one edge -> mvc = 1
        {
            rst += 1; // add edge weight
            continue;
        }

        std::vector<int> subgraph(indices.size()  * indices.size(), 0);
        int num_edges = 0;
        for (int j = 0; j < (int) indices.size(); j++)
        {
            for (int k = j + 1; k < (int)indices.size(); k++)
            {
                subgraph[j * indices.size() + k] = CG[indices[j] * num_of_agents + indices[k]];
                subgraph[k * indices.size() + j] = CG[indices[k] * num_of_agents + indices[j]];
                if (subgraph[j * indices.size() + k] > 0)
                    num_edges++;
            }
        }

        if (num_edges > ILP_edge_threshold)
        {
            rst += greedyMatching(subgraph, (int)indices.size());
            double runtime = (double)(clock() - start_time) / CLOCKS_PER_SEC;
            if (runtime > time_limit)
                return -1; // run out of time
        }
        else
        {
            for (int k = 1; i < (int)indices.size(); k++)
            {
                if (KVertexCover(subgraph, (int)indices.size(), num_edges, i=k, (int)indices.size()))
                {
                    rst += k;
                    break;
                }
                double runtime = (double)(clock() - start_time) / CLOCKS_PER_SEC;
                if (runtime > time_limit)
                    return -1; // run out of time
            }
        }
    }
    num_solve_MVC++;
    runtime_solve_MVC += (double)(clock() - t) / CLOCKS_PER_SEC;
    return rst;
}

the following sentences

for (int k = 1; i < (int)indices.size(); k++)
            {
                if (KVertexCover(subgraph, (int)indices.size(), num_edges, i=k, (int)indices.size()))
                {
                    rst += k;
                    break;
                }

should be :

for (int k = 1; k < (int)indices.size(); k++)
            {
                if (KVertexCover(subgraph, (int)indices.size(), num_edges, k, (int)indices.size()))
                {
                    rst += k;
                    break;
                }

Jiaoyang-Li / EECBS

Some possible coding errors #13