Hello,
First of all this is my first post ever on the forum, so please excuse mistakes that I might've made.
I'm trying to solve the coloring graph problem, everything went well until this happened
Sorry for the huge image.
I believe the problem lies within how the lines are drawn but for the love of my life, I cannot figure it out.
I'm going to show you my codes and I would be happy if you can suggest a more sufficient way to solve this problem or a solution for that would be greatly appreciated, thank you for your time.
My codes are a mess, so sorry about that, I'm still learning.
#include "stdafx.h"
#include <SFML/Graphics.hpp>
#include <iostream>
#include <list>
#include <math.h>
#define PI 3.14159265
using namespace sf;
using namespace std;
struct Coordinates {
float x;
float y;
};
class Graph
{
int V;
public:
list<int> *adj;
Graph(int V) { this->V = V; adj = new list<int>[V]; }
void addEdge(int v, int w);
void greedyColoring(vector <int> &A);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); // Note: the graph is undirected
}
void Graph::greedyColoring(vector <int> &A)
{
vector <int> result(V);
result[0] = 0;
for (int u = 1; u < V; u++)
result[u] = -1;
vector <bool> available(V);
for (int cr = 0; cr < V; cr++)
available[cr] = false;
for (int u = 1; u < V; u++)
{
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (result[*i] != -1)
available[result[*i]] = true;
int cr;
for (cr = 0; cr < V; cr++)
if (available[cr] == false)
break;
result[u] = cr;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (result[*i] != -1)
available[result[*i]] = false;
}
for (int u = 0; u < V; u++)
cout << "Vertex " << u << " ---> Color "
<< result[u] << endl;
for (int i = 0; i < V; i++)
A[i] = result[i];
}
int getDistance(int x, int y)
{
return sqrt(x * x + y * y);
}
float getRotation(float x1, float y1, float x2, float y2)
{
return acos((x1*x2 + y1 * y2) / (getDistance(x1, y1)*getDistance(x2, y2))) * 180 / PI;
}
// Driver program to test above function
int main()
{
int n = 5;
const int N = n;
vector <int> objects(n);
//handle the input
Graph g1(n);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(2, 3);
g1.addEdge(3, 4);
cout << "Coloring of graph 1 \n";
g1.greedyColoring(objects);
//cout << objects[4] << endl;
//result comes here
// create the window
//Use sprite if you want more color
Coordinates boxes[1000];
Color Paint[] = { Color::White, Color::Red, Color::Green, Color::Blue, Color::Yellow ,Color::Magenta ,Color::Cyan,Color::Transparent, };
RenderWindow window(VideoMode(800, 600), "My window");
RectangleShape district[1000];
int i, run[4] = { 1 }; //iterator
// need to update
for (i = 0; i < n; i++) {
district[i].setSize(Vector2f(50, 50));
district[i].setFillColor(Paint[objects[i]]);
if (i <= n / 4) {
district[i].setPosition(0, 100 * i);
boxes[i].x = 0;
boxes[i].y = 100 * i;
}
if (i > n / 4 && i <= n / 2) {
district[i].setPosition(700, 100 * i);
boxes[i].x = 700;
boxes[i].y = 100 * i;
}
if (i > n / 2 && i <= n * 3 / 4) {
district[i].setPosition(i * 100, 0);
boxes[i].x = 100 * i;
boxes[i].y = 500;
}
if (i > n * 3 / 4) {
district[i].setPosition(100 * i, 500);
boxes[i].x = 0;
boxes[i].y = 100 * i;
}
}
// draw the edges
int j = 0; //reset iterator
RectangleShape lines[1000];
for (int x = 0; x < n; x++) {
list<int>::iterator i;
for (i = g1.adj[x].begin(); i != g1.adj[x].end(); ++i)
{
if (x < *i) {
lines[j].setSize(Vector2f(getDistance(boxes[x].x - boxes[*i].x, boxes[x].y - boxes[*i].y), 3));
lines[j].setPosition(boxes[x].x + 25, boxes[x].y + 25);
lines[j].setRotation(getRotation(boxes[x].x - boxes[*i].x, boxes[x].y - boxes[*i].y, 600, 0)); j++;
cout << getRotation(boxes[x].x - boxes[*i].x, boxes[x].y - boxes[*i].y, 600, 0) << endl;
}
}
}
// run the program as long as the window is open
while (window.isOpen())
{
Event event;
while (window.pollEvent(event))
{
//cout << event.type << endl;
if (event.type == Event::Closed)
window.close();
}
// clear the window with black color
window.clear();
// draw everything here...
// window.draw(...);
// end the current frame
for (int i = 0; i < n; i++)
window.draw(district[i]);
for (int i = 0; i < j; i++)
window.draw(lines[i]);
window.display();
}
return 0;
}
