Coloring a Map

[crimsonzero2]

I have this assignment where I have a map of counties and I have to color each county different from its neighbors. I have the code that can compile, but throws a bad_alloc argument. Here's the code:

Map.hpp
#ifndef MAP_HPP_INCLUDED
#define MAP_HPP_INCLUDED

#include<string>
#include<vector>

using namespace std;

class Map
{
    //TODO add a private variable color to keep up with the regions colors
    private:
        vector<string> regions;
        vector<vector<int> > borders;
        //vector<int> region_color;
    public:
        Map(vector<string> regions, vector<vector<string> > borders);
        vector<string> getRegions();
        int countConflicts(/*int colors[]*/vector<int> colors);
        int countConflicts(/*int colors[]*/vector<int> colors, string region);
        //void changeColor(int new_color, int space);
        //vector<int> Cregions();
};

/*
    regions is the list of regions
    borders is the matrix of borders
    for every regions[i], borders[i] would hold all regions that border regions[i]
*/
Map::Map(vector<string> Regions, vector<vector<string> > borders)
{
    //adding the list of regions into the regions within class Map
    this->regions = Regions;// = regions;
    //this->borders = regions.size();

    for(unsigned int i = 0; i < regions.size(); i++)
    {
        //gets the neighbors of regions[i]
        //string neighborNames[] = borders[i];
        vector<string> neighborNames;
        neighborNames = borders[i];

        /*
            used to hold the index within the list of regions
            these will be the neighbors of regions[i]
        */
        //int neighbors[neighborNames.size()];
        vector<int> neighbors;

        //this will hold all the neighbors of regions[i] in int form
        for(unsigned int j = 0; j < neighborNames.size(); j++)
        {

            //returns the index within the list
            //neighbors[j] = Arrays.asList(regions).indexOf(neighborNames[j]);
            for(unsigned int k = 0; k < regions.size(); k++)
            {
                //comparing if regions[k] name is the same as the neighborNames[j]
                //store it into the list of neighbors if so
                if(regions[k] == neighborNames[j])
                {
                    neighbors.push_back(k);
                    break;
                }
            }
        }

        //add the list of neighbors into the matrix of borders
        this->borders.push_back(neighbors);
        //this->region_color.push_back(0);
    }
}

vector<string> Map::getRegions()
{
    return regions;
}

int Map::countConflicts(/*int colors[]*/vector<int> colors)
{
    int nConflicts = 0;
    for(unsigned int i = 0; i < regions.size(); i++)
    {
        nConflicts += countConflicts(colors, regions[i]);
    }
    return nConflicts/2;
}

int Map::countConflicts(/*int colors[]*/vector<int> colors, string region)
{
    int nConflicts = 0;
    int regionNumber;
    //int regionNumber = Arrays.asList(regions).indexOf(region);
    for(unsigned int j = 0; j < regions.size(); j++)
    {
        if(regions[j] == region)
        {
            regionNumber = j;
            break;
        }
    }
    //int neighbors[] = borders[regionNumber];
    vector<int> neighbors;

    //adds the list of neighbors from border into neighbors
    neighbors = borders[regionNumber];

    for(unsigned int i = 0; i < neighbors.size(); i++)
    {
        //compare the region's color to its neighbors' colors
        if(colors[regionNumber] == colors[neighbors[i]] && colors[regionNumber] != 0)
        {
            nConflicts++;
        }
    }
    return nConflicts;
}
/*
void Map::changeColor(int new_color, int space)
{
    this->region_color.at(space) = new_color;
}
*/
/*
vector<int> Map::Cregions()
{
    return this->region_color;
}
*/
#endif // MAP_HPP_INCLUDED

Backtrack.hpp
#ifndef BACKTRACK_HPP_INCLUDED
#define BACKTRACK_HPP_INCLUDED

#include<vector>

#include "Map.hpp"

using namespace std;

class Backtrack
{
    public:
        vector<int> Search(Map Mmap, int nColors);
        vector<int> Search(Map Mmap, vector<int> colors, int nColors);
};

