sith/graphcoloring.cpp at master · ajnovice/sith · GitHub

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include "graphcoloring.h"
#include <QDebug>
#include <QVector>

void graphColoring::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}

QVector <int> graphColoring::greedyColoring()
{

    // Assign the first color to first vertex
    color.push_back(0);

    qDebug() << "Reached till here!";
    // Initialize remaining V-1 vertices as unassigned
    for (int u = 1; u < V; u++)
        color.push_back(-1);  // no color is assigned to u


    // A temporary array to store the available colors. True
    // value of available[cr] would mean that the color cr is
    // assigned to one of its adjacent vertices
    bool available[V];
    for (int cr = 0; cr < V; cr++)
        available[cr] = false;

    // Assign colors to remaining V-1 vertices
    for (int u = 1; u < V; u++)
    {
        // Process all adjacent vertices and flag their colors
        // as unavailable
        QList<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            if (color[*i] != -1)
            {
                available[color[*i]] = true;
            }
        }

        // Find the first available color
        int cr;
        for (cr = 0; cr < V; cr++)
        {
            if (available[cr] == false)
            {
                break;
            }
        }

        color[u] = cr; // Assign the found color

        // Reset the values back to false for the next iteration
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            if (color[*i] != -1)
            {
                available[color[*i]] = false;
            }
        }
    }

    // print the color
    for (int u = 0; u < V; u++)
    {
        qDebug() << "Vertex " << u << " --->  Color " << color[u] << endl;
    }
    return color;
}

QVector<int> graphColoring::sortMessages(int nVertices, QVector<int> input)
{
    int repitition[nVertices];
    int temp, pos, i;
    //initialize repitition to 0
    for (i = 0 ; i < nVertices ; i++ )
    {
        repitition[i] = 0;
    }

    //filling repitition with data from QVector input
    for (i = 0 ; i < nVertices ; i ++ )
    {
        temp = input[i];
        repitition[temp] = repitition[temp] + 1;
    }

    //finding max in repitition
    temp = repitition[0];
    pos = 0;
    for (i = 0 ; i < nVertices ; i++)
    {
        if (repitition[i] > temp)
        {
            temp = repitition[i];
            pos = i;
        }
    }

    //now swapping 0 with the number having highest value
    //Step 1. Swap "pos" in QVector with "nVertices"
    for (i = 0 ; i < nVertices ; i ++)
    {
        if (input[i] == pos)
        {
            input[i] = nVertices;
        }
    }
    //Step 2. Swap "0" in QVector with pos
    for (i = 0 ; i < nVertices ; i ++ )
    {
        if (input[i] == 0)
        {
            input[i] = pos;
        }
    }
    //Step 3. Swap "nVertices" in QVector with "0"
    for (i = 0 ; i < nVertices ; i ++ )
    {
        if (input[i] == nVertices)
        {
            input[i] = 0;
        }
    }
    return input;

}

int graphColoring::messageCount(int nVertices, QVector<int> input)
{
    int i;
    int max = 0;
    for (i = 0; i < nVertices; i++ )
    {
        if (input[i] > max)
        {
            max = input[i];
        }
    }
    max += 1;
    return max;
}