3
I will use standard library vectors and implement simple map coloring algorithm. The goal of a map coloring problem is to color a map so that regions sharing a common border have different colors
In C++ I can represent the neighboring information using a 2D vector of booleans. For example, consider the following 2D neighbor vector:
Countries 1 2 3 4
1 - T F T
2 T - F F
3 F F - T
4 T F T -
The countries 1 and 2 are neighbors. The countries 1 and 3 are not neighbors. Note that the 2D vector is symmetric
I write a C++ class with a constructor that takes the number of countries and a vector of available colors represented by strings (“red”, “blue”, “green”, etc.). The constructor builds a private random neighboring 2D vector.
I override the constructor with a function that takes a neighbor vector and a vector of available colors
I write a member function that accepts a vector of available colors
I write a member function that accepts a 2D neighboring vector
I write a member function named mapColor that assigns colors to countries. If the coloring is successful, it prints the country colors. Otherwise, it gives an error message. For example, for the above neighbor vector the output would be
Country 1 (red),
Country 2 (blue),
Country 3 (blue)
Country 4 (red).
I write some code but it is not run:S
MY CODE :
Expand|Select|Wrap|Line Numbers
- #include<iostream>// allows program to output data to the screen
- using std::cout;// program uses cout
- using std::cin;// program uses cin
- using std::endl;//program uses endl
- // contains prototypes for functions srand and rand
- #include<cstdlib>
- //contains prototypes for function time
- #include<ctime>
- #include "dosya_1.h"// include definition of class Country
- // constructor takes the number of countries and a vector of available colors represented by strings
- Country::Country(vector<char> &v_c_array,int number)
- {
- vector<vector<bool> > v_2x_array;
- set_function_number_country(number);
- accept_vector_color(v_c_array);
- accept_2D_neighboring_vector(v_2x_array);
- }//end Country constructor
- Country::Country(vector<char> &a,vector<vector<char> &b)
- {
- accept_vector_color();
- b(country_number,v_color_array);
- for (int i=0; i<b.size(); ++i)
- for (int j=0; j<b[i].size(); ++j)
- b[i][j] = v_2d_neighbor[i][j];
- }
- void Country::accept_vector_color(vector<char> &v_c_array)
- {
- for(int i=0; i<country_number; ++i)
- v_color_array[i] = v_c_array[i];
- }
- void Country::accept_2D_neighboring_vector(vector<vector<bool> > &v_2D_neighbor)
- {
- int x;
- srand(time(0));
- for (int i=0; i<b.size(); ++i)
- for (int j=0; j<b[i].size(); ++j)
- v_2D_neighbor[i][j] = v_2d_neighbor[i][j];
- for (int i=0; i<v_2D_neighbor.size(); ++i)
- for (int j=0; j<v_2D_neighbor[i].size(); ++j)
- {
- x = rand()%10 + 1;
- if(i == j)
- continue;
- else if(x = 1)
- v_2D_neighbor[i][j] = true;
- else
- v_2D_neighbor[i][j] = false;
- }
- }
- void Country::set_function_number_country(int f_number)
- {
- country_number = f_number;
- }
- void mapColor()
- {
- char country[country_number];
- for (int i=0; i<v_2d_neighbor.size(); ++i)
- {
- for (int j=0; j<v_2d_neighbor[i].size(); ++j)
- {
- if(i == j)
- continue;
- else if(v_2d_neighbor[i][j])
- {
- country[i] = v_color_array[0];
- country[j] = v_color_array[1];
- }
- else
- {
- country[i] = v_color_array[0];
- country[j] = v_color_array[0];
- }
- }
- }
- for(int k=0; k<country_number; ++k)
- cout << "country(" << k << ") " << country[k] << "\n";
- }
- and MY HEADER :
- #include <vector>
- using std::vector;
- class Country{
- public:
- Country(vector<char>&,int);
- Country(vector<char>&,vector<vector<bool> >&);
- void set_function_number_country(int);
- void accept_vector_color(vector<char> &);
- void accept_2D_neighboring_vector();
- void mapColor();
- int find_minimum_number_of_colors();
- private:
- int country_number;
- vector<char> v_color_array(4);
- vector<vector<bool> > v_2d_neighbor();
- };
REGARDS..