vector<int> Backtrack::Search(Map Mmap, int nColors)
{
    //int colors[Mmap.getRegions().size()];
    int region_size = Mmap.getRegions().size();
    vector<int> colors;
    colors.resize(region_size, 0);
    return Search(Mmap, colors, nColors);
}

/*
    vector<int> colors is a list that correspond with the region list
*/
vector<int> Backtrack::Search(Map Mmap, vector<int> colors, int nColors)
{
    //picks an uncolored region
    //string uncolored_region;
    //vector<int> colored_regions = colors;
    int region_index;
    for(unsigned int r = 0; r < colors.size(); r++)
    {
        if (colors.at(r) == 0)
            region_index = r;
            break;
    }
    //vector<string> regions = Mmap.getRegions();
    //uncolored_region = regions[region_index];

    //loops over all possible colors

        for(int j = 1; j <= nColors; j++)
        {
            //color uncolor region with color i
        //Mmap.changeColor(j, i);
        colors.at(region_index) = j;

        //test if there are any conflicts
        int conflicts = Mmap.countConflicts(colors);

        //if so continue loop
        if(conflicts != 0)
            continue;
        else
        {
            Search(Mmap, colors, nColors);
            return colors;
        }
        //if not call Backtrack recursively
        }

    //return failure
    vector<int> fail;
    fail.push_back(-1);
    return fail;
}

#endif // BACKTRACK_HPP_INCLUDED

MinConflicts.hpp
#ifndef MINCONFLICTS_HPP_INCLUDED
#define MINCONFLICTS_HPP_INCLUDED

#include<stdlib.h>
#include<vector>

#include "Map.hpp"

using namespace std;

class MinConflicts
{
    public:
        vector<int> Search(Map Mmap, int nColors, int maxSteps);

        //method to pick a random integer
        int Random_color();
        int Random_region(Map Mmap);

        //method to return index of array with smallest value(tiebreaks done at random)
        int Index(vector<int> ConflictList, int smallestConflict);
};

vector<int> MinConflicts::Search(Map Mmap, int ncolors, int maxSteps)
{
    //color map randomly
    //int colors[Mmap.getRegions().size()];
    vector<int> colors;
    for(unsigned int i = 0; i < Mmap.getRegions().size(); i++)
    {
        //colors[i] = new random color
        colors.push_back(Random_color());
        //Mmap.changeColor(i, Random_color());
    }
    vector<int> conflicts;
    for(int i = 0; i <= maxSteps - 1; i++)
    {
        int random_region = Random_region(Mmap);
        for(int j = 1; j <= ncolors; j++)
        {
            //Mmap.changeColor(random_region, j);
            colors.at(random_region) = j;
            conflicts.push_back(Mmap.countConflicts(colors));
        }
        int smallest_conflict = conflicts.at(0);
        for(unsigned int k = 1; k < conflicts.size(); k++)
        {
            if(conflicts.at(k) < smallest_conflict)
            {
                smallest_conflict = conflicts.at(k);
            }
        }
        int index_of_smallest = Index(conflicts, smallest_conflict);
        //Mmap.changeColor(random_region, index_of_smallest);
        colors.at(random_region) = index_of_smallest;

        if(Mmap.countConflicts(colors) == 0)
        {
            return colors;
        }

    }
    //next 3 steps inside a loop that run from 0 to maxSteps - 1:
    //pick a random region
    //try all possible colors, pick the one that gives the fewest conflicts
    //check for a solution if so return it if not continue loop
}

int MinConflicts::Random_color()
{
    return rand() % 4 + 1;
}

int MinConflicts::Random_region(Map Mmap)
{
    int region = Mmap.getRegions().size();
    return rand() % region + 1;
}

int MinConflicts::Index(vector<int> ConflictList, int smallestConflict)
{
    for(unsigned int i = 0; i < ConflictList.size(); i++)
    {
        if(ConflictList.at(i) == smallestConflict)
        {
            return i;
        }
    }
}


#endif // MINCONFLICTS_HPP_INCLUDED 

[crimsonzero2]

main.cpp
#include <iostream>
#include <string>
#include <vector>

#include "Map.hpp"
#include "Backtrack.hpp"
#include "MinConflicts.hpp"
using namespace std;

