Teori Graph di Python lewat NetworkX: Studi Kasus Greedy Algorithm

Di post sebelumnya kita sudah mengaplikasikan Teori Graph di data media sosial. Post ini justru mundur ke belakang dan fokus ke memperkenalkan NetworkX untuk aplikasi terkait Teori Graph secara umum. Graph banyak digunakan untuk memodelkan berbagai permasalahan di dunia nyata, mulai dari media sosial, transportasi, Data Science, sampai penyelesaian permainan Sudoku. Tapi saya lihat banyak pengajar & pelajar yang penelitian tentang graph-nya hanya berhenti sampai pembahasan secara teori, jarang sekali yang mengaplikasikannya sampai ke aplikasi (minimal program). Nah post ini semoga bisa menjadi sumber motivasi untuk mengembangkan lebih lanjut dengan menunjukkan bahwa membuat aplikasi graph itu mudah dengan NetworkX di Python.

Several Graph Applications [various sources].

Saya akan menggunakan studi kasus Algoritma Greedy yang sebenarnya merupakan salah satu pembahasan di Mata Kuliah Analisa Algoritma. Greedy di jadikan contoh karena mudah untuk dimengerti, sehingga mudah²an penjelasannya tidak membuat sakit kepala 😁 Ok, mari kita mulai saja dengan memperkenalkan permasalahannya. Misal diberikan suatu Graph sederhana berikut:

Tantangannya adalah mendapatkan "Minimum Spanning Tree" (MST)  dari graph tersebut. Spanning ya, bukan spaneng ... jadi ga usah puyeng dulu. Gampang kok, intinya buat sebuah Tree yang merupakan bagian dari graph diatas, tapi dengan jumlah weight di edge seminimal mungkin. Seandainya lupa, Tree adalah graph terhubung tanpa cycle ... dan bukan Tree beringin, atau Tree Pisang ya ... jokes garing ... 😅 ... MST dari graph diatas adalah sebagai berikut (Total Weight = 16):

Nah ... sekarang kita coba selesaikan dengan pendekatan Greedy. Kita bahas dulu, apa sih pendekatan Greedy? Greedy artinya "rakus", ... seseorang yang rakus adalah orang oportunis yang selalu mencoba mengambil untung sebanyak-banyaknya setiap saat tanpa memperhatikan kelak seluruh perbuatannya itu baik/tidak. Nah, ketika diterjemahkan dengan bahasa akademis (formal), untung sebanyak-banyaknya = "optimal" (dalam permasalahan diatas berarti optimal=minimal). Lalu "tanpa memperhatikan seluruh perbuatannya" maksudnya seluruh keputusannya menghasilkan optimal Global atau tidak. Optimal global dalam hal ini adalah MST dengan total weight di edge yang minimal. "Lucunya" pendekatan Greedy bisa  digunakan dalam menyelesaikan masalah MST diatas. Walau kelak ketika diterapkan di masalah lain belum tentu menghasilkan solusi optimal. Namun sebenarnya cukup dekat ke optimal. Anyway mari kita mulai dengan membentuk Graph-nya di NetworkX. Berikut codenya:

import networkx as nx
    V = ['a','b','c','d','e','f','g','z'] # Vertices
    E = [('a','b',2),('a','f',1),('b','c',2),('b','d',2),
           ('b','e',4),('c','e',3),('c','z',1),('d','e',4),('d','f',3),
           ('e','g',7),('f','g',5),('g','z',6)] # Edges & Weight-nya
# Mulai Membentuk Graph-nya
    G = nx.Graph() # Empty Graph
    for vertex in V: # Menambahkan semua vertexnya
        G.add_node(vertex)
    for v1,v2,w in E: # Menambahkan edgesnya
        G.add_edge(v1,v2, weight=w)
    print('G: {0} nodes, {1} edges'.format(G.number_of_nodes(),G.number_of_edges()))

Code diatas cukup mudah dipahami hanya dengan komentar yang ada di code-nya. But wait a minute ... mana gambar graphnya? Sabar Gan, ini baru membentuk graphnya di memory, berikutnya kita akan menggambar/plot graphnya. Berikut caranya:

pos = nx.spring_layout(G)
    eL = nx.get_edge_attributes(G,'weight')
    nx.draw_networkx_nodes(G,pos) 
    nx.draw_networkx_labels(G,pos)
    nx.draw_networkx_edge_labels(G,pos,edge_labels=eL)
    nx.draw_networkx_edges(G,pos)

Variabel "pos" adalah tipe Graph. Tipe graph sendiri bisa dipilih Spring, Shell, Spectral, random, atau Circular.  Variabel "eL" adalah weight dari edgesnya yang akan digunakan dalam parameter "edge_labels".  Sementara 4 baris terakhir secara berturut-turut menggambar di "canvas": vertex (node), label vertex, label edge, dan edgenya. Perintahnya ndak harus urut, bayangkan kalau mau gambar gunung & sawah kayak anak SD, maka Gunung atau sawahnya bisa digambar duluan. Berikut hasil Graphnya:

