I have a graph coloring program that takes in a 2D array as an adjacency matrix and colors the graph based on that adjacency matrix. This file is Color.cpp. I have another program that creates this adjacency matrix and puts it in a text file, this program AdjacencyMatrix.cpp.
When I originally created the coloring program, I hard coded the adjacency matrix into the 2D array graph[V][V] where V is the number of vertices.
These are two separate programs, I was just copying and pasting the adjacency matrix created by AdjacencyMatrix.cpp into Color.cpp.
Because my program already creates a file with the adjacency matrix in it, I want to have my coloring program read that file. I know best practice is to combine them and have the matrix stored in the array passed into the coloring program in one cohesive program. I think reading a file is my simplest solution at this point, but if more experienced users can show me how to store the matrix in a data structure and pass it into the coloring program, I welcome it.
AdjacencyMatrix.cpp
This program takes in a file that is a string of integers listed as adjacent pairs and creates an adjacency matrix from it, then stores it in a file. The file "24cell_skeleton.txt" is the file it reads in and "out.txt" is the file it prints the matrix into.
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
const int cellSize = 24;
bool graph[cellSize][cellSize];
int prevNum = -1;
int currNum = -1;
bool markMatrix(int x, int y) {
graph[x][y] = true;
graph[y][x] = true;
/*std:cout << "adding pair: " << y << "," << x << "\n";*/
return true;
}
int main()
{
ifstream in("C:\\Users\\Austin\\Documents\\adjMatrix\\24cell_skeleton.txt");
ofstream out;
out.open("C:\\Users\\Austin\\Documents\\adjMatrix\\output.txt", ios::out);
ios::out;
string line, field;
vector< vector<string> > array; // the 2D array
vector<string> v; // array of values for one line only
while (getline(in, line)) // get next line in file
{
v.clear();
stringstream ss(line);
while (getline(ss, field, ',')) // break line into comma delimited fields
{
v.push_back(field); // add each field to the 1D array
}
array.push_back(v); // add the 1D array to the 2D array
}
// print out what was read in
bool firstIter = true;
for (size_t i = 0; i<array.size(); ++i)
{
for (size_t j = 0; j<array[i].size(); ++j)
{
string curr = array[i][j]; // (separate fields by |)
prevNum = currNum;
currNum = stoi(curr);
if (j != 0 && firstIter) { //if its not the first iteration . . . or the last?
/*out << "adding pair: " << prevNum << "," << currNum << "\n";*/
markMatrix(prevNum, currNum);
}
}
firstIter = false;
}
in.close();
//std::cout << "{";
for (int i = 1; i <= cellSize; ++i)
{
std::cout << "{";
out << "{";
for (int j = 1; j <= cellSize; ++j)
{
//std::cout << "{";
std::cout << graph[i][j] << ' ';
std::cout << ", ";
out << graph[i][j] << ' ';
out << ", ";
//std::cout << "}";
}
out << "},";
std::cout << "},";
std::cout << std::endl;
}
//std::cout << "}";
out.close();
//cout << graph[534][42];
system("pause");
return 0;
}
Color.cpp
This file colors a graph given an adjacency matrix. Like I mentioned before, the matrix is hard coded into it (copy and pasted from the file the previous program created). This is where I would like to read the file instead of copy and paste it myself.
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <fstream>
#include<stdio.h>
#include<cstdio>
// Number of vertices in the graph
#define V 24
using namespace std;
//this function was added in the update to attempt reading file and storing into a 2d matrix
int createMatrix(int myArray[V][V])
{
ifstream in("C:\\Users\\Austin\\Documents\\adjMatrix\\output.txt");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
in >> myArray[i][j];
}
}
return myArray[V][V];
}
//end of updated code added
void printSolution(int color[]);
/* A utility function to check if the current color assignment
is safe for vertex v */
bool isSafe(int v, bool graph[V][V], int color[], int c)
{
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
/* A recursive utility function to solve m coloring problem */
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)
{
/* base case: If all vertices are assigned a color then
return true */
if (v == V)
return true;
/* Consider this vertex v and try different colors */
for (int c = 1; c <= m; c++)
{
/* Check if assignment of color c to v is fine*/
if (isSafe(v, graph, color, c))
{
color[v] = c;
/* recur to assign colors to rest of the vertices */
if (graphColoringUtil(graph, m, color, v + 1) == true)
return true;
/* If assigning color c doesn't lead to a solution
then remove it */
color[v] = 0;
}
}
/* If no color can be assigned to this vertex then return false */
return false;
}
bool graphColoring(bool graph[V][V], int m)
{
// Initialize all color values as 0. This initialization is needed
// correct functioning of isSafe()
int *color = new int[V];
for (int i = 0; i < V; i++)
color[i] = 0;
// Call graphColoringUtil() for vertex 0
if (graphColoringUtil(graph, m, color, 0) == false)
{
std::cout << "Solution does not exist";
return false;
}
// Print the solution
printSolution(color);
return true;
}
/* A utility function to print solution */
void printSolution(int color[])
{
std::cout << "Solution Exists:"
" Following are the assigned colors \n";
for (int i = 0; i < V; i++)
std::cout << color[i];
std::cout << "\n";
}
// driver program to test above function
int main()
{
/* Create following graph and test whether it is 3 colorable
(3)---(2)
| / |
| / |
| / |
(0)---(1)
*/
bool graph[V][V] = {
{ 0 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , },
{ 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , },
{ 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , },
{ 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , },
{ 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , },
{ 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , },
{ 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , },
{ 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , },
{ 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , },
{ 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , },
{ 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , },
{ 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , },
{ 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , },
{ 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , },
{ 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , },
{ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , },
{ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
{ 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , },
};
int m = 5; // Number of colors
graphColoring(graph, m);
//return 0;
system("pause");
}
Is there a way to take in this matrix from the file rather than hard coding it into the program? The brackets and commas are easy to add or remove from the file. They are necessary when hard coded into the coloring program but I don't think they would be necessary if I could read from the file.
To make this as clear as possible, where you see the 24x24 matrix in Color.cpp, I would like to have that section be a matrix read from out.txt that AdjacencyMatrix.cpp creates.
Edit/Update
I have this so far in the beginning of color.cpp
int createMatrix(int myArray[V][V])
{
ifstream in("C:\\Users\\Austin\\Documents\\adjMatrix\\output.txt");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
in >> myArray[i][j];
}
}
return myArray[V][V];
}
I know something is off here, but if I can get this to work I plan to use something like
bool graph[V][V] =
{
myArray[V][V]
};
in main().
As of now VisualStudio says myArray is an undeclared identifier and is undefined in main().
You are almost there with your createMatrix function, but return myArray[V][V]; not what you want to do. This is saying return a single int that is outside the bounds of the array(Array of size V is valid 0 to V-1. Undefined Behaviour badness will result from breaching the array's bounds.
Fortunately you don't have to return a darn thing. myArray is a pointer to the array that createMatrix was called with (See What is array decaying?) so in >> myArray[i][j]; is reading the file directly into the array.
So with a few checks to make sure the reading succeeded:
bool createMatrix(int myArray[V][V])
{
ifstream in("C:\\Users\\Austin\\Documents\\adjMatrix\\output.txt");
if (in) // if the file is open and readable
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (!(in >> myArray[i][j]))
{ // failed to read a value from the file. Bad file
// may want to log the error here so you know why it failed
return false;
}
}
}
}
else
{ // couldn't open the file
// may want to log the error here so you know why it failed
return false;
}
return true; // read everything we wanted to read. all done.
}
and then in main
int main()
{
int graph[V][V];
if (createMatrix(graph))
{ // read the file successfully
int m = 5; // Number of colors
graphColoring(graph, m);
}
else
{ // did not read the file successfully
// display failure message
}
system("pause");
}