0

So, I need to make a function that is going to return the chromatic number of a graph. The graph is given through an adjecency matrix that the function finds using a file name. I have a function that should in theory work and which the compiler is throwing no issues for, yet when I run it, it simply prints out an empty line and ends the program.


#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

int Find_Chromatic_Number (vector <vector <int>> matg, int matc[], int n) {

    if (n == 0) {
        return 0;
    }

    int result, i, j;
    result = 0;

    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            if (matg[i][j] == 1) {
                if (matc[i] == matc[j]) {
                    matc[j]++;
                }
            }
        }
    }

    for (i = 0; i < n; i++) {
        if (result < matc[i]) {
            result = matc[i];
        }
    }

    return result;
}

int main() {
    string file;
    int n, i, j, m;

    cout << "unesite ime datoteke: " << endl;
    cin >> file;

    ifstream reader;
    reader.open(file.c_str());

    reader >> n;

    vector<vector<int>> matg(n, vector<int>(0));
    int matc[n];
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            reader >> matg[i][j];
        }
        matc[i] = 1;
    }

    int result = Find_Chromatic_Number(matg, matc, n);

    cout << result << endl;

    return 0;

}

The program is supposed to use an freader to convert the file into a 2D vector which represents the adjecency matrix (matg). I also made an array (matc) which represents the value of each vertice, with different numbers corresponding to different colors. The function should go through the vector and every time there is an edge between two vertices it should check if their color value in matc is the same. If it is, it ups the second vale (j) by one. After the function has passed through the vector, the matc array should contain n different number with the highest number being the chromatic number I am looking for. I hope I have explained enough of what I am trying to accomplish, if not just ask and I will add any further explanations.

Matej Kovačić
  • 1
  • 2
    `int matc[n];` is not a valid c++, see [this](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) question why. – Hawky Jan 12 '20 at 18:03
  • 1
    I don't know if this is all of the problem, but `vector> matg(n, vector(0));` defines a vector of 0-sized vectors. Your subsequent access to `matg[i][j]` results in Undefined Behavior. `vector> matg(n, vector(n));` would work better. Then pass it by `const &` to `Find_Chromatic_Number` to avoid making a copy. – 1201ProgramAlarm Jan 12 '20 at 18:10
  • thanks that clears up why it's not returning anything, but I now have trouble with the compiler because it doesn't recognize the operator < for some reason – Matej Kovačić Jan 12 '20 at 18:13

1 Answers1

0

Try to make it like that. Don't choose a size for your vector vector<vector<int> > matg; And instead of using reader >> matg[i][j]; use:

int tmp;
reader >> tmp;
matg[i].push_back(tmp);
Mahmoud Hendi
  • 139
  • 11
  • wouldn't that cause the matrix to be copied wrong, seeing as how that would take the current element an push it to the furthest available index in the vector? – Matej Kovačić Jan 12 '20 at 18:21
  • No, it wouldn't. You add element one after one and that's that push_back is doing. that's for sure isn't the best solution but try this out. – Mahmoud Hendi Jan 12 '20 at 18:23