Hasil Plot Graph G dengan code diatas.

But Wait!!!.... kok ga sama dengan gambar diatas? ... Sabar Gan... Graph itu terdefinisi atas vertex dan edge saja dan tidak terdefinisi atas koordinat. Artinya asal (V dan E )-nya sama, maka graphnya sama ... istilah orang jawa-nya "Isomorphis" ... kalau orang perancis bilangnya, graphnya idem bin podo ... 😂... Bayangkan seperti vector, vector juga begitu, ia tidak memiliki informasi koordinat, cuma "besar" dan "arah" saja .... tapi saya ga mau bahas lebih lanjut, takutnya entar nyasar ke mana-mana ... 😅...

Graph di atas bisa di modifikasi warna, opacity, ketebalan, ukuran font, ukuran node, dll-nya ... silahkan baca disini untuk keterangan lebih lanjut untuk membuat Graph cantiknya. Btw, yang paling keren kalau gambarnya pakai graphViz... tapi kalau dibahas disini takut kepanjangan bin (riweuh).

Nah ... sekarang kembali ke permasalahan awal. Lalu solusi MST lewat Greedy-nya bagaimana? Ok, kita buat algoritmanya dulu ya:

1. Buat Graph baru (misal = MST) yang isinya hanya semua vertex di G
2. Tambahkan edge dengan weight paling minimal di E ke MST
3. Hapus Edge tersebut dari E
4. Cek apakah penambahan edge di langkah ke-2 menimbulkan cycle atau tidak (karena Tree tidak boleh memuat cycle).
5. Jika terbentuk cycle hapus edge yang baru saja ditambahkan (ndak jadi/undo)
6. Ulang mulai langkah ke [2] hingga E kosong.
7. Gambar/plot MST

Algoritma diatas mungkin bukan yang paling efisien, tapi relatif cukup mudah dimengerti. Dimana letak Greedy-nya? ... di langkah ke-2 Gan ... di setiap langkah hanya meng-consider nilai minimal di langkah tersebut. Berikut code dan hasil gambarnya ketika di implementasi-kan ke NetworkX:

MST = nx.Graph() # Empty Graph as G
    for vertex in V: # Menambahkan semua vertex di G ke MST
        MST.add_node(vertex)
    while E: # sama saja dengan While len(W)>0:
        Wmin = min(E, key = lambda t: t[2])[-1] # Ga efisien nih disini, tapi gapapa ya :D
        idx = [w[2] for w in E].index(Wmin) # ini juga sebenarnya bukan yang paling efisien
        Emin = E[idx][:2] # hanya ambil informasi edgenya
        del E[idx] # hapus edge minimal tersebut dari E
        MST.add_edge(Emin[0],Emin[1], weight=Wmin) # Tambahkan edge minimal ke MST
        if len(nx.cycle_basis(MST,'a'))>0: # Check timbul cycle/tidak, misal 'a' root
            MST.remove_edge(Emin[0],Emin[1]) # Undo jika iya
    # start drawing graph MST
        pos = nx.spring_layout(MST)
        eL = nx.get_edge_attributes(MST,'weight')
        nx.draw_networkx_nodes(MST,pos) 
        nx.draw_networkx_labels(MST,pos)
        nx.draw_networkx_edge_labels(MST,pos,edge_labels=eL)
        nx.draw_networkx_edges(MST,pos)

 

MST berdasarkan Greedy approach dengan NetworkX diatas.

Penjelasannya saya skip untuk Agan latihan memahami code ya (komentar code-nya cukup jelas kok). Seharusnya ndak terlalu sulit (dengan kata lain TS sudah capek nulis post yang sudah mulai kepanjangan ini ... 😆). Kalau mau mengefisienkan code di atas caranya mudah:

1. Urutkan E berdasarkan weight : E.sort(key=lambda tup: tup[2])
2. Ubah 2 baris setelah While menjadi Wmin = E[0][2] dan idx = 0 (Karena sudah terurut)

Dengan begitu maka total kompleksitas-nya turun menjadi O(N log(N)) dengan N adalah jumlah vertex. Aplikasinya saya serahkan ke Agan untuk latihan. Kalau ada yang kurang jelas silahkan tanya di kolom komentar. O iya, mulai hari ini, semua codes di blog ini saya taro di GitHub berikut, code post ini ada di file Greedy_Minimum_Spannning_Tree.py, sehingga Agan ndak perlu capek-capek CoPas dari blog ini. Gimana serpis-nya memuaskan kan Gan? ... jangan lupa kasih cendol ya... #eh #lupa ini bukan kaskus ... 😅 ....

Pengetahuan dari post ini sekilas nampak remeh dan mudah (dasar). Namun jika dipahami dengan baik, sebenarnya permasalahan Graph yang kompleks seperti aplikasi di sosial media atau data science secara umum juga dapat diselesaikan dengan pendekatan yang sama. Semoga bermanfaat, silahkan share jika sekiranya bermanfaat, like kalau emang suka, dan cicing wae kalau ngga ... #kidding 😄 ... Cheers ...