Algoritma Graph Coloring

Algoritma Graph Coloring adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah menentukan penjadwalan mata kuliah sederhana.

Diasumsikan ada 4 slot waktu yang tersedia, yaitu slot S1, S2, S3, S4
dan ada 3 ruang yang tersedia, yaitu R1, R2, R3
Berapa mata kuliah yang dapat dimasukkan seminimal mungkin dan memenuhi syarat berikut:
– Tidak ada mata kuliah yang diajarkan pada slot waktu yang sama
– Tidak ada mata kuliah yang diajarkan pada ruang yang sama

Jika diilustrasikan dalam tabel, maka model penjadwalan adalah sebagai berikut

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
Tentukan jumlah titik yang digunakan
Diasumsikan dalam kasus ini, jumlah titik adalah 4 slot waktu * 3 ruang = 12

Const jumlahTitik As Integer = 12

Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi semua variabel yang diperlukan, yaitu variabel gambar, titik, dan garis
Penjelasan tentang masing-masing class akan dijelaskan pada skrip dibawah ini

Console.WriteLine("Masukkan kata yang akan dicari usulannya: ")
Dim gmb As New Gambar(jumlahTitik)
Dim daftarTitik As List(Of Titik) = gmb.daftarTitik
Dim daftarGaris As New List(Of Garis)()
Dim grs As Garis

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah 4 buah class
Class Titik digunakan untuk menampung data indeks, jumlah tetangga, dan warna titik tersebut
Class Garis digunakan untuk menampung data titik awal, dan titik tujuan garis tersebut
Class Gambar digunakan untuk menampung semua data titik dan semua data garis yang digunakan
Deklarasi masing-masing class adalah sebagai berikut:

Public Class Gambar
    Public daftarTitik As List(Of Titik) = Nothing
    Public daftarGaris As List(Of Garis) = Nothing

    Public Sub New(jumlahTitik As Integer)
        daftarTitik = New List(Of Titik)
        For i As Integer = 0 To jumlahTitik - 1
            daftarTitik.Add(New Titik(i))
        Next
    End Sub
End Class

Public Class Garis
    Private m_titikAwal As Titik
    Private m_titikTujuan As Titik

    Public Property titikAwal() As Titik
        Get
            Return m_titikAwal
        End Get
        Set(value As Titik)
            m_titikAwal = value
        End Set
    End Property

    Public Property titikTujuan() As Titik
        Get
            Return m_titikTujuan
        End Get
        Set(value As Titik)
            m_titikTujuan = value
        End Set
    End Property

    Public Sub New(titikAwal As Titik, titikTujuan As Titik)
        m_titikAwal = titikAwal
        m_titikTujuan = titikTujuan
    End Sub
End Class

Public Class Titik
    Private m_Idx As String
    Private m_jumlahTitikTetangga As Integer
    Private m_warna As String

    Public Property Idx() As String
        Get
            Return m_Idx
        End Get
        Set(value As String)
            m_Idx = value
        End Set
    End Property

    Public Property JumlahTitikTetangga() As Integer
        Get
            Return m_jumlahTitikTetangga
        End Get
        Set(value As Integer)
            m_jumlahTitikTetangga = value
        End Set
    End Property

    Public Property Warna() As String
        Get
            Return m_warna
        End Get
        Set(value As String)
            m_warna = value
        End Set
    End Property

    Public Sub New(ByVal idx As Integer)
        m_Idx = idx
        m_jumlahTitikTetangga = 0
        m_warna = ""
    End Sub
End Class

2. Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia
data garis yang digunakan adalah mengikuti deskripsi batasan yang sudah dijelaskan sebelumnya
sehingga beri garis pada titik yang berada pada slot waktu atau ruang yang sama

grs = New Garis(daftarTitik(0), daftarTitik(1))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(2))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(3))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(6))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(9))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(1), daftarTitik(2))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(4))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(7))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(10))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(2), daftarTitik(5))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(8))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(11))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(3), daftarTitik(4))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(5))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(6))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(9))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(4), daftarTitik(5))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(4), daftarTitik(7))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(4), daftarTitik(10))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(5), daftarTitik(8))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(5), daftarTitik(11))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(6), daftarTitik(7))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(6), daftarTitik(8))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(6), daftarTitik(9))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(7), daftarTitik(8))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(7), daftarTitik(10))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(8), daftarTitik(11))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(9), daftarTitik(10))
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(9), daftarTitik(11))
daftarGaris.Add(grs)

grs = New Garis(daftarTitik(10), daftarTitik(11))
daftarGaris.Add(grs)

Jika diilustrasikan dalam gambar, maka model graphnya adalah sebagai berikut

3. Hitung jumlah titik tetangga dari masing-masing titik yang terhubung oleh garis

For i As Integer = 0 To daftarGaris.Count - 1
	Dim garis As Garis = daftarGaris(i)

	garis.titikAwal.JumlahTitikTetangga += 1
	garis.titikTujuan.JumlahTitikTetangga += 1
Next

4. Lakukan pengurutan perhitungan sehingga titik yang dihitung lebih dulu adalah titik dengan jumlah titik tetangga terbanyak sampai pada titik tetangga yang paling sedikit

gmb.daftarTitik = daftarTitik.ToList().OrderByDescending(Function(p) p.JumlahTitikTetangga).ToList()

* Lakukan perhitungan untuk mendapatkan urutan titik dan banyak warna yang digunakan (poin 5)

5. Lakukan perhitungan pada masing-masing titik (poin 5a – 5d)

