Messages

1

General / Re: The coloring graph problem.

« on: May 25, 2018, 04:00:07 pm »

Gods bless you !! ^^

2

General / Re: The coloring graph problem.

« on: May 25, 2018, 03:03:16 pm »

Well,  my teacher is pretty busy so I do not think he will answer to my questions. And drawing lines was my issue. I have not found any solutions for drawing lines so far. So if you know any solutions, please help me out!
Anyway , Its been a pleasure for me since your first reply to my problem .

3

General / Re: The coloring graph problem.

« on: May 25, 2018, 01:51:30 pm »

https://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/

I am having a project in my school and it is graph coloring. I was trying to draw lines to show the connections in the graph. And I can not find a solution to connect the boxes by drawing the lines. ((

4

General / The coloring graph problem.

« on: May 25, 2018, 01:11:12 pm »

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;
}