1

Okay so I'm working on a school task, writing a program that calculates the chromatic number of a graph from a text file that contains the number of vertices and the graph's adjacency matrix, like so:

8

0 1 0 1 1 0 0 1
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 0 0 1 0 0
0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 0

Here's my program:

#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <vector>

#define MAX 512

using namespace std;

bool adjMat[MAX][MAX]; 

int chromaticNum(int n) {
   int chromaticRet = 1; // return value, chromatic number

   vector<int> colors(n, INT_MAX); // color for every vertex
   colors[0] = 0;                  

   // iterating through every vertex except 0 as that one already has a color
   for (int i = 1; i < n; i++) {

      int color = 0; // current/first color
      for (int j = 0; j < n; j++) {   
         if (adjMat[j][i] == 1) {     // 1 = vertices are adjacent
            if (colors[j] == color) { // if the adjacent vertex is that color we change the color to  the next one
               ++color;              
            }
         }
      }
      bool colorAdded = true;
      for (int d = 0; d < n; d++) { // checking if this color has already been used
         if (colors[d] == color) {
            colorAdded = false;
         }
      }
      colors[i] = color;
      if (colorAdded) {
         ++chromaticRet;
      }
   }

   return chromaticRet;
}

int main() {

   string fileName;
   cin >> fileName;
   int i, j;
   ifstream stream;
   stream.open(fileName.c_str());
   int n = 0;

   if (stream.is_open()) {

      stream >> n;
      stream.ignore(1, '\n');


      for (i = 0; i < n; i++) {
         for (j = 0; j < n; j++) {
            stream >> adjMat[i][j];
         }
      }
      cout << "Chromatic number: " << chromaticNum(n) << endl;

   } else {
      cout << "File not found";
   }
   stream.close();

   return 0;
}

This works for about a dozen or so graphs I've tested (cycles, stars, trees, wheels, bipartite graphs, Petersen's graph) but it does not work for Groetzsch's graph. It returns 3 instead of 4 for that one. The text file for that one that I've been using:

11

0 1 1 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0 1 0
1 0 0 0 1 0 1 0 1 0 0
0 1 0 0 1 0 0 0 1 0 1
0 0 1 1 0 0 0 1 0 1 0
0 0 0 0 0 0 1 1 1 1 1 
0 1 1 0 0 1 0 0 0 0 0
1 0 0 0 1 1 0 0 0 0 0 
0 0 1 1 0 1 0 0 0 0 0
0 1 0 0 1 1 0 0 0 0 0 
1 0 0 1 0 1 0 0 0 0 0

This code should only work in a decent time for smaller graphs so I'm not looking to make it more time efficient, I would like to find out why it works for other graphs but not this one.

4

0 回答 0