Graph Coloring
This is a real world problem. When designing maps, every region should be painted with different and fewer colors. This method can be used to decide how many different colors will be used.
The Algorithm
Pascal Source Code
Used Variables in program:
A[n,n] : Stores relations between nodes.
C[]: Stores color letters
B[]: Stores colored nodes.
Element 1: 1'rst node
Element 2: 2'nd node
.. ..
S[]:array holds 0(zero)s in every line.
|
k |
Red |
|
m |
Blue |
|
y |
Green |
|
s |
Yellow |
|
t |
Orange |
|
b |
White |
|
f |
|
Program Graf_coloring;
uses crt;
const
c:array[1..7] of char=('k','m','y','s','t','b','f');
var
a:array[1..7,1..7]of integer;
b:array[1..7]of string[5];
s:array[1..7]of integer;
i,j,k,n,r,t,p,f,d:integer; ch:char;
{ "a" relation matrix
"b" colored elements' array
"c" coloring array
"s" array holds 0(zero)s in every line
}
Begin
clrscr;
write('Relation matrix's size:');readln(n);
writeln('Write the relation matrix...');
i:=1;
gotoxy(5,3);
repeat
write(i:4);i:=i+1;
until i=n+1;
for i:=1 to n do
begin
k:=3;
for j:=1 to n do
begin
gotoxy(k+4,i+3);read( a[i,j] );k:=k+4;
end;
end;
t:=0;
for i:=1 to n do
begin {2}
t:=t+1;
f:=0;
j:=i;
if b[i]='' then
begin
while j < n do
begin
if a[i,j]=0 then
begin {1}
k:=1;
if (b[j]='') then k:=n+1;
if k>n then
begin
b[j]:=c[t];{generating coloring array}
if j<>i then
begin
f:=f+1;
s[f]:=j;{ holds 0's place number }
end;
end
else j:=n;
end;{1}
end;
if f<>0 then { controlling matrix and changing colored array'}
begin
for k:=1 to f-1 do
for d:=k+1 to f do
begin
if a[s[k],s[d]]=1 then b[s[d]]:='';
end;
end;
end
else t:=t-1;
end; {2}
writeln('Colored elements and their colors');
for i:=1 to n do
begin
for j:=1 to n do
begin
if b[i]=c[j] then
case j of
1:writeln(i,' ´s color is red');
2:writeln(i,' ´s color is blue');
3:writeln(i,' ´s color is green');
4:writeln(i,' ´s color is yellow');
5:writeln(i,' ´s color is orange');
6:writeln(i,' ´s color is white');
end;
end;
end;
repeat ch:=readkey until ch=#27;
end.
Sample Executions
1)
Relation matrix's
size:7
Write the relation matrix...
1 2 3 4 5 6 7
0 1 1 1 1 0 0
0 0 1 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1
0 0 0 0 0 0 0
Colored elements and their colors
1 ´s color is red
2 ´s color is blue
3 ´s color is green
4 ´s color is yellow
5 ´s color is blue
6 ´s color is red
7 ´s color is orange
2)
Relation matrix's
size:7
Write the relation matrix...
1 2 3 4 5 6 7
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
Colored elements and their colors
1 ´s color is red
2 ´s color is red
3 ´s color is red
4 ´s color is blue
5 ´s color is blue
6 ´s color is blue
7 ´s color is blue