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.

Think about what happens with `i < mat.size())` when you `i = mat.size();` and then `i++;`. If you mean to break out of a loop, use `break`; don't try to break out by falsifying the loop condition. — molbdnilo, Feb 21 '23 at 07:39
`colors[i] != color` immediately followed by `colors[idx] = color` makes me suspicious that `i` should be `idx` or visa versa. Using meaningful variable names would help understand your code — Alan Birtles, Feb 21 '23 at 07:39
[Why should I not #include ?](https://stackoverflow.com/a/31816096/430766) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/430766) — bitmask, Feb 21 '23 at 07:40
you go out of bounds of the `color` vector on line 24: https://godbolt.org/z/hd6boxbh3. `mat.size()` is `7` therefore the maximum value of `idx` is `6` but `colors` only has 6 elements causing a crash when you do `colors[idx]` — Alan Birtles, Feb 21 '23 at 08:00
This problem is, generally speaking, a task for a debugger. Step through your code, one line at a time, and check the value `i` and `idx` immediately before they are being used as array indices. You'll probably find one (maybe both) is going out of bounds for the vector it is being used for - which causes undefined behaviour (memory problems allocating or deallocating are ONE possible symptom of undefined behaviour). If you can't/won't use a debugger, add code to do those checks BEFORE EVERY usage as indices (and output something obvious when an invalid index is encountered). — Peter, Feb 21 '23 at 08:02
should `m` be `mat.size()-1` rather than the magic number `5`? https://godbolt.org/z/1f8KGbsnd — Alan Birtles, Feb 21 '23 at 08:07
After the debugger stops with an error, did you look at the stacktrace to see how you got there and inspect variable values in the stackframes leading up to the crash - what did you learn by doing so? In short; *use the debugger* :) — Jesper Juhl, Feb 21 '23 at 08:26

score 1 · Accepted Answer · answered Feb 21 '23 at 08:26

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.

answered Feb 21 '23 at 08:26

molbdnilo

64,751
3
43
82

score 0 · Answer 2 · answered Feb 21 '23 at 07:37

0

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.

answered Feb 21 '23 at 07:37

YSC

38,212
9
96
149

It won't recurse deeper than `mat.size()`, which is 5, so I doubt that it's the problem. – molbdnilo Feb 21 '23 at 07:41
A stack overflow would normally result in a segfault rather than an abort. Looks more like heap corruption to me – Alan Birtles Feb 21 '23 at 07:41
@molbdnilo it's not the depth that kills it, it's the width. At depth `n`, you have `m*mat.size()` direct calls to depth `n+1`, so I'd say about `n^(5*49)` calls. At depth 2 (yes only two) you already have a width of ~10e73 calls. – YSC Feb 21 '23 at 07:46
@AlanBirtles Can be. There's an issue with the recursive algorithm anyway. – YSC Feb 21 '23 at 07:48

Im getting SIGABRT error in my c++ recursive code

2 Answers2