Mdeni Blog: Graph Coloring dalam C#

Dalam Graph Theory, coloring adalah suatu penamaan vertex (node) dengan label yang unik. Tidak ada dua vertex yang dihubungkan oleh sebuah edge memliki label yang sama. ( atau dengan kata lain tidak ada vertex yang bertetangga memilki warna yang sama ). Dalam prakteknya label tersebut berupa warna pada node/vertex yang bersangkutan. Banyaknya warna yang dapat digunakan untuk mewarnai suatu graph dengan jumlah sesedikit mungkin warna yang diperlukan di sebut bilangan chromatic. Dalam gambar di bawah diperlukan 3 warna, maka graph di bawah memiliki chromatic number 3.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacentvertices share the same colorWikipedia………..

Sebuah graph Petersen dapat diwarnai dengan 3 warna saja

Algoritma

Lalu bagaimana cara melakukan pewarnaan tersebut dalam komputer ? yang pertama dilakukan tentunya adalah membuat suatu rangka kerja yang memungkinkan user menggambar line dan node, kemudian semua line dimasukkan dalam suatu List ( sejenis array ) daftarLine dan semua node dalam daftarNode.

Node class

Dalam class node ini yang jelas akan menyimpan variabel nama Vertex dan warna (dalam integer). Dan juga sebuah daftar Node yang terhubung dengan node ini, dalam gambar di atas, Vertex F akan mempunyai daftar yang berisi 3 Node lain ( G,E,dan H). Selain itu, Node juga mempunyai method getColor() untuk mendapatkan warna ( merah, kuning, hijau, … ) tergantung dari variabel warna mereka masing-masing.

Line class

Line class tidak akan dijelaskan terlalau dalam di sini karena yang terdapat dalam class Line hanya berupa variabel yang diperlukan untuk melakukan penggambaran di layar, tidak ada hubungannya dengan algoritma coloring.

Kedua class di atas mampu menggambar diri mereka masing-masing dengan pemanggilan method draw().
Kedua, setelah semuanya siap, sekarang giliran algoritma coloringnya :

Untuk setiap vertex yang terdapat dalam daftarNode, set warnanya dengan melihat daftar node yang terhubung dengan node ini.
Cek semua warna dari node-node itu. Karena label ‘warna’ yang digunakan berupa angka. Maka pilih angka warna paling kecil dan unik dari keseluruhan daftar tersebut.
Ulangi proses ini untuk semua sisa node dalam daftarNode.

Lihat contoh berikut :

Warna 0 berarti node tersebut belum bewarna, pada hasil akhir tidak ada warna 0.
Lantas, bagaimana algoritma fungsi untuk menentukan angka yang dipilih ? Dari ilustrasi tersebut tampak bahwa :

Jika ada daftar angka 0,0,0 maka fungsi mengembalikan angka 1
jika ada daftar angka 0,0,1 maka fungsi mengembalikan angka 2
jika ada daftar angka 0,1,2 maka fungsi mengembalikan angka 3
jika ada daftar angka 2,3,5 maka fungsi mengembalikan angka 4
jika ada daftar angka 1,1,2 maka fungsi mengembalikan angka 3

Kemudian dapat dibuat algoritmanya, berikut yang harus dilakukan :

Buat sebuah fungsi yang mempunyai parameter berupa array angka ( int[] ) dan keluaran berupa sebuah angka
Deklarasikan sebuah variabel integer , bernama x misalkan dan beri nilai 1 pada x
Urutkan angka-angka dalam array tersebut secara ascending dari kecil ke besar
Untuk semua angka dalam array yang bukan angka nol ( for i –> n ) :

jika angka ini sama dengan x maka tambah x dengan 1 ( x++ )
jika angka tidak sama dengan x dan angka tersebut bukanlah angka pertama dalam array ( i > 0 ), maka periksa, apakah angka ini sama atau tidak degan angka sebelumnya dalam array (daftar[i] dengan daftar[i-1]).. Jika tidak sama maka fungsi dihentikan dan kembalikan nilai x sebagai output dari funsgi ( return x)
Sesudah perulangan selesai, kembalikan variabel x sebagai output fungsi ( return x ), apapun nilai dari x, kembalikan.

Dalam C# :

private int SetWarna(int[] daftarWarna)
{
Sort( ref daftarWarna); 
for (int i = 0; i < daftarWarna.Length; i++)
{
 if (daftarWarna[i] != 0) 
 {
   if (daftarWarna[i] == x ) x++; 
   else if (i > 0 &&

daftarWarna[i] != daftarWarna[i - 1])
           {
              return x;// return warna
           }
 }
}
return x;
}

Sekarang, mari kita lihat apa yang sebenarnya dilakukan oleh algoritma ini : Misalkan fungsi tersebut mendapatkan array berisi angka 0,1,1,2,3,5 maka fungsi ini harus mengembalikan nilai 4 karena 4 adalah nilai terkecil dan terunik dalam daftar tersebut