BFS & DFS dengan NetworkX di Python

Kemarin kita sudah membahas permasalahan sederhana Greedy algorithm di NetworkX. Sekarang kita akan membahas 2 permasalahan sederhana lain di Teori Graph masih dengan NetworkX, yaitu Breadth First Search (BFS) dan Depth First Search (DFS). O iya, post ini adanya di blog ini, bukannya di blog data science, karena permasalahan yang dibahas agak menjauh dari tema DS/IoT/BD. Ada cerita yang (menurut saya) menarik dibalik post ini. DFS & BFS biasanya dibahas (setidaknya) di either mata kuliah Matematika Diskrit atau Analisa Algoritma. Either way saya akhir² ini agak "gemes" mahasiswa ga sadar betapa pentingnya materi² yang ia pelajari di kehidupan nyata. Sebenarnya mungkin ndak sepenuhnya salah mereka juga sih, karena ndak hanya pengajar, bahkan bukunya-pun jarang yang menerangkan hal ini. Tapi sekarang jaman internet, mereka bisa dengan mudah mendapatkan informasi ini. Singkat cerita, DFS/BFS ini cukup banyak aplikasinya di dunia nyata, misal saja penentuan rute di GPS atau permasalahan di bidang sistem transportasi. Kemungkinan besar they use modified version of the algorithm, tapi basic/logic-nya masih sama (baca disni atau disini).

Contoh Aplikasi Graph Traversal - Map Route (GPS)

