-
Notifications
You must be signed in to change notification settings - Fork 0
/
PASS
164 lines (149 loc) · 6.3 KB
/
PASS
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class PASS {
/**
* @param adjMat the adjacency matrix
* @param doneArray the array that contain the actual coloring
* @return the next vertex to color based on our Quai-PASS algorithm.
* it would look for the one with the highest saturation, if there is more than 1 with the same degree of saturation
* it would compare unique colors, if that is also the same it would choose at random between each two.
*/
public static int PASShighestSaturation(int[][] adjMat, int[] doneArray) {
int highestIndex = 0;
int currentHigh = 0;
int connectionCounter = 0;
ArrayList<Integer> amountOfColors = new ArrayList<>();
ArrayList<Integer> amountOfColors2 = new ArrayList<>();
for (int i = 0; i < adjMat.length; i++) {
for (int j = 0; j < adjMat.length; j++) {
if (doneArray[j] != 0) {
if (adjMat[i][j] == 1) {
connectionCounter++;
}
}
}
if (connectionCounter > currentHigh && doneArray[i] == 0 && i != 0) {
currentHigh = connectionCounter;
highestIndex = i;
}
if (connectionCounter == currentHigh && doneArray[i] == 0 && i != 0) {
for (int u = 0; u < adjMat.length; u++) {
if (adjMat[currentHigh][u] == 1 && doneArray[u] != 0) {
amountOfColors.add(doneArray[u]);
}
if (adjMat[highestIndex][u] == 1 && doneArray[u] != 0) {
amountOfColors2.add(doneArray[u]);
}
}
int uniqueColors1 = amountOfColors(amountOfColors);
int uniqueColors2 = amountOfColors(amountOfColors2);
if (uniqueColors1 > uniqueColors2) {
highestIndex = i;
}else if(uniqueColors1 == uniqueColors2){
Random rand= new Random();
int rando = rand.nextInt(2) +1;
if(rando == 1){
highestIndex = i;
}
}
}
connectionCounter = 0;
}
if (highestIndex == 0) {
for(int y=0;y<doneArray.length;y++){
if(doneArray[y] == 0){
highestIndex = y;
return highestIndex;
}
}
}
return highestIndex;
}
/**
* @param colors is an ArrayList that includes all the colors that the vertex is connected to
* @return the amount of unique(different colors)
*/
public static int amountOfColors(ArrayList<Integer> colors) {
int counter = 0;
int amountOfConnections = colors.size();
for (int i = 0; i < colors.size(); i++) {
for (int j = 0; j < colors.size(); j++) {
if (colors.get(i) == colors.get(j)) {
counter++;
}
}
}
amountOfConnections = amountOfConnections - counter;
return amountOfConnections;
}
/**
* @param adjMat the adjacency matrix
* @return a chromatic number
* this only does the Quasi-PASS algorithm once, it will use standard vertex ordering.
*/
public static int PASSchromaticSaturation(int[][] adjMat) {
int[] color = ChromaticMethods.makeColorsArray(adjMat.length);
int[] doneArray = new int[adjMat.length];
ArrayList<Integer> usedArray = new ArrayList<>();
int counter = 0;
while (counter != adjMat.length ) {
if (counter == 0) {
doneArray[counter] = 1;
}
if (counter == 1) {
usedArray.add(counter);
doneArray[counter] = ChromaticMethods.coloringSaturation(color, adjMat, doneArray, counter, usedArray);
} else {
int satuIndex = PASShighestSaturation(adjMat,doneArray);
System.out.println("___________________________________________highest saturation index is " + satuIndex);
usedArray.add(satuIndex);
doneArray[satuIndex] = ChromaticMethods.coloringSaturation(color, adjMat, doneArray, satuIndex, usedArray);
}
counter++;
}
System.out.println(Arrays.toString(doneArray));
return ChromaticMethods.findChromatic(doneArray);
}
/**
* @param adjMat the adjacency matrix
* @return a chromatic number
* this method tries to color the graph using our Quasi-PASS algorithm, which will find which next vertex it should color
* next by analyzing its saturation and the amount of unique colors connected to it.
* it would start coloring in vertex number 2, and in each cycle it would change its starting point by 1.
*/
public static int randomPASS(int[][] adjMat){
int[] color = ChromaticMethods.makeColorsArray(adjMat.length);
int[] doneArray = new int[adjMat.length];
ArrayList<Integer> usedArray = new ArrayList<>();
int vertex = adjMat.length;
int minimumChromatic = vertex;
int counter = 0;
for(int c = 2; c<adjMat.length-1;c++) {
Arrays.fill(doneArray, 0);
counter =0;
usedArray.clear();
while (counter != adjMat.length) {
if (counter == 0) {
doneArray[counter] = 1;
usedArray.add(counter);
}
else if (counter == 1) {
usedArray.add(c);
doneArray[c] = 1;
} else{
int satuIndex = PASShighestSaturation(adjMat, doneArray);
System.out.println("highest PASS index is " + satuIndex);
usedArray.add(satuIndex);
doneArray[satuIndex] = ChromaticMethods.coloringSaturation(color, adjMat, doneArray, satuIndex, usedArray);
}
counter++;
}
int chromaticRandomized = ChromaticMethods.findChromatic(doneArray);
if (chromaticRandomized < minimumChromatic) {
minimumChromatic = chromaticRandomized;
}
}
return minimumChromatic;
}
}