For i As Integer = 0 To jumlahTitik - 1
. . .

5a. Dapatkan titik yang sedang digunakan

Dim titik As Titik = gmb.daftarTitik(i)

5b. Lakukan perhitungan pada masing-masing garis
Tandai semua titik lain yang terhubung dengan titik yang sedang dihitung

For j As Integer = 0 To daftarGaris.Count - 1
	Dim garis As Garis = daftarGaris(j)

	If titik.Idx = garis.titikAwal.Idx Or titik.Idx = garis.titikTujuan.Idx Then
		isTitikTerhubung(garis.titikAwal.Idx) = True
		isTitikTerhubung(garis.titikTujuan.Idx) = True
	End If
Next

5c. Lakukan perhitungan pada semua titik
Masukkan semua titik yang tidak terhubung dengan titik yang sedang dihitung secara berurutan,
tapi pastikan juga bahwa tidak ada titik yang sama dimasukkan lebih dari 1 kali
Jika semua titik sudah masuk dalam urutan maka hentikan perhitungan

For j As Integer = 0 To jumlahTitik - 1
	If (i = j) Or Not isTitikTerhubung(j) Then
		Dim st As Boolean = False
		For k As Integer = 0 To urutanTitik.Count - 1
			If urutanTitik(k) Is daftarTitik(j) Then
				st = True
				Exit For
			End If
		Next

		If Not st Then
			isDitemukan = True
			urutanTitik.Add(daftarTitik(j))
			If urutanTitik.Count >= jumlahTitik Then Exit For
		End If
	End If
Next

5d. Jika ditemukan titik yang tidak terhubung dengan titik yang sedang dihitung, maka tambahkan jumlah warna yang digunakan
Jika semua titik sudah masuk dalam urutan maka hentikan perhitungan

If isDitemukan Then jumlahWarna += 1
If urutanTitik.Count >= jumlahTitik Then Exit For

6. Lakukan inisialisasi warna sebanyak jumlah warna yang diperlukan

Dim warna(jumlahWarna - 1) As String
For i As Integer = 0 To jumlahWarna - 1
	warna(i) = "Warna" & (i + 1).ToString("00")
Next

* Lakukan perhitungan untuk memberikan warna pada masing-masing titik (poin 7)

7. Lakukan perhitungan sesuai urutan titik yang sudah ditentukan sebelumnya (poin 7a – 7c)

For i As Integer = 0 To urutanTitik.Count - 1
. . .

7a. Dapatkan titik yang sedang digunakan

Dim titik As Titik = urutanTitik(i)

7b. Lakukan perhitungan pada masing-masing garis
Tandai semua warna yang sudah digunakan pada titik yang terhubung dengan titik yang sedang dihitung

For j As Integer = 0 To daftarGaris.Count - 1
	Dim garis As Garis = daftarGaris(j)

	If (isTitikTerpakai(garis.titikAwal.Idx) Or isTitikTerpakai(garis.titikTujuan.Idx)) AndAlso _
		(titik.Idx = garis.titikAwal.Idx Or titik.Idx = garis.titikTujuan.Idx) Then
		For k As Integer = 0 To jumlahWarna - 1
			If warna(k) = garis.titikAwal.Warna Then isWarnaTerpilih(k) = True
			If warna(k) = garis.titikTujuan.Warna Then isWarnaTerpilih(k) = True
		Next
	End If
Next

7c. Beri warna titik ini dengan warna yang belum digunakan pada titik yang terhubung dengan titik yang sedang dihitung
Kemudian tandai bahwa titik ini sudah diberi warna

For k As Integer = 0 To jumlahWarna - 1
	If Not isWarnaTerpilih(k) Then
		titik.Warna = warna(k)
		isTitikTerpakai(titik.Idx) = True

		Console.WriteLine("Titik " & (titik.Idx + 1).ToString("00") & " termasuk dalam warna " & k + 1)
		Exit For
	End If
Next

* Tampilkan hasil kesimpulan jumlah warna pada layar
Kemudian tampilkan data mata kuliah yang dapat dimasukkan pada jadwal kuliah

Dim kesimpulan(jumlahWarna - 1) As String
For i As Integer = 0 To jumlahTitik - 1
	Dim slot As String = ""
	If daftarTitik(i).Idx <= 2 Then
		slot = "S1"
	ElseIf daftarTitik(i).Idx <= 5 Then
		slot = "S2"
	ElseIf daftarTitik(i).Idx <= 8 Then
		slot = "S3"
	ElseIf daftarTitik(i).Idx <= 11 Then
		slot = "S4"
	End If

	Dim ruang As String = ""
	If daftarTitik(i).Idx Mod 3 = 0 Then
		ruang = "R1"
	ElseIf daftarTitik(i).Idx Mod 3 = 1 Then
		ruang = "R2"
	ElseIf daftarTitik(i).Idx Mod 3 = 2 Then
		ruang = "R3"
	End If

	For k As Integer = 0 To jumlahWarna - 1
		If daftarTitik(i).Warna = "Warna" & (k + 1).ToString("00") Then
			kesimpulan(k) &= IIf(kesimpulan(k) = "", "", " - ") & "Slot " & slot & " Ruang " & ruang
			Exit For
		End If
	Next
Next

For k As Integer = 0 To jumlahWarna - 1
	Console.WriteLine("Mata Kuliah #" & (k + 1).ToString("00") & " diletakkan pada " & kesimpulan(k))
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

Jika diilustrasikan dalam tabel, maka hasil penjadwalan adalah sebagai berikut

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.