Anyway, di kelas saya sering melempar pertanyaan dengan iming² nilai tambahan di ujian (UTS/UAS). Misal UTS/UAS+10, 20, atau bahkan 30 bergantung kesulitan soal yang saya berikan di kelas. Prinsip saya ujian kan hanya meng-evaluasi pemahaman mahasiswa, kalau di kelas ia sudah mampu menunjukan bahwa ia mengerti materi yang diberikan, maka sebenarnya ujian menjadi tidak terlalu efektif buat mereka. Anyway balik ke laptop, eh maksudnya BFS/DFS, ... pas ngajar ini di kelas saya agak gemes karena mereka kok kurang termotivasi dengan imimng² bonus nilai di ujian di atas. Walhasil saya waktu itu iseng dan mengatakan: "kalau ada yang bisa aplikasikan DFS atau BFS ini ke NetworkX untuk menemukan Spanning Tree dari Graph dalam 30 menit, maka ndak hanya nilai ujian UTS & UAS-nya yang di tambah, tapi juga saya traktir makan siang di warung Padang, minumnya es jeruk, dan boleh nambah. Ga hanya itu, boleh di kerjakan berkelompok (semua member di traktir & dapat bonus nilai) dan boleh nyontek dari internet (copas)." Jujur, saat itu agak deg²an juga, bukan hanya karena uang di dompet pas²an, tapi juga karena belum nge-check di internet: "ada ga ya?" ... ?? ... (Notes, mereka sudah belajar networkX dan aplikasi²nya di pertemuan² sebelumnya). "Untungnya" ndak ada yang bisa .... ?? ... (#DosennyaJahatGaIkhlas) ... Anyway, saya cukup PD karena saya sering menyayangkan kurikulum perguruan tinggi yang jarang update dari puluhan tahun yang lalu (di banyak universitas dalam & bahkan luar negeri). Hal ini di dukung dengan kenyataan bahwa mereka ndak bisa menemukan aplikasi langsung BFS/DFS ini ke aplikasi yang kekinian. (that!, atau nge-Google-nya kurang cermat ... ??) Ah udah ah ... ceritanya kepanjangan ... mari kita bahas DFS/BFS-nya ??. BFS/DFS sebenarnya merupakan Graph traversal, atau dengan kata lain traversal adalah jalan² di graph melalui edge²nya. namun tentu saja dengan syarat tertentu. Teori "ngasal"-nya mudah sekali: BFS: "Traverse level yang rendah dan sesuai urutan nodes terlebih dahulu" DFS: "Keep Traversing sesuai urutan nodes, lalu backtrack kalau mentok" Kalau mau penjelasan teori lebih lengkap dan formalnya bisa simak disini: BFS & DFS Sehingga kalau diberikan graph seperti ini:

dengan pemisalan root = "a" dan urutan node sesuai abjad (a,b,c,d,e,f,g,h), maka spanning tree BFS-nya adalah:

Penjelasannya cukup sederhana: dimulai dari root "a" (level 0), maka di level selanjutnya (1) ada nodes b, c, & g. Sesuai level dan urutan maka setelah a terus b, lalu c, kemudian g. Setelah itu ke level 2, ada d & e. Kemudian f di level 3 dan terakhir h di level 4. Sehingga spanning tree-nya seperti di atas. dan spanning tree DFS-nya adalah:

Dimulai dari user-defined root = "a", kemudian traverse sesuai urutan node: berarti b, kemudian terus maju sesuai urutan node: d, dan seterusnya sampai h. Karena di h mentok, lalu "backtrack" ke f, tapi di f tidak ada lagi edge yang bisa di tambahkan, kemudian backtrack lagi ke e, kemudian terakhir tambahkan g.

 

Mudah sekali kan? ... Ok, kalau sudah mengerti sekarang coba Agan coba sendiri dulu aplikasi NetworkX-nya. Kalau perlu refresh lagi pengetahuan dari post sebelumnya ini. Agan boleh search ke internet for clues (tapi ga boleh ke blog dan github saya). Coba selesaikan masing-masing (DFS & BFS) dalam waktu <30 menit (total 1 jam). Inputnya graph diatas, outputnya gambar graph spanning tree seperti di atas. If you can please let me know in the comment. Catt: nope, agan ga dapet makan siang gratis ... ?? ... saya penasaran aja ...

... Asumsi pembaca lagi ngerjain ....

~

... masih juga berasumsi yang sama ....

~

... Ceritanya masih nungguin ...

~

Ok... mari kita bahas contoh solusinya. Seperti biasa, saya akan berikan code yang tidak/kurang efisien. Saya mengharapkan Agan bisa latihan untuk meng-efisienkan code tersebut. Seperti yang dijelaskan disini, algoritma & program yang efisien sangat penting di Data Science/Big Data.

Code lengkap berikut ini saya letakkan di GitHub saya ini, dan nama filenya "BFS_NetworkX.py" dan "DFS_NetworkX.py" dengan file pendukung "my_NetworkX_lib.py" supaya BFS dan DFS-nya ndak keriting. Ok, berikut penjelasannya:

1. Menyiapkan graph awalnya:

   

import networkx as nx
    from my_NetworkX_lib import buildGraph, drawGraph # ini berdasarkan post networkX saya sebelumnya.


    V = ['a', 'b', 'c', 'd' , 'e', 'f', 'g', 'h'] # Untuk memudahkan kita asumsikan urutan di V ini = urutan nodes di soal.
    E = [('a','b'),('a','c'),('a','g'),('a','g'),('b','d'),('b','g'),('c','d'),('c','e'),('d','f'),('e','f'),('e','f'),('f','h'),('g','e')]
    G = buildGraph(V, E=E) # Graph di soal
    root = V[0] # Asumsi root = "a"

Untuk bagian ini tidak perlu penjelasan, karena sudah dibahas di post sebelumnya. Bedanya hanya sekarang kita tidak punya weight di edges-nya (lebih simple/sederhana).

2. Solusi BFS:

 

  Levels = [[root]]
    Vtemp = [root]
    # Mulai dengan mencari informasi nodes di setiap level [belum efisien]
    for v in V:
        e = G.edges(v)
        e = [v2 for v1,v2 in e if v2 not in Vtemp]
        if e:
            Levels.append(e)
            Vtemp = Vtemp + e
    # Mulai membangun Spanning Tree-nya
    BFS = buildGraph(V)
    for vertices in Levels:
        for v in vertices:
            e = G.edges(v) # Semua edges yang adjacent ke node v
            for v1, v2 in e:
                BFS.add_edge(v1,v2)
                if len(nx.cycle_basis(BFS,root))>0:
                    BFS.remove_edge(v1,v2)

 

Algoritmanya simple: pertama-tama cari tau dulu ada nodes apa saja di setiap level. Kemudian tambahkan edges ke BFS sesuai dengan level tersebut. Informasinya di simpan dalam variable "Levels", jadi Levels adalah "list of lists" (i.e. Levels = [['a'], ['b','c','g'], ... dst]). Variable "Vtemp" digunakan supaya kita tidak traverse ke level di atasnya.

That's it!.... Bagian kedua program ini mirip dengan kasus Greedy kemarin. Menambahkan edge ke BFS selama tidak menimbulkan cycle. O iya, ada satu yang baru, yaitu perintah "G.edges(v)" yang akan menghasilkan (v,v2) untuk semua v2 yang adjacent/terhubung ke v. Atau dengan kata lain memberikan informasi nodes mana saja yang terhubung dengan node v.

3. Solusi DFS:

VDFS = V[:] # a copy of V by values
    DFS = nx.Graph() # empty graph
    v = VDFS[0]; del VDFS[0]
    stack = [root] # untuk backtrack


    while VDFS: # VDFS not empty
        DFS.add_node(v)
        e = G.edges(v)
        nextNode = [v2 for v1,v2 in e if v2 not in DFS.nodes()]
        if nextNode: # Not Empty
            nextNode.sort() # meyakinkan urutannya sesuai urutan node (abjad)
            DFS.add_node(nextNode[0])
            DFS.add_edge(v,nextNode[0])
            v = nextNode[0]
            stack.append(v)
            del VDFS[VDFS.index(v)]
        else: #Backtrack
            v = stack[-1]; del stack[-1]

Bedanya dengan BFS, di DFS ini kita butuh suatu variabel untuk melakukan "BackTrack". Variabel yang saya gunakan di code ini adalah "stack". Saya gunakan variabel VDFS sebagai stopper, bahwa kita sudah men-traverse seluruh node di graph. Hati-hati ... kita tidak bisa menggunakan perintah berikut di python "VDFS=V" karena Python melakukan copy by reference (pointer) dan bukan by values (baca disini). Backtrack dilakukan di baris terakhir dengan menggunakan elemen terakhir dari variabel stack. Di dunia pemrograman biasa disebut sebagai "pop" operation. Sedangkan perintah "stack.append(v)" biasa disebut sebagai operasi "push".

4. Plot Graph solusinya:

drawGraph(G, file="GraphAwal.png", labels = True, edge_Label=False, gType = 'spring')
    drawGraph(BFS, file="BFS.png", labels = True, edge_Label=False, gType = 'spring')
    drawGraph(DFS, file="DFS.png", labels = True, edge_Label=False, gType = 'spring')

Graphnya selain di plot, langsung di save ke disk (dalam bentuk PNG)... ?? ... biar handy. Ini hasilnya:

Graph Awal, BFS, & DFS. Silahkan di cek apakah hasil tersebut isomorfis dengan solusi di atas.

That's it ... mudah kan? ... ?? ... Kalau di search di Google banyak solusi dari BFS dan DFS ini menggunakan fungsi rekursif. Agan bisa latihan dengan mencari solusi rekursifnya. O iya, hati-hati juga banyak algoritma BFS dan DFS di internet hanya sekedar untuk traversal saja, tapi belum ke spanning tree-nya. Anyway ... semakin banyak baca insya Allah akan semakin puyeng... eh salah, maksud saya semakin jelas ... ?? ...

Post selanjutnya kita coba masalah umum lain di Graph, that's it for now. Have a nice weekend Guys ... Cheers...

Depok, 07 Jan 2018

 

</TES>®