Im getting SIGABRT error in my c++ recursive code

Question

Im running this code and im getting this error

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)
Aborted (core dumped)

When i run it using gdb it says this:

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;

I have no idea why. Please help me.

The code:

#include <bits/stdc++.h>
using namespace std;

bool cancolor(vector<vector<int>> &mat, int m, vector<int> colors, int idx)
{
    if (idx == mat.size())
    {
        return true;
    }
    else
    {
        int color = 1;
        while (color <= m)
        {
            int edges = 0;
            int i = 0;
            while (i < mat.size())
            {
                if (mat[idx][i] == 1)
                {
                    edges++;
                    if (colors[i] != color)
                    {
                        colors[idx] = color;
                        if (cancolor(mat, m, colors, idx + 1))
                        {
                            return true;
                        }
                        colors[idx] = 0;
                    }
                    else
                    {
                        i = mat.size();
                    }
                }
                i++;
            }
            if (edges == 0)
            {
                colors[idx] = color;
                if (cancolor(mat, m, colors, idx + 1))
                {
                    return true;
                }
                return false;
            }
            color++;
        }
        return false;
    }
}

string graphColoring(vector<vector<int>> &mat, int m)
{
    vector<int> colors;
    for (int i = 0; i <= m; i++)
    {
        colors.push_back(0);
    }
    if (cancolor(mat, m, colors, 0))
    {
        return "YES";
    }
    return "NO";
}

int main()
{
    vector<vector<int>> mat = {{0, 0, 0, 1, 0, 0, 0},
                               {0, 0, 1, 0, 1, 0, 0},
                               {0, 1, 0, 0, 1, 0, 1},
                               {1, 0, 0, 0, 0, 0, 0},
                               {0, 1, 1, 0, 0, 0, 0},
                               {0, 0, 0, 0, 0, 0, 0},
                               {0, 0, 1, 0, 0, 0, 0}};
    cout << graphColoring(mat, 5) << endl;
    return 0;
}

If youre wondering what im trying to acheive with this, here is the link: https://www.codingninjas.com/codestudio/problems/981273

I tried to run it using pythontutor but it ended after 174 steps or so, after 5th node.

Answer 1

The problem is in graphColoring; m is the number of colors, but your colors vector should have mat.size() elements.
Writing outside that vector (as you do) has undefined behaviour, and likely leads to some type of memory corrution.

Answer 2

while (color <= m) {
  // ...
   while (i < mat.size()) {
     // ...
     if (cancolor(mat, m, colors, idx + 1))

What you've got there is an exponential explosion. For each idx, you excursively call cancolor() a lot. For each call, another lot of recursive calls will be made. And so forth.

You'd normally run into a stack overflow, but your usage of dynamically allocated memory (probably from the std::vector<int> colors) makes me think the free store explode first.

You should rethink your algorithm; if it is not possible, try and linearise it to reduce your memory needs.

Also, using namsepace std and #include <bits/stdc++.h> are considered harmful. I'll let you search about that.