Pewarnaan graf dengan python

Bismillah.
Assalaamu 'alaikum wa rahmatullaah wa barakaatuh, Sahabat.
Beberapa waktu yang lalu, sebenarnya sudah dari 2015 aku lihat seperti ini, tapi masih belum di springerlink, sih. Aku lihat lagi di
http://link.springer.com/article/10.1007/s10878-015-9862-1
itu di tahun 2016 ini. Dulu dari google scholar kalau ndak salah. Barangkali ada yang mau gratisnya, silakan unduh di researchgate ini:
https://www.researchgate.net/publication/274076696_A_fast_greedy_sequential_heuristic_for_the_vertex_colouring_problem_based_on_bitwise_operations
Pewarnaan graf menggunakan operasi bit. Canggih banget. MasyaAllah tabarakallah. Walaupun itu ndak diurutkan derajat titiknya, tapi cepet juga kok. Kalau optimalnya, belum tentu sih..
Aku mbuat contoh kasus sekalian programnya dengan bahasa python seperti ini. Siapatau ada yang tertarik.. ^_^

Kita punya graf seperti ini, misalkan.

Kalau pengin tau gimana cara nggambar graf kayak gitu (yang canggih bisa ditarik-tarik kayak jelly) di blog, bisa mampir dulu ke sini:
http://muktyas.blogspot.co.id/2016/08/menggambar-graf-dengan-html5.html
Bisa kita warnai dengan algoritma yang disusun Komosko tadi seperti ini.
Di situ aku juga cerita langkah demi langkahnya lho..
# Sahabat, kita punya list yang berisi ketetanggaan # dari titik-titik graf G berikut ini: g = [[1,2], [1,6], [1,7], [2,3], [3,4], [4,5], [4,8], [5,6]] # Itu artinya titik 1 bertetangga dengan titik 2, 6, dan 7. # Kita bisa membuat matriks ketetanggaannya # dengan fungsi ini: def mk(listsisi): makst = max([i for grup in listsisi for i in grup]) a = [[0 for i in range(makst)] for j in range(makst)] for i in listsisi: a[i[0]-1][i[1]-1] = 1 a[i[1]-1][i[0]-1] = 1 return a # Selanjutnya kita namakan matriks ketetanggaan dari graf G dengan "a" a = mk(g) # Lalu bisa kita print di output terminal kita dengan perintah ini print "Matriks ketetanggaan A =" for i in a: print i print "-------------" # Di fungsi habis ini akan kita buat matriks ketetanggaan tadi menjadi # bentuk bilangan bulat, baris per baris. maksudnya dari biner ke integer. # Contoh saja di baris pertama seperti ini. # Kalau binernya 01000110 berarti bulatnya jadi 70 def listkeint(list): b = '' for i in list: b += str(i) return int(b,2) # Kita namakan dengan variabel "aint", yaitu "a" yang menjadi integer. aint = [ listkeint(i) for i in a] # Terus kita tampilkan deh.. print "aint =", aint # -------------------------- # Nah, ini bagian pewarnaan grafnya # ==================================== # c adalah matriks warna terlarang (forbidden color) # maksudnya, di matriks c yang bitnya 1 itu berarti # ndak boleh diwarnai dengan warna baris itu. pjgA = len(aint) c = [ 0 for i in range(pjgA)] print "c =", c # ini untuk "mask" nya, kita indonesiakan jadi "topeng" # nantinya topeng ini sangat bermanfaat lho, # kita mau ngecek apakah di bit itu hidup (1) atau mati (0) # kalau di coloring ini, apakah masih bisa diwarnai (0) atau # sudah ndak bisa (1) # caranya dengan operator "dan (&)" topeng = 1 << (pjgA - 1) # Setelah menginisialisasi "topeng" nya, # di bagian ini lah proses pewarnaan untuk seluruh grafnya for i in range(pjgA): # untuk kolom di A for j in range(pjgA): # ini untuk baris di C cek = c[j] & topeng # bitnya hidup ndak ya? if cek == 0: c[j] = c[j] | aint[i] topeng = topeng >> 1 break # Akhirnya bisa kita tampilkan di layar dengan script ini. print "Setelah kutunggu cukup lama, akhirnya ketemu juga.." print "c =", c # Itu kalau kita artikan di bahasa manusia seperti ini print "\nItu artinya seperti ini:" h = [ 1<<pjga | i for i in c ] for bul in h: print bin(bul) # Kita perjelas lagi.. wint = [ i for i in c if i != 0 ] banyakw = len(wint) print "\nAku kira %s warna saja sudah cukup untuk semua titik." %(banyakw) print "Anggap 0b1 itu tidak ada.\n" print "Selanjutnya bit 0 berarti boleh diwarnai baris itu." print "Jadinya pasangan titik dan warna adalah seperti ini.\n" for i in range(banyakw): print "warna %s:" %i print [ j+1 for j, e in enumerate(bin(h[i])[3:]) if e == '0' ]
Blok semua script itu, lalu simpan sebagai warnagrafmuks.py. Jalankan dengan python. Semoga bermanfaat, Sahabat. :)
Assalaamu'alaikum..