Map Vermont()
{
    string grandIsle = "Grand Isle";
    string franklin = "Franklin";
    string orleans = "Orleans";
    string essex = "Essex";
    string chittenden = "Chittenden";
    string lamoille = "Lamoille";
    string caledonia = "Caledonia";
    string addison = "Addison";
    string washington = "Washington";
    string orange = "Orange";
    string rutland = "Rutland";
    string windsor = "Windsor";
    string bennington = "Bennington";
    string windham = "Windham";

    vector<string> grandIsleNeighbors = { franklin, chittenden };
    vector<string> franklinNeighbors = { grandIsle, chittenden, lamoille, orleans };
    vector<string> orleansNeighbors = { franklin, lamoille, caledonia, essex };
    vector<string> essexNeighbors = { orleans, caledonia };
    vector<string> chittendenNeighbors = { grandIsle, franklin, lamoille, washington, addison };
    vector<string> lamoilleNeighbors = { franklin, orleans, caledonia, washington, chittenden };
    vector<string> caledoniaNeighbors = { orleans, essex, orange, washington,	lamoille };
    vector<string> addisonNeighbors = { chittenden, washington, orange, windsor, rutland };
    vector<string> washingtonNeighbors = { lamoille, caledonia, orange, addison, chittenden };
    vector<string> orangeNeighbors = { washington, caledonia, windsor, addison };
    vector<string> rutlandNeighbors = { addison, windsor, bennington };
    vector<string> windsorNeighbors = { addison, orange, rutland, windham };
    vector<string> benningtonNeighbors = { rutland, windsor, windham };
    vector<string> windhamNeighbors = { windsor, bennington };

    vector<string> counties = {grandIsle, franklin, orleans, essex, chittenden,
                                lamoille, caledonia, addison, washington, orange,
                                rutland, windsor, bennington, windham};

    vector<vector<string> > neighbors;
    neighbors.push_back(grandIsleNeighbors);
    neighbors.push_back(franklinNeighbors);
    neighbors.push_back(orleansNeighbors);
    neighbors.push_back(essexNeighbors);
    neighbors.push_back(chittendenNeighbors);
    neighbors.push_back(addisonNeighbors);
    neighbors.push_back(washingtonNeighbors);
    neighbors.push_back(orangeNeighbors);
    neighbors.push_back(rutlandNeighbors);
    neighbors.push_back(windsorNeighbors);
    neighbors.push_back(benningtonNeighbors);
    neighbors.push_back(windhamNeighbors);

    return Map(counties, neighbors);
}

int main()
{
    Map Vermont_counties = Vermont();
    int nColors = 4;
    int maxSteps = 10000;
    //Backtrack b;
    vector<int> result;
    //result = b.Search(Vermont_counties, nColors);
    return 0;
}

I don't know what else to do. I am completely lost at this point.

[JLBorges]

std::bad_alloc is thrown when we run out of available memory. Brute-force search for a 4-coloring of a non-trivial graph leads to a combinatorial explosion. (In our case, 4¹⁴ == 268435456)

A map coloring problem can be solved by first converting the map into a graph where each region is a vertex and an edge connects two vertices if and only if the corresponding regions share a border. Once a map is converted into a graph, a process called vertex coloring can be used to decide how the map should be colored. - http://www.ctl.ua.edu/math103/mapcolor/mapcolor.htm

Once we have formed the graph, a simple vertex colouring algorithm is greedy colouring: http://en.wikipedia.org/wiki/Greedy_coloring

[crimsonzero2]

In the program, Map.hpp holds a vector of strings where each place in memory is one region, and the borders is suppose to hold the index location of each region within that vector of regions for each one of a region's neighbor. Then the backtracking function is suppose to output a vector of int that holds the color for each region.

[crimsonzero2]

Ok, I freed up the memory. Now I can't get the Backtrack to work. Any one knows why?

[crimsonzero2]

I realized that my border matrix in Map.hpp is putting in wrong data.

[JLBorges]

