-
Notifications
You must be signed in to change notification settings - Fork 0
/
twoCourteousColoring.m
67 lines (63 loc) · 1.57 KB
/
twoCourteousColoring.m
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
function [set k]=twoCourteousColoring(A)
set=[];
fileID = fopen('twoCourteousColoringRecorder.txt','w');
%set graph g from Matrix A
graph_init;
g=graph;
set_matrix(g,A);
%set link list of g
numNode=nv(g);
elistG=[];
fprintf(fileID,'link list order:\n');
for i=1:1:numNode
elistV=g(i);
ni=length(elistV);
for j=1:1:ni
if elistV(j)>i
elistG=[elistG; [i elistV(j)]];
fprintf(fileID,'\t%d-%d',i,elistV(j));
end
end
end
fprintf(fileID,'\n');
%set vector w
numW=length(elistG);
wVector=zeros(1,numW);
whileFlag=1;
k=0;
tempG=graph;
while ((max(wVector)>=k || whileFlag)&& k<25)
if whileFlag ~= 0
whileFlag=0;
end
k=k+1;
k
fprintf(fileID,'k= %d\n',k);
copy(tempG,g);
tempWVector=ones(1,numW);
%sort vector w[l]
[sortedValueW indexTempW]=sort(wVector,'descend');
for i=1:1:numW
oneW=sortedValueW(i);
oneEdge=elistG(indexTempW(i),:);
%delete link
delete(tempG,oneEdge(1),oneEdge(2));
%check bridge
bridgeTempG=bridges(tempG,'matrix');
[mb nb]=size(bridgeTempG);
if mb==0
tempWVector(indexTempW(i))=0;
fprintf(fileID,'\t deleted link: %d - %d\n',oneEdge(1),oneEdge(2));
else
add(tempG,oneEdge(1),oneEdge(2));
end
end
wVector=wVector+tempWVector;
set=[set;tempWVector];
fprintf(fileID,'\t w Vector:')
fprintf(fileID,'\t %d',wVector');
fprintf(fileID,'\n');
end
free(tempG);
free(g);
fclose(fileID);