Why do you need to backtrack?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <vector> #include <map> #include <string> #include <iostream> #include <set> #include <algorithm> #include <iterator> int main() { const std::vector<std::string> counties = { "grandIsle", "franklin", "orleans", "essex", "chittenden", "lamoille", "caledonia", "addison", "washington", "orange", "rutland", "windsor", "bennington", "windham" }; const std::vector< std::vector<std::string> > neighbours = { { "franklin", "chittenden" }, { "grandIsle", "chittenden", "lamoille", "orleans" }, { "franklin", "lamoille", "caledonia", "essex" }, { "orleans", "caledonia" }, { "grandIsle", "franklin", "lamoille", "washington", "addison" }, { "franklin", "orleans", "caledonia", "washington", "chittenden" }, { "orleans", "essex", "orange", "washington", "lamoille" }, { "chittenden", "washington", "orange", "windsor", "rutland" }, { "lamoille", "caledonia", "orange", "addison", "chittenden" }, { "washington", "caledonia", "windsor", "addison" }, { "addison", "windsor", "bennington" }, { "addison", "orange", "rutland", "windham" }, { "rutland", "windsor", "windham" }, { "windsor", "bennington" } }; const std::set< std::string > colours = { "1RED", "2GREEN", "3BLUE", "4YELLOW", "5MAGENTA", "6CYAN", "7WHITE", "8BLACK", "9zzzz" // "9zzzz" == unassigned }; // colours are 1, 2, 3, ... n std::vector<std::string> county_colours( counties.size(), "9zzzz" ) ; // initially unassigned // greedy for( std::size_t i = 0 ; i < counties.size() ; ++i ) { const std::vector<std::string>& adjacent_counties = neighbours[i] ; std::set<std::string> unavailable_colours ; for( const std::string& county : adjacent_counties ) { auto pos = std::find( counties.begin(), counties.end(), county ) - counties.begin() ; unavailable_colours.insert( county_colours[pos] ) ; } std::vector< std::string > possible_colours ; std::set_difference( colours.begin(), colours.end(), unavailable_colours.begin(), unavailable_colours.end(), std::back_inserter(possible_colours) ) ; county_colours[i] = possible_colours.front() ; // pick the first possible colour std::cout << counties[i] << " - " << county_colours[i].substr(1) << '\n' ; } }

grandIsle - RED franklin - GREEN orleans - RED essex - GREEN chittenden - BLUE lamoille - YELLOW caledonia - BLUE addison - RED washington - GREEN orange - YELLOW rutland - GREEN windsor - BLUE bennington - RED windham - GREEN

http://coliru.stacked-crooked.com/a/070439bbd92d4a9c

[crimsonzero2]

I need Backtrack because it's part of the assignment that I was told. It was originally suppose to be done in Java, but since I'm not all too good with Java, I went and convert it to c++ which the professor allows anyone to do with the code. Right now I realize that the recursion causes and infinite loop.

[crimsonzero2]

UPDATE: I got it to show the right answer through novice debugging, but I can't get it to stop when it should.

#ifndef BACKTRACK_HPP_INCLUDED
#define BACKTRACK_HPP_INCLUDED

#include<vector>

#include "Map.hpp"

using namespace std;

class Backtrack
{
    public:
        vector<int> Search(Map Mmap, int nColors);
        vector<int> Search(Map Mmap, vector<int> colors, int nColors);
};

vector<int> Backtrack::Search(Map Mmap, int nColors)
{
    int size_of_map = Mmap.getRegions().size();
    vector<int> colors;
    colors.resize(size_of_map);
    for(int i = 0; i < colors.size(); i++)
    {
        colors[i] = 0;
    }
    return Search(Mmap, colors, nColors);
}

/*
    vector<int> colors is a list that correspond with the region list
*/
vector<int> Backtrack::Search(Map Mmap, vector<int> colors, int nColors)
{
    int uncolored_region;
    for(unsigned int i = 0; i < colors.size(); i++)
    {
        cout << "the number in colors[" << i << "] is " << colors[i] << endl;
        if(colors[i] == 0)
        {
            cout << "number i is " << i << endl;
            uncolored_region = i;
            break;
        }
    }
    cout << "I found the uncolored region at " << uncolored_region << endl;

    for(int j = 1; j <= nColors; j++)
    {
        colors[uncolored_region] = j;
        int conflicts = Mmap.countConflicts(colors);
        cout << "I've done the conflicts" << endl;
        if(conflicts != 0)
        {
            cout << "I found a conflict" << endl;
            continue;
        }
        else
        {
            cout << "Doing the recursion" << endl;
            return Search(Mmap, colors, nColors);
        }
    }
    cout << "I'm going to return fail" << endl;
    vector<int> fail;
    fail.push_back(-1);
    cout << "I returned fail" << endl;
    return fail;
}

#endif // BACKTRACK_HPP_INCLUDED

[JLBorges]

vector<int> Backtrack::Search(Map Mmap, vector<int> colors, int nColors)
{
     if( std::find( colors.begin(), colors.end(), 0 ) == colors.end() )
     {
           // all regions have been coloured
           std::cout << "we are done\n" ;
           return colors ;
     }   

     // ....

 }

[crimsonzero2]

Wouldn't find have an issue regarding the last element? In the documentation it states that it includes the first and ends before the last *[first,last)*.

[crimsonzero2]

Anyways, now I'm having an issue with the MinConflicts.hpp file. It throws an out of range error. Anyone knows why?

#ifndef MINCONFLICTS_HPP_INCLUDED
#define MINCONFLICTS_HPP_INCLUDED

#include<stdlib.h>
#include<vector>

#include "Map.hpp"

using namespace std;

class MinConflicts
{
    public:
        vector<int> Search(Map Mmap, int nColors, int maxSteps);

        //method to pick a random integer
        int Random_color();
        int Random_region(Map Mmap);

        //method to return index of array with smallest value(tiebreaks done at random)
        int Index(vector<int> ConflictList, int smallestConflict);
};

vector<int> MinConflicts::Search(Map Mmap, int nColors, int maxSteps)
{
    //color map randomly
    //int colors[Mmap.getRegions().size()];
    vector<int> colors;
    for(unsigned int i = 0; i < Mmap.getRegions().size(); i++)
    {
        //colors[i] = new random color
        //cout << "pushing random color into region[" << i << "]" << endl;
        colors.push_back(Random_color());
        //Mmap.changeColor(i, Random_color());
    }
    vector<int> conflicts;
    for(int i = 0; i <= maxSteps - 1; i++)
    {
        int random_region = Random_region(Mmap);
        for(int j = 1; j <= nColors; j++)
        {
            //Mmap.changeColor(random_region, j);
            //cout << "changing color[" << random_region << "] to " << j << endl;
            colors[random_region] = j;
            conflicts.push_back(Mmap.countConflicts(colors));
            //cout << "pushback the conflict into the array of conflicts" << endl;
        }
        int smallest_conflict = conflicts[0];
        for(unsigned int k = 1; k < conflicts.size(); k++)
        {
            if(conflicts[k] < smallest_conflict)
            {
                smallest_conflict = conflicts[k];
            }
        }
        int index_of_smallest = Index(conflicts, smallest_conflict);
        //Mmap.changeColor(random_region, index_of_smallest);
        colors[random_region] = index_of_smallest;
        //cout << "set the new color with lowest conflict" << endl;

        conflicts.clear();
        vector<int>(conflicts).swap(conflicts);

        if(Mmap.countConflicts(colors) == 0)
        {
            /*
            for(int i = 0; i < colors.size(); i++)
            {
                cout << "color[" << i << "] = " << colors[i] << endl;
            }
            */
            return colors;
        }

    }
    //next 3 steps inside a loop that run from 0 to maxSteps - 1:
    //pick a random region
    //try all possible colors, pick the one that gives the fewest conflicts
    //check for a solution if so return it if not continue loop
}

int MinConflicts::Random_color()
{
    return rand() % 4 + 1;
}

int MinConflicts::Random_region(Map Mmap)
{
    int region = Mmap.getRegions().size();
    return rand() % region;
}

int MinConflicts::Index(vector<int> ConflictList, int smallestConflict)
{
    for(unsigned int i = 0; i < ConflictList.size(); i++)
    {
        if(ConflictList[i] == smallestConflict)
        {
            return i;
        }
    }
}


#endif // MINCONFLICTS_HPP_INCLUDED

It shouldn't get an output like this:

11111111111111

[JLBorges]

> Wouldn't find have an issue regarding the last element?
> In the documentation it states that it includes the first and ends before the last *[first,last)*.

See: http://en.cppreference.com/w/cpp/container/vector/end


> It throws an out of range error. Anyone knows why?

colors.at(random_region) will throw if random_region >= colours.size()

conflicts.at(0) will throw if conflicts.empty()

[crimsonzero2]

I actually figured the issue with that out. I'm now trying to get MinConflicts to output a result that creates no conflicts. Even though it's suppose to be random in choosing the region and getting the color with the lowest amount of conflicts with it, I end up getting the same result. And I just checked to make sure my if statement was running or not and it wasn't.
Here's my up-to-date code on it:

#ifndef MINCONFLICTS_HPP_INCLUDED
#define MINCONFLICTS_HPP_INCLUDED

#include<stdlib.h>
#include<vector>

#include "Map.hpp"

using namespace std;

class MinConflicts
{
    public:
        vector<int> Search(Map Mmap, int nColors, int maxSteps);

        //method to pick a random integer
        int Random_color();
        int Random_region(Map Mmap);

        //method to return index of array with smallest value(tiebreaks done at random)
        int Index(vector<int> ConflictList, int smallestConflict);
};

vector<int> MinConflicts::Search(Map Mmap, int nColors, int maxSteps)
{
    //color map randomly
    //int colors[Mmap.getRegions().size()];
    vector<int> colors;
    for(unsigned int i = 0; i < Mmap.getRegions().size(); i++)
    {
        //colors[i] = new random color
        //cout << "pushing random color into region[" << i << "]" << endl;
        colors.push_back(Random_color());
        //Mmap.changeColor(i, Random_color());
    }
    vector<int> conflicts;
    for(int i = 0; i <= maxSteps - 1; i++)
    {
        int random_region = Random_region(Mmap);
        for(int j = 1; j <= nColors; j++)
        {
            //Mmap.changeColor(random_region, j);
            //cout << "changing color[" << random_region << "] to " << j << endl;
            colors[random_region] = j;
            conflicts.push_back(Mmap.countConflicts(colors));
            //cout << "pushback the conflict into the array of conflicts" << endl;
        }
        /*
        for(int i = 0; i < conflicts.size(); i++)
        {
            cout << "the number of conflicts for color " << i + 1 << " is: " << conflicts[i] << endl;
        }
        */
        int smallest_conflict = conflicts[0];
        for(unsigned int k = 1; k < conflicts.size(); k++)
        {
            if(conflicts[k] < smallest_conflict)
            {
                smallest_conflict = conflicts[k];
            }
        }
        //cout << "smallest conflict is: " << smallest_conflict << endl;
        int index_of_smallest = Index(conflicts, smallest_conflict);
        //cout << "index of the smallest conflict is: " << index_of_smallest << endl;
        //Mmap.changeColor(random_region, index_of_smallest);
        colors[random_region] = index_of_smallest + 1;
        //cout << "set the new color with lowest conflict" << endl;

        conflicts.clear();
        vector<int>(conflicts).swap(conflicts);

        if(Mmap.countConflicts(colors) == 0)
        {
            cout << "found solution: " << endl;
            for(int i = 0; i < colors.size(); i++)
            {
                cout << "color[" << i << "] = " << colors[i] << endl;
            }

            return colors;
        }

    }
    //next 3 steps inside a loop that run from 0 to maxSteps - 1:
    //pick a random region
    //try all possible colors, pick the one that gives the fewest conflicts
    //check for a solution if so return it if not continue loop
}

int MinConflicts::Random_color()
{
    return rand() % 4 + 1;
}

int MinConflicts::Random_region(Map Mmap)
{
    int region = Mmap.getRegions().size();
    return rand() % region;
}

int MinConflicts::Index(vector<int> ConflictList, int smallestConflict)
{
    vector<int> answers;
    for(unsigned int i = 0; i < ConflictList.size(); i++)
    {
        if(ConflictList[i] == smallestConflict)
        {
            answers.push_back(i);
        }
    }
    int answer = rand() % answers.size();
    return answer;
}


#endif // MINCONFLICTS_HPP_INCLUDED