desaindananalisisalgoritmakomputasijumlah...

TUGAS AKHIR - KI141502

DESAIN DAN ANALISIS ALGORITMA KOMPUTASI JUMLAHBRIDGE PADA GRAF DINAMIS INKREMENTAL

YUSRO TSAQOVANRP 5112 100 095

Dosen Pembimbing 1Bilqis Amaliah, S.Kom., M.Kom.

Dosen Pembimbing 2Rully Soelaiman, S.Kom., M.Kom.

JURUSAN TEKNIK INFORMATIKAFakultas Teknologi InformasiInstitut Teknologi Sepuluh NopemberSurabaya, 2016

UNDERGRADUATE THESES - KI141502

ALGORITHM DESIGN AND ANALYSIS FOR BRIDGE COMPU-TATION ON INCREMENTAL DYNAMIC GRAPH

YUSRO TSAQOVANRP 5112 100 095

Supervisor 1Bilqis Amaliah, S.Kom., M.Kom.

Supervisor 2Rully Soelaiman, S.Kom., M.Kom.

INFORMATICS DEPARTMENTFaculty of Information TechnologyInstitut Teknologi Sepuluh NopemberSurabaya, 2016

DESAIN DAN ANALISIS ALGORITMA KOMPUTASIJUMLAH BRIDGE PADA GRAF DINAMIS INKREMEN-TALNama : YUSRO TSAQOVANRP : 5112 100 095Jurusan : Teknik Informatika FTIF - ITSPembimbing I : Bilqis Amaliah, S.Kom., M.Kom.Pembimbing II : Rully Soelaiman, S.Kom., M.Kom.

AbstrakKomputasi jumlah bridge pada graf dinamis inkremental meru-pakan permasalahan perhitungan jumlah bridge pada sebuah grafyang bentuknya berubah secara dinamis karena pertambahan edge.Untuk mendapatkan jumlah bridge pada graf bisa dilakukan de-ngan komputasi ulang untuk setiap operasi penambahan edge na-mun pendekatan tersebut tentunya tidak efisien.

Pada Tugas Akhir ini akan dirancang penyelesaian permasalah-an di atas dengan melihat beberapa kondisi yang harus diperhatik-an dari pasangan vertex yang mengalami pertambahan edge ya-itu apakah pasangan vertex berada dalam himpunan connected-component yang berbeda, himpunan connected-component yangsama namun dalam himpunan bridge-block yang berbeda atau da-lam himpunan bridge-block yang sama. Implementasi dari solusiini menggunakan bantuan struktur data disjoint set ditambah pen-dekatan heuristik union by weight dan path compression.

Hasil dari Tugas Akhir ini telah berhasil menyelesaikan perma-salahan di atas dengan cukup efisien dengan kompleksitas waktuO(M(α(N))) dimana α(N) adalah invers dari fast-growingackermann function dan bernilai ≤ 4 untuk setiap N.

Kata Kunci: Graf, Bridge, Online, Pencarian, Dinamis,Inkremental

ix

x

Halaman ini sengaja dikosongkan

ALGORITHM DESIGN AND ANALYSIS FOR BRIDGECOMPUTATION ON INCREMENTAL DYNAMIC GRA-PHName : YUSRO TSAQOVANRP : 5112 100 095Major : Informatics Department Faculty of IT - ITSSupervisor I : Bilqis Amaliah, S.Kom., M.Kom.Supervisor II : Rully Soelaiman, S.Kom., M.Kom.

AbstractBridge number computation on incremental graph is a problem ofcomputation of bridge number on a graphwhich is dynamically cha-nged because of edge addition. For obtaining bridge total numberin a graph, the use of re-computation for every single operation ofedge addition is possible, but certainly it is inefficient.

This undergraduate thesis will design the problem solving of theproblem above by seeing some conditions which should be consi-dered from vertex pair which has edge addition, which is whethervertex are located in same connected-component set or not but in asame bridge-block set or in similar bridge-block set. The implemen-tation of this solution is using the help of disjoint set data structureand heuristic union by weight and path compression.

The result of this undergraduate thesis has successfully solved theproblem mentioned with sufficient enough by the O(M(α(N)))time complexity where α(N) is the inverse of fast-growing acker-mann function and has less than or equal 4 for every single N.

Kata Kunci: Graph, Bridge, Online, Searching, Dynamic,Incremental

xi

xii


KATA PENGANTAR

Puji syukur penulis panjatkan kepada Allah SWT atas segala rah-mat dan karunia-Nya sehingga memungkinkan penulis untuk dapatmenyelesaikan Tugas Akhir yang berjudul:

DESAIN DAN ANALISIS ALGORITMA KOMPUTASIJUMLAH BRIDGE PADA GRAF DINAMIS

INKREMENTAL.

Penelitian Tugas Akhir ini dilakukan untuk memenuhi salah satusyarat meraih gelar Sarjana di Jurusan Teknik Informatika FakultasTeknologi Informasi Institut Teknologi Sepuluh Nopember.

Dengan selesainya Tugas Akhir ini diharapkan apa yang telah diker-jakan penulis dapat memberikan manfaat bagi perkembangan ilmupengetahuan terutama di bidang teknologi informasi serta bagi diripenulis sendiri selaku peneliti.

Penulis mengucapkan terima kasih kepada semua pihak yang te-lah memberikan dukungan baik secara langsungmaupun tidak lang-sung selama penulis mengerjakan Tugas Akhir maupun selama me-nempuh masa studi antara lain:

• Allah SWT atas segala rahmat dan karunia yang telah dibe-rikan selama ini.

• Ayah, Ibu dan keluarga penulis yang selalu memberikan per-hatian, dorongan dan kasih sayang yang menjadi semangatutama bagi diri penulis baik selama penulis menempuh masakuliah maupun pengerjaan Tugas Akhir ini.

• Bapak Rully Soelaiman, S.Kom., M.Kom. selaku DosenPembimbing yang telah banyak meluangkan waktu untukmemberikan ilmu, nasihat, motivasi, pandangan dan bim-

xiii

xiv

bingan kepada penulis baik selama penulis menempuh masakuliah maupun selama pengerjaan Tugas Akhir ini.

• Ibu Bilqis Amaliah, S.Kom., M.Kom. selaku Dosen Pembim-bing yang telah memberikan dukungan, nasihat, arahan danmasukan kepada penulis.

• Seluruh tenaga pengajar dan karyawan Jurusan Teknik Infor-matika ITS yang telah memberikan ilmu dan waktunya demiberlangsungnya kegiatan belajar mengajar di Jurusan TeknikInformatika ITS.

• Teman-teman Laboratorium Pemrograman angkatan 2011,2012 dan 2013 yang telah menjadi keluarga di kampus.

• Seluruh teman penulis di Jurusan Teknik Informatika ITSyang telah memberikan dukungan dan semangat kepada pe-nulis selama penulis menyelesaikan Tugas Akhir ini.

• Seluruh pihak yang tidak bisa penulis sebutkan satu-persatuyang telah memberikan dukungan selama penulis menyelesa-ikan Tugas Akhir.

Penulis mohon maaf apabila masih ada kekurangan pada TugasAkhir ini. Penulis juga mengharapkan kritik dan saran yangmembangun untuk pembelajaran dan perbaikan di kemudianhari. Semoga melalui Tugas Akhir ini penulis dapat memberikankontribusi dan manfaat yang sebaik-baiknya.

Surabaya, Januari 2016

Yusro Tsaqova

DAFTAR ISI

SAMPUL i

LEMBAR PENGESAHAN vii

ABSTRAK ix

ABSTRACT xi

KATA PENGANTAR xiii

DAFTAR ISI xv

DAFTAR TABEL xix

DAFTAR GAMBAR xxi

DAFTAR KODE SUMBER xxv

1 PENDAHULUAN 11.1 Latar Belakang . . . . . . . . . . . . . . . . . . . 11.2 Rumusan Masalah . . . . . . . . . . . . . . . . . . 31.3 Batasan Masalah . . . . . . . . . . . . . . . . . . 31.4 Tujuan . . . . . . . . . . . . . . . . . . . . . . . . 31.5 Metodologi . . . . . . . . . . . . . . . . . . . . . 41.6 Sistematika Penulisan . . . . . . . . . . . . . . . . 5

2 DASAR TEORI 72.1 Deskripsi Permasalahan . . . . . . . . . . . . . . . 72.2 Strategi Penyelesaian Permasalahan . . . . . . . . 92.3 Disjoint Set . . . . . . . . . . . . . . . . . . . . . 13

xv

xvi

2.4 Lowest Common Ancestor (LCA) . . . . . . . . . 192.5 Permasalahan Online Bridge Searching pada SPOJ 222.6 Pembuatan Data Generator untuk Uji Coba . . . . 29

3 DESAIN 333.1 Deskripsi Umum Sistem . . . . . . . . . . . . . . 333.2 Desain Kelas Node dan Fungsi Init . . . . . . . . . 343.3 Desain Fungsi InsertEdge . . . . . . . . . . . . . . 353.4 Desain Fungsi FindBridgeBlock . . . . . . . . . . 363.5 Desain Fungsi FindComponent . . . . . . . . . . . 363.6 Desain Fungsi SetRoot . . . . . . . . . . . . . . . 373.7 Desain Fungsi MergeBridgeBlock . . . . . . . . . 38

4 IMPLEMENTASI 394.1 Lingkungan Implementasi . . . . . . . . . . . . . 394.2 Implementasi Fungsi Main . . . . . . . . . . . . . 394.3 Implementasi Variabel Global . . . . . . . . . . . 404.4 Implementasi Struct Node . . . . . . . . . . . . . . 414.5 Implementasi Fungsi InsertEdge . . . . . . . . . . 424.6 Implementasi Fungsi FindBridgeBlock . . . . . . . 434.7 Implementasi Fungsi FindComponent . . . . . . . 444.8 Implementasi Fungsi SetRoot . . . . . . . . . . . . 444.9 Implementasi Fungsi MergeBridgeBlock . . . . . . 45

5 UJI COBA DAN EVALUASI 475.1 Lingkungan Uji Coba . . . . . . . . . . . . . . . . 475.2 Skenario Uji Coba . . . . . . . . . . . . . . . . . . 47

5.2.1 Uji Coba Kebenaran . . . . . . . . . . . . 475.2.2 Uji Coba Kinerja . . . . . . . . . . . . . . 58

6 KESIMPULAN 636.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . 63

DAFTAR PUSTAKA 65

xvii

Lampiran A Hasil uji pada situs SPOJ sebanyak 30 kali 67

Lampiran B Hasil uji kinerja jumlah operasi M tetap 71

Lampiran C Hasil uji kinerja jumlah vertex N tetap 79

BIODATA PENULIS 87

xviii


DAFTAR GAMBAR

2.1 Ilustrasi permasalahan. . . . . . . . . . . . . . . . 82.2 Ilustrasi komputasi jumlah bridgemenggunakan al-

goritma Bridge-Finding. . . . . . . . . . . . . . . 102.3 Ilustrasi bridge, dan bridge-block. . . . . . . . . . 112.4 Ilustrasi penambahan edge(u, v) dengan u dan v ber-

ada pada connected component yang berbeda. . . . 112.5 Ilustrasi penambahan edge(u, v) dengan u dan v ber-

ada pada bridge-block yang berbeda namun dalamconnected component yang sama. . . . . . . . . . 12

2.6 Path-compression pada disjoint set. . . . . . . . . 142.7 Ilustrasi disjoint set dari graf pada permasalahan. . 152.8 Ilustrasi penambahan bridge dan representasi pada

disjoint set (1). . . . . . . . . . . . . . . . . . . . 162.9 Ilustrasi penambahan bridge dan representasi pada




disjoint set (5). . . . . . . . . . . . . . . . . . . . 182.13 Contoh ilustrasi LCA dari 2 vertex. . . . . . . . . . 202.14 Ilustrasi cycle dan penerapan LCA pada permasa-

lahan (1). . . . . . . . . . . . . . . . . . . . . . . 212.15 Ilustrasi cycle dan penerapan LCA pada permasa-

lahan (2). . . . . . . . . . . . . . . . . . . . . . . 212.16 Deskripsi permasalahan Online Bridge Searching

di SPOJ. . . . . . . . . . . . . . . . . . . . . . . . 22

xxi

xxii

2.17 Contoh masukan dan keluaran pada soal OnlineBridge Searching. . . . . . . . . . . . . . . . . . . 24

2.18 Ilustrasi operasi yang menghasilkan bridge padacontoh permasalahan. . . . . . . . . . . . . . . . . 24

2.19 Ilustrasi disjoint set pada contoh permasalahan. . . 252.20 Ilustrasi operasi yang menggabungkan beberapa

bridge-block dan menghapus bridge pada contohpermasalahan. . . . . . . . . . . . . . . . . . . . . 26

2.21 Ilustrasi disjoint set dan LCA saat pembentukancycle (1). . . . . . . . . . . . . . . . . . . . . . . 26

2.22 Ilustrasi disjoint set dan LCA saat pembentukancycle (2). . . . . . . . . . . . . . . . . . . . . . . 27

2.23 Ilustrasi graf dan disjoint set setelah operasi penam-bahan edge(1, 4). . . . . . . . . . . . . . . . . . . 28

2.24 Ilustrasi graf dan disjoint set setelah operasi penam-bahan edge(2, 4). . . . . . . . . . . . . . . . . . . 28

2.25 Ilustrasi kondisi akhir dari graf dan disjoint set padacontoh kasus Online Bridge Searching. . . . . . . 29

2.26 Pseudocode Fungsi Main Generator Skenario Uji 1 302.27 Pseudocode Fungsi Main Generator Skenario Uji 2 31

3.1 Pseudocode Fungsi Main . . . . . . . . . . . . . . 333.2 Pseudocode Fungsi Init . . . . . . . . . . . . . . . 343.3 Pseudocode Fungsi InsertEdge . . . . . . . . . . . 353.4 Pseudocode Fungsi FindBridgeBlock . . . . . . . . 363.5 Pseudocode Fungsi FindComponent . . . . . . . . 373.6 Pseudocode Fungsi SetRoot . . . . . . . . . . . . 373.7 Pseudocode Fungsi MergeBridgeBlock . . . . . . 38

5.1 Contoh kasus uji hasil dari data generator. . . . . . 485.2 Inisialisasi contoh kasus uji. . . . . . . . . . . . . 495.3 Ilustrasi penambahan edge(5, 3) pada contoh kasus

uji. . . . . . . . . . . . . . . . . . . . . . . . . . . 49

xxiii

5.4 Ilustrasi penambahan edge(5, 4) pada contoh kasusuji. . . . . . . . . . . . . . . . . . . . . . . . . . . 50



5.7 Ilustrasi penambahan edge(4, 2) pada contoh kasusuji (1). . . . . . . . . . . . . . . . . . . . . . . . . 52








5.15 Hasil luaran program pada contoh kasus uji. . . . . 575.16 Hasil uji kebenaran pada situs SPOJ. . . . . . . . . 575.17 Peringkat waktu eksekusi program Online Bridge

Searching pada situs SPOJ. . . . . . . . . . . . . . 585.18 Grafik Hasil uji pada situs SPOJ sebanyak 30 kali. . 605.19 Grafik hasil uji coba pengaruh jumlah vertex terha-

dap pertumbuhan waktu. . . . . . . . . . . . . . . 615.20 Grafik hasil uji coba pengaruh jumlah operasi ter-

hadap pertumbuhan waktu. . . . . . . . . . . . . . 62

A.1 Hasil uji pada situs SPOJ sebanyak 30 kali (1). . . 67

xxiv

A.2 Hasil uji pada situs SPOJ sebanyak 30 kali (2). . . 68A.3 Hasil uji pada situs SPOJ sebanyak 30 kali (3). . . 69

DAFTAR KODE SUMBER

4.1 Implementasi Fungsi Main . . . . . . . . . . . . . 404.2 Implementasi Variabel Global . . . . . . . . . . . 404.3 Implementasi Struct Node . . . . . . . . . . . . . . 414.4 Implementasi Fungsi InsertEdge . . . . . . . . . . 424.5 Implementasi Fungsi FindBridgeBlock . . . . . . . 434.6 Implementasi Fungsi FindComponent . . . . . . . 444.7 Implementasi Fungsi SetRoot . . . . . . . . . . . . 444.8 Implementasi Fungsi MergeBridgeBlock . . . . . . 45

xxv

xxvi


DAFTAR TABEL

B.1 Hasil uji dengan nilai jumlah operasi M tetap 25.000. 71B.1 Hasil uji dengan nilai jumlah operasiM tetap 25.000

(lanjutan). . . . . . . . . . . . . . . . . . . . . . . 72B.2 Hasil uji dengan nilai jumlah operasi M tetap 50.000. 73B.2 Hasil uji dengan nilai jumlah operasiM tetap 50.000

(lanjutan). . . . . . . . . . . . . . . . . . . . . . . 74B.3 Hasil uji dengan nilai jumlah operasi M tetap 75.000. 75B.3 Hasil uji dengan nilai jumlah operasiM tetap 75.000

(lanjutan). . . . . . . . . . . . . . . . . . . . . . . 76B.4 Hasil uji dengan nilai jumlah operasi M tetap 100.000. 77B.4 Hasil uji dengan nilai jumlah operasi M tetap

100.000 (lanjutan). . . . . . . . . . . . . . . . . . 78

C.1 Hasil uji dengan nilai jumlah vertex N tetap 12.500. 79C.1 Hasil uji dengan nilai jumlah vertex N tetap 12.500

(lanjutan). . . . . . . . . . . . . . . . . . . . . . . 80C.2 Hasil uji dengan nilai jumlah vertex N tetap 25.000. 81C.2 Hasil uji dengan nilai jumlah vertex N tetap 25.000



(lanjutan). . . . . . . . . . . . . . . . . . . . . . . 86

xix

xx


BAB 1

PENDAHULUAN

Pada bab ini akan dijelaskan latar belakang, rumusan masalah, ba-tasan masalah, tujuan, metodologi dan sistematika penulisan TugasAkhir.

1.1 Latar Belakang

Teori graf adalah salah satu cabang ilmu yang sudah ada sejak lamadan banyak sekali diterapkan untuk membantu pemecahan masa-lah terutama di bidang ilmu pengetahuan dan teknologi informasi.Banyak permasalahan di dunia nyata seperti komputasi jalur terpen-dek atau informasi yang terkandung pada hubungan pertemanan dimedia sosial yang dapat dimodelkan dengan bantuan teori graf un-tuk selanjutnya dilakukan komputasi dan didapatkan hasil yang di-inginkan. Dalam beberapa dekade terakhir tidak sedikit algoritmadan struktur data yang diciptakan untuk mengatasi permasalahangraf.

Graf dinamis adalah sebuah model permasalahan graf dimana infor-masi yang diinginkan bisa didapat kapan saja dari sebuah graf yangbentuknya berubah-ubah dikarenakan operasi modifikasi berupa pe-nambahan maupun pengurangan vertex atau edge pada graf terse-but [1]. Permasalahan graf dinamis dapat diklasifikasikan menja-di fully dynamic dan partially dynamic. Sebuah masalah dikatak-an fully dynamic apabila dalam masalah tersebut terdapat dua je-nis operasi modifikasi yaitu penambahan dan penghapusan vertexatau edge. Sebuah masalah dikatakan partially dynamic apabila ha-nya ada satu jenis operasi dari penambahan atau penghapusan yang

1

2

dapat dilakukan. Jika hanya operasi penambahan yang dapat dila-kukan, maka masalah tersebut dikatakan inkremental. Jika hanyaoperasi penghapusan yang dapat dilakukan, maka masalah tersebutdikatakan dekremental.

Salah satu topik yang cukup menarik pada teori graf adalah bridge.Bridge pada graf adalah sebuah edge yang apabila edge tersebut di-hapus maka akan meningkatkan jumlah connected component padasebuah graf. Penulis tertarik melakukan penelitian dalam pemecah-an masalah yang berhubungan dengan teori graf khususnya perma-salahan komputasi jumlah bridge pada graf dinamis.

Permasalahan yang diangkat pada Tugas Akhir ini adalah permasa-lahan komputasi jumlah bridge pada graf yang berubah secara dina-mis karena operasi penambahan edge atau disebut juga graf dinamisinkremental. Diberikan sebuah undirected graph yang terdiri dari Nvertex dan pada awalnya graf tersebut tidak memiliki edge. Selan-jutnya akan dilakukanM operasi penambahan undirected edge yangmenghubungkan antara sebuah vertex dengan vertex lainnya. Untuksetiap operasi penambahan edge diperlukan informasi total jumlahbridge yang terdapat pada graf tersebut. Edge yang ditambahkanuntuk setiap operasi dipastikan bukan merupakan edge yang telahada sebelumnya ataupun edge yang menghubungkan sebuah vertexdengan vertex itu sendiri.

Solusi naif dari permasalahan di atas adalah dengan melakukankomputasi ulang jumlah bridge untuk setiap operasi penambahanedge, namun solusi tersebut sangatlah tidak efisien mengingat jum-lah edge pada graf terus bertambah karena adanya operasi penam-bahan edge. Oleh karena itu, dibutuhkan desain algoritma dan struk-tur data yang efisien baik dalam kecepatan komputasi maupun peng-gunaan memori untuk permasalahan ini.

Hasil dari Tugas Akhir ini diharapkan dapat menentukan implemen-tasi algoritma dan struktur data yang tepat untuk memecahkan per-

3

masalahan di atas secara optimal dan dapat memberikan kontribusiterhadap perkembangan pengetahuan teknologi informasi.

1.2 Rumusan Masalah

Rumusan masalah yang diangkat dalam Tugas Akhir ini adalah se-bagai berikut:

1. Bagaimana menganalisis dan menentukan algoritma danstruktur data yang tepat untuk menyelesaikan permasalahankomputasi jumlah bridge pada graf dinamis inkremental de-ngan optimal.

2. Bagaimana implementasi dari algoritma dan struktur datayang dirancang dalam penyelesaian permasalahan komputasijumlah bridge pada graf dinamis inkremental.

3. Bagaimana hasil kinerja dari implementasi algoritma danstruktur data yang dirancang dalam penyelesaian permasalah-an komputasi jumlah bridge pada graf dinamis inkremental.

1.3 Batasan Masalah

Permasalahan yang dibahas pada Tugas Akhir ini memiliki bebera-pa batasan, yaitu sebagai berikut:

1. Batas maksimum jumlah vertex awal pada graf adalah 50.000vertex.

2. Batas maksimum jumlah operasi penambahan edge adalah100.000 operasi.

3. Edge yang ditambahkan pada graf dipastikan bukan edgeyang telah ada sebelumnya ataupun edge yang menghu-bungkan antara sebuah vertex dengan vertex itu sendiri.

1.4 Tujuan

Tujuan dari Tugas Akhir ini adalah sebagai berikut:

4

1. Melakukan analisis dan desain algoritma dan struktur datauntuk menyelesaikan permasalahan komputasi jumlah bridgepada graf dinamis inkremental.

2. Mengevaluasi hasil dan kinerja dari algoritma dan struk-tur data yang telah dirancang dalam penyelesaian komputasijumlah bridge pada graf dinamis inkremental.

1.5 Metodologi

Metodologi yang digunakan dalam pengerjaan Tugas Akhir ini ada-lah sebagai berikut:

1. Penyusunan proposal Tugas AkhirPada tahap ini dilakukan penyusunan proposal tugas akhiryang berisi permasalahan dan gagasan solusi yang akan di-teliti pada permasalahan komputasi jumlah bridge pada grafdinamis inkremental.

2. Studi literaturPada tahap ini dilakukan pencarian informasi dan studi litera-tur mengenai pengetahuan atau metode yang dapat digunak-an dalam penyelesaian masalah. Informasi didapatkan darimateri-materi yang berhubungan dengan algoritma dan struk-tur data yang digunakan untuk penyelesaian permasalahanini, materi-materi tersebut didapatkan dari buku maupun in-ternet.

3. DesainPada tahap ini dilakukan desain rancangan algoritma danstruktur data yang digunakan dalam solusi untuk pemecahanmasalah komputasi jumlah bridge graf dinamis inkremental.

4. Implementasi perangkat lunakPada tahap ini dilakukan implementasi atau realiasi dari ran-cangan desain algoritma dan struktur data yang telah diba-ngun pada tahap desain ke dalam bentuk program.

5. Uji coba dan evaluasi

5

Pada tahap ini dilakukan uji coba kebenaran dan uji coba ki-nerja dari implementasi yang telah dilakukan. Pengujian ke-benaran dilakukan pada sistem penilaian daring SPOJ sesu-ai dengan masalah yang dikerjakan untuk diuji apakah luarandari program telah sesuai dengan luaran yang seharusnya. Pe-ngujian kinerja dilakukan dengan cara memberi masukan pa-da implementasi program dengan variasi jumlah vertex danoperasi penambahan edge yang beragam untuk melihat pe-ngaruh masing-masing jumlah vertex dan operasi terhadappertumbuhan waktu eksekusi. Hasil dari uji coba kebenarandan kinerja pada program digunakan sebagai bahan evaluasikesalahan dan juga optimasi kinerja agar performa yang di-dapat lebih optimal.

6. Penyusunan buku Tugas AkhirPada tahap ini dilakukan penyusunan buku Tugas Akhir yangberisi dokumentasi hasil pengerjaan Tugas Akhir.

1.6 Sistematika Penulisan

Berikut adalah sistematika penulisan buku Tugas Akhir ini:

1. BABI: PENDAHULUANBab ini berisi latar belakang, rumusan masalah, batasan ma-salah, tujuan, metodologi dan sistematika penulisan TugasAkhir.

2. BAB II: DASAR TEORIBab ini berisi dasar teori mengenai permasalahan dan algori-tma penyelesaian yang digunakan dalam Tugas Akhir

3. BAB III: DESAINBab ini berisi desain algoritma dan struktur data yang digu-nakan dalam penyelesaian permasalahan.

4. BAB IV: IMPLEMENTASIBab ini berisi implementasi berdasarkan desain algortima danstruktur data yang telah dilakukan pada tahap desain.

6

5. BAB V: UJI COBA DAN EVALUASIBab ini berisi uji coba dan evaluasi dari hasil implementasiyang telah dilakukan pada tahap implementasi.

6. BAB VI: KESIMPULANBab ini berisi kesimpulan yang didapat dari hasil uji cobayang telah dilakukan.

BAB 2

DASAR TEORI

Pada bab ini akan dijelaskan mengenai dasar teori yang menjadi da-sar pengerjaan Tugas Akhir ini.

2.1 Deskripsi Permasalahan

Permasalahan yang diangkat pada Tugas Akhir ini adalah permasa-lahan komputasi jumlah bridge pada graf yang berubah secara dina-mis karena operasi penambahan edge atau disebut juga graf dinamisinkremental. Diberikan sebuah undirected graph yang terdiri dari Nvertex dan pada awalnya graf tersebut tidak memiliki edge. Selan-jutnya akan dilakukanM operasi penambahan undirected edge yangmenghubungkan antara sebuah vertex dengan vertex lainnya. Untuksetiap operasi penambahan edge diperlukan informasi total jumlahbridge yang terdapat pada graf tersebut. Edge yang ditambahkanuntuk setiap operasi dipastikan bukan merupakan edge yang telahada sebelumnya ataupun edge yang menghubungkan sebuah vertexdengan vertex itu sendiri.

Pada Gambar 2.1 diilustrasikan permasalahan di atas dengan jumlahvertex N bernilai 4 dan setiap vertex diberi nomor dari 0 hingga 3dan akan dilakukan operasi penambahan edge dengan jumlah ope-rasi M bernilai 6. Pertama dilakukan operasi penambahan edge(0,2) yang menghubungkan antara vertex 0 dengan vertex 2, operasiini akan membentuk bridge baru karena edge menghubungkan duabuah connected component yang berbeda sehingga jumlah bridgesetelah operasi tersebut adalah 1. Selanjutnya dilakukan operasi pe-nambahan edge(0, 1) dan juga edge (0, 3). Kedua operasi ini juga

7

8

Gambar 2.1: Ilustrasi permasalahan.

masing-masing membentuk sebuah bridge sehingga jumlah bridgepada dua operasi tersebut adalah 2 kemudian 3. Kemudian dilakuanoperasi penambahan edge(2, 3). Operasi ini membentuk cycle an-tara vertex 0, 2 dan 3 sehingga edge yang ada pada cycle tersebutbukan lagi sebuah bridge, jumlah bridge setelah operasi ini adalah 1.Selanjutnya dilakukan operasi penambahan edge(0, 3) yang bukanmerupakan sebuah bridge karena sudah terdapat cycle sebelumnyaantara kedua vertex tersebut. Operasi selanjutnya adalah penam-bahan edge(1, 3) yang menciptakan cycle pada graf dan membuat

9

edge pada cycle tersebut bukan lagi sebuah bridge, jumlah bridge diakhir ilustrasi ini adalah 0. Edge yang berwarna merah pada Gam-bar 2.1 menandakan edge tersebut merupakan sebuah bridge, se-dangkan edge berwarna hitam berarti vertex-vertex yang terhubungtergabung dalam sebuah cycle.

2.2 Strategi Penyelesaian Permasalahan

Solusi naif dari permasalahan ini adalah dilakukan komputasi ulangjumlah bridge untuk setiap operasi penambahan edge dengan caramencoba menghapus setiap edge yang ada lalu memeriksa apakahgraf tersebut masih terhubung dengan cara melakukan graf traver-sal. Jika graf tidak terhubung atau jumlah connected componentbertambah dari pada bentuk graf sebelumnya sebelum edge dihapusmaka edge tersebut merupakan sebuah bridge. Percobaan pengha-pusan edge ini dilakukan untuk setiap edge pada graf dan diulangiuntuk setiap operasi pertambahan edge. Performansi metode naifuntuk permasalahan ini membutuhkan waktu eksekusi yang kurangefisien dengan kompleksitas O(M2(N +M)).

Alternatif lain yang dapat dilakukan adalah dengan menggunak-an algoritma Bridge-finding [2] yang sudah cukup terkenal untuksetiap operasi yang dilakukan dengan cara melakukan depth-first-search (DFS) traversal pada graf. Pada saat dilakukanDFS traversaledge(u, v) (dimisalkan u adalah parent dari v) dikatakan bridge apa-bila tidak ada path alternatif lain untuk mencapai u atau ancestor da-ri u dari subtree dengan v sebagai root. Ilustrasi dari komputasi jum-lah bridge pada suatu graf menggunakan algoritma Bridge-Findingdiilustrasikan pada Gambar 2.2. Algoritma ini dijalankan untuk se-tiap operasi penambahan edge untuk mengetahui jumlah bridge pa-da setiap operasi. Pendekatan metode ini untuk menyelesaikan per-masalahan di atas masih memiliki kompleksitas O(M(N + M))yang masih belum cukup efisien.

10

Gambar 2.2: Ilustrasi komputasi jumlah bridge menggunakan algoritmaBridge-Finding.

Pada kasus komputasi jumlah bridge pada graf dinamis inkremen-tal, solusi yang lebih efisien bisa didapatkan denganmemperhatikanbeberapa kondisi ketika terjadi operasi penambahan edge [3].

Dimisalkan bridge-block adalah connected component yang terben-tuk apabila seluruh bridge pada graf dihapus seperti yang dijelaskanpada Gambar 2.3, terdapat tiga kondisi yang harus diperhatikan un-tuk setiap operasi pendambahan edge(u, v) yaitu:

1. Vertex u dan v berada pada himpunan connected componentyang berbeda.

11

2. Vertex u dan v berada pada himpunan bridge-block yang ber-beda namun tergabung dalam himpunan connected compo-nent yang sama.

3. Vertex u dan v berada pada himpunan bridge-block yang sa-ma.

Gambar 2.3: Ilustrasi bridge, dan bridge-block.

Gambar 2.4: Ilustrasi penambahan edge(u, v) dengan u dan v berada padaconnected component yang berbeda.

Jika u dan v berada pada himpunan connected component yang ber-beda seperti yang diilustrasikan pada Gambar 2.4, maka edge yangditambahkan adalah bridge dan vertex u dan v akan tergabung da-lam himpunan connected component yang sama tetapi masih dalamhimpunan bridge-block yang berbeda karena belum terdapat cycleantara u dan v.

Jika vertex u dan v berada pada himpunan bridge-block yang berbe-da namun tergabung dalam himpunan connected component yangsama, maka edge tersebut akan membentuk cycle baru yang akanmengurangi jumlah bridge pada graf. Semua bridge-block yang

12

Gambar 2.5: Ilustrasi penambahan edge(u, v) dengan u dan v berada pa-da bridge-block yang berbeda namun dalam connected component yangsama.

berada di antara path(u, v) akan tergabung menjadi satu bridge-block yang sama dan semua bridge yang terdapat di antara path(u,v) bukan lagi sebuah bridge. Kondisi ini diilustrasikan pada Gam-bar 2.5.

Jika vertex u dan v berada pada himpunan bridge-block yang sa-ma maka tidak ada perubahan yang terjadi pada struktur data begitujuga dengan jumlah bridge pada graf karena sudah ada cycle yangterjadi sebelumnya antara path(u, v).

Dari pendekatan metode penyelesaian di atas, operasi-operasi yangakan dilakukan adalah:

1. Menentukan apakah dua buah vertex terdapat dalam himpun-an connected component yang sama atau tidak.

2. Menentukan apakah dua buah vertex terdapat dalam himpun-an bridge-block yang sama atau tidak.

13

3. Mendapatkan path antara bridge-block yang saling terhu-bung.

4. Menggabungkan dua himpunan connected component men-jadi satu himpunan.

5. Menggabungkan beberapa himpunan bridge-block menjadisatu himpunan.

Untuk mendukung operasi di atas bisa digunakan struktur data de-ngan bantuan disjoint set yang menyimpan himpunan bridge-blockdan connected component dari suatu vertex dan penerapan LowestCommon Ancestor untuk mendapatkan path antara bridge-blockyang saling terhubung dalam sebuah connected component. De-ngan pendekatan heuristik union by weight dan path-compressionpada disjoint set, pendekatan penyelesaian di atas memiliki kom-pleksitas waktu amortized O(M(α(N))) dimana α(N) adalah in-vers dari fast-growing ackermann function dan bernilai ≤ 4 untuksetiap N [4]. Kompleksitas dari pendekatan penyelesaian ini sudahmemiliki ekspektasi waktu eksekusi yang cukup efisien.

2.3 Disjoint Set

Disjoint set adalah struktur data yang merepresentasikan kumpulandari himpunan objek yang saling lepas [2]. Disjoint set digunakanuntuk mengetahui himpunan terkait dari suatu objek. Pada dasarnyadisjoint set mendukung tiga operasi dasar, yaitu:

• Make-Set: Membuat sebuah objek baru yang tidak terkait de-ngan himpunan yang sudah ada sebelumnya.

• Find-Set: Menentukan himpunan terkait dari suatu objek.• Union: Menggabungkan dua buah himpunan menjadi satu.

Penerapan disjoint set pada graf dilakukan dengan cara setiap ver-texmemiliki parent yangmerujuk pada himpunan terkait dari vertextersebut. Setiap himpunan pada disjoint set direpresentasikan olehsalah satu anggota dari himpunan tersebut untuk selanjutnya disebut

14

root. Himpunan dari suatu vertex diketahui dengan cara menelusu-ri parent pointer hingga mencapai root. Proses penggabungan duabuah himpunan menjadi satu dilakukan dengan cara menjadikan sa-lah satu vertex pada himpunan menjadi parent dari root himpunanyang lain.

Terdapat dua pendekatan heuristik yang bisa diterapkan pada dis-joint set untuk mendapatkan kinerja waktu yang lebih optimal. Pen-dekatan heuristik yang pertama adalah dengan melihat karakteristikkedua himpunan ketika akan dilakukan proses penggabungan. Sa-lah satu metode pada pendekatan ini adalah union by weight. Padaunion by weight penggabungan dua himpunan akan melihat ukur-an dari kedua himpunan. Root dari himpunan dengan ukuran yanglebih kecil akan menjadi child dari node pada himpunan denganukuran yang lebih besar. Pendekatan heuristik yang kedua adalahpath-compression. Seperti yang diilustrasikan pada Gambar 2.6 ke-tika proses Find-set terjadi maka setiap vertex yang ada dalam pa-th dari vertex awal menuju root pada akhirnya akan merujuk padaroot dari tree. Dengan menggunakan kedua pendekatan heuristikunion by weight dan path-compressionmaka kompleksitas dari dis-joint-set untuk setiap operasi Find-Set dan Union adalah amortizedα(M,N) dimana α(M,N) adalah invers dari fast-growing acker-mann function dan bernilai ≤ 4 untuk setiap N [4].

Gambar 2.6: Path-compression pada disjoint set.

Aplikasi dari disjoint set pada permasalahan ini adalah untuk me-

15

ngetahui himpunan bridge-block dan connected component dari se-buah vertex. Pada Gambar 2.7 diilustrasikan inisialisasi dari sebuahgraf yang awalnya tidak memiliki edge dan representasi disjoint setbridge-block dan connected component dari graf.

Gambar 2.7: Ilustrasi disjoint set dari graf pada permasalahan.

Parent sets pada ilustrasi merupakan disjoint set dari connectedcomponent tanpa path-compression. Parent sets dibutuhkan keti-ka proses penggabungan beberapa bridge-block menjadi satu aki-bat terbentuknya cycle dan mengakibatkan berkurangnya jumlahbridge. Parent sets menjaga struktur hubungan antara bridge-block.

Seperti yang telah dijelaskan pada subbab 2.2 ketika terjadi prosespenambahan edge maka akan dilihat bridge-block root dari keduavertex. Jika kedua vertex tidak dalam bridge-block yang samamakaakan dilihat connected component root dari kedua vertex. Jika ke-dua vertex tidak dalam connected component yang sama maka edgetersebut adalah bridge dan vertex dengan ukuran connected compo-nent yang lebih kecil akan menjadi root dari himpunan connected

16

Gambar 2.8: Ilustrasi penambahan bridge dan representasi pada disjointset (1).

component. Untuk mengetahui bridge-block dan connected compo-nent terkait dari suatu vertex digunakan operasi dasar Find-set pa-da disjoint set dengan tambahan path-compression untuk connectedcomponent sets dan bridge-block sets namun tidak pada parent se-ts. Proses menjadikan vertex sebagai root dari himpunan connectedcomponent dilakukan dengan caramembalikkan arah pointer parentpada parent sets dan connected component sets dari semua bridge-block root yang ada dalam path dari bridge-block root vertex terse-but ke root dari connected component. Untuk mengetahui bridge-block selanjutnya dalam path menuju root connected componentmaka akan dilihat parent dari vertex tersebut pada parent sets. Sete-lah menjadi root dari himpunan connected-componentmaka parentpada parent sets dan connected component sets dari vertex tersebutadalah bridge-block root dari vertex dengan ukuran himpunan con-nected-component yang lebih besar. Ilustrasi dari kondisi di atasdigambarkan juga pada Gambar 2.9, 2.10, 2.11 dan 2.12.

17



18



Pada saat penambahan edge(1, 4) seperti yang ditunjukkan pada

19

Gambar 2.11 dan 2.12. Vertex 1 memiliki ukuran himpunan con-nected component yang lebih kecil dibandingkan dengan ukuranhimpunan connected component dari vertex 4. Ukuran himpunandapat diketahui dengan melihat nilai ukuran subtree dari disjoint setyang disimpan pada root dari set. Pada kondisi ini juga dilakukanpath-compression pada disjoint set sehingga vertex 4 langsung me-rujuk pada vertex 2 yang merupakan root dari himpunan connectedcomponent sedangkan vertex 1 sebelumnya sudah langsung meru-juk pada root dari connected component yaitu vertex 0. Vertex 1yang memiliki ukuran himpunan connected component lebih kecilterlebih dahulu akan menjadi root dari himpunan connected compo-nent. Proses ini dilakukan dengan cara membalikkan arah pointerparent pada parent sets dan connected component sets dari semuabridge-block root yang ada dalam path dari bridge-block root ver-tex tersebut ke root dari connected component (Gambar 2.11). Se-telah vertex 1 telah menjadi root dari himpunan connected compo-nent maka root bridge-block dari vertex dengan ukuran himpunanconnected component yang lebih besar yaitu vertex 4 akan menjadiparent dari vertex 1 pada connected component sets dan parent sets(Gambar 2.12).

2.4 Lowest Common Ancestor (LCA)

LCA adalah sebuah konsep dalam teori graf dan ilmu komputer.LCA antara dua vertex u dan v adalah vertex terjauh dari tree T yangmemiliki u dan v sebagai keturunan [5]. LCA dalam aplikasinyadapat digunakan untukmencapai titik temu terdekat antara dua buahvertex dalam sebuah tree. Pada Gambar 2.13 diilustrasikan bahwavertex e adalah LCA antara vertex h dan i dalam sebuah tree.

Aplikasi dari LCA pada permasalahan ini adalah ketika prosespenggabungan beberapa bridge-block menjadi satu akibat dari ter-bentuknya cycle ketika penambahan edge. Semua bridge-blockyang berada di antara path kedua vertex akan tergabung menjadi sa-

20

Gambar 2.13: Contoh ilustrasi LCA dari 2 vertex.

tu bridge-block dan semua bridge yang terdapat di antara path terse-but bukan lagi sebuah bridge. Untuk mengetahui bridge-block yangada dalam path antara kedua vertex maka dicari LCA antara keduavertex. Pencarian LCA pada kasus ini dilakukan dengan cara keduavertex mencari bridge-block root lalu melihat ke arah bridge-blockselanjutnya dengan cara melihat parent dari vertex tersebut pada pa-rents set. Kemudian dari parent tersebut mencari lagi bridge-blockroot dan proses ini berjalan terus menerus hingga mencapai titiktemu antara kedua vertex. Titik temu ini adalah LCA dari keduavertex dan parent bridge-block dari semua bridge-block yang telahdilewati sebelumnya akan merujuk pada LCA.

Pada Gambar 2.14 dan 2.15 diilustrasikan operasi penambahanedge(0, 2) yang akan membentuk cycle. LCA antara bridge-blockvertex 0 dan 2 adalah vertex 2. Semua bridge-block parent yang adadalam path ini yaitu vertex 0, 1, 4, 3 dan 2 akan merujuk pada LCAyaitu vertex 2 (Gambar 2.15).

21

Gambar 2.14: Ilustrasi cycle dan penerapan LCA pada permasalahan (1).

Gambar 2.15: Ilustrasi cycle dan penerapan LCA pada permasalahan (2).

22

2.5 Permasalahan Online Bridge Searching pada SPOJ

Pada situs penilaian daring SPOJ terdapat permasalahan komputa-si jumlah bridge pada graf secara online dengan judul soal OnlineBridge Searching dan kode soal ONBRIDGE [6]. Deskripsi perma-salahan ditunjukkan pada Gambar 2.16.

Gambar 2.16: Deskripsi permasalahan Online Bridge Searching di SPOJ.

Deskripsi singkat dari persoalan tersebut ialah diberikan sebuahundirected graph yang terdiri dari N buah vertex dan pada awalnyagraf tersebut tidak memiliki edge. Pada graf tersebut akan dilakuk-an M operasi penambahan undirected edge yang menghubungkanantara sebuah vertex dengan vertex lainnya. Untuk setiap opera-si penambahan edge dibutuhkan informasi total jumlah bridge yangterdapat pada graf tersebut. Edge yang ditambahkan dipastikan buk-an merupakan edge yang telah ada sebelumnya ataupun edge yangmenghubungkan sebuah vertex dengan vertex itu sendiri.

Berikut merupakan format masukan yang diminta dari permasalah-an:

23

1. Baris pertama terdiri dari sebuah bilangan integer T yang me-representasikan banyaknya kasus uji

2. Untuk setiap kasus uji terdapat dua buah integer N dan Myang menyatakan banyaknya vertex pada graf dan jumlahoperasi penambahan edge yang akan dilakukan.

3. M baris selanjutnya adalah berisi pasangan U dan V yang me-representasikan dua buah vertex yang mengalami penambah-an edge.

Format keluaran dari permasalahan tersebut adalah sebuah integeryang merepresentasikan jumlah bridge pada graf untuk setiap ope-rasi penambahan edge.

Batasan permasalahan yang diberikan adalah sebagai beri-kut:

1. T ≤ 102. 1 ≤ N ≤ 500003. 1 ≤ M ≤ 1000004. 0 ≤ u, v ≤ N − 1

Program akan diuji pada cluster Cube (Intel Pentium G860 3GHz)dengan batasan waktu eksekusi 0.140s, batasan kapasitas memorysebesar 1536MB dan batasan kode sumber sebesar 50000B.

Pada deskripsi soal tersebut dijelaskan juga contoh masukan dankeluaran yang akan digunakan sesuai dengan format masukan dankeluaran yang telah dijelaskan. Contoh masukan dan keluaran yangdiberikan digambarkan pada Gambar 2.17.

Untuk menyelesaikan permasalahan pada contoh maka akan diba-ngun struktur data dan melihat kondisi vertex yang mengalami per-tambahan edge seperti yang telah dijelaskan pada subbab 2.2.

Pada contoh masukan pertama dilakukan operasi penambahanedge(3, 0) yang menghubungkan antara vertex 3 dengan vertex0, operasi ini akan membentuk bridge baru karena edge menghu-

24

Gambar 2.17: Contoh masukan dan keluaran pada soal Online Bridge Se-arching.

bungkan dua buah connected component yang berbeda sehinggajumlah bridge setelah operasi tersebut adalah 1. Selanjutnya dila-kukan operasi penambahan edge(0, 2) dan juga edge (1, 0). Ke-dua operasi ini juga masing-masing memiliki kondisi yang samadengan kondisi sebelumnya dengan membentuk sebuah bridge se-hingga jumlah bridge daripada dua urutan operasi tersebut adalah 2kemudian 3. Ketiga operasi penambahan bridge ini diilustrasikanpada Gambar 2.18.

Gambar 2.18: Ilustrasi operasi yang menghasilkan bridge pada contohpermasalahan.

Ilustrasi disjoint set dari kondisi graf setelah dilakukan ketiga ope-

25

rasi di atas digambarkan pada Gambar 2.19.

Gambar 2.19: Ilustrasi disjoint set pada contoh permasalahan.

Kemudian dilakuan operasi penambahan edge(1, 3). Operasi inimenghubungkan dua buah vertex yang berada pada bridge-blockyang berbeda namun terhimpun dalam connected component yangsama sehingga membentuk cycle antara vertex 0, 1 dan 3. Operasiini mengakibatkan edge yang ada dalam path cycle tersebut bukanlagi sebuah bridge. Untuk mendapatkan path antara bridge-blockyang sebelumnya sudah berada dalam sebuah connected compo-nent yang sama maka dilakukan pencarian LCA bridge-block darimasing-masing vertex seperti yang telah dijelaskan pada subbab 2.2.Pada awalnya kedua vertex akan melihat pada bridge-block rootmasing-amsing lalu untuk mendapatkan vertex selanjutnya yang ha-rus dikunjungi akan dilihat pada parent sets dari vertex tersebut.Proses ini terus dilakukan hingga mencapai titik temu antara keduavertex. Setelah didapatkan LCA maka bridge-block yang telah di-kunjungi dalam proses ini pada akhirnya akan merujuk pada LCAdan jumlah bridge akan berkurang sebanyak jumlah bridge-blockyang mengarah ke LCA kecuali LCA itu sendiri. Jumlah bridge se-

26

Gambar 2.20: Ilustrasi operasi yang menggabungkan beberapa bridge-block dan menghapus bridge pada contoh permasalahan.

telah operasi ini adalah 1. Ilustrasi struktur disjoint set pada operasidi atas digambarkan pada Gambar 2.21 dan 2.22.

Gambar 2.21: Ilustrasi disjoint set dan LCA saat pembentukan cycle (1).

27

Gambar 2.22: Ilustrasi disjoint set dan LCA saat pembentukan cycle (2).

Operasi penambahan edge(1, 4) membentuk sebuah bridge karenavertex 1 dan 4 berada pada himpunan connected component yangberbeda. Karena vertex 4 memiliki ukuran himpunan connectedcomponent yang lebih kecil daripada vertex 1 maka vertex 4 akanmerujuk pada bridge-block root dari vertex 1 yaitu vertex 0. To-tal bridge setelah operasi ini adalah 2. Ilustrasi dari operasi di atasdigambarkan pada Gambar 2.23.

Operasi penambahan edge(2, 4) membentuk cycle pada graf yangmembuat edge pada cycle tersebut bukan lagi sebuah bridge, se-hingga jumlah bridge setelah operasi ini adalah 0. Ilustrasi strukturdata disjoint set setelah operasi penambahan edge(2, 4) digambark-an pada Gambar 2.24.

Operasi penambahan edge(4, 0), edge(2, 1), edge(2,3), dan edge(3,4) menghubungkan vertex yang sudah tergabung dalam bridge-block yang sama sehingga tidak mempengaruhi jumlah bridge padagraf. Kondisi akhir dari graf dan struktur data pada akhir operasidigambarkan pada Gambar 2.25.

28

Gambar 2.23: Ilustrasi graf dan disjoint set setelah operasi penambahanedge(1, 4).

Gambar 2.24: Ilustrasi graf dan disjoint set setelah operasi penambahanedge(2, 4).

29

Gambar 2.25: Ilustrasi kondisi akhir dari graf dan disjoint set pada contohkasus Online Bridge Searching.

2.6 Pembuatan Data Generator untuk Uji Coba

Pembuatan data generator dilakukan untuk membuat kasus uji yangakan digunakan untuk pengujian pada uji coba yang akan dijelaskanpada bab 5. Data generator ini disesuaikan dengan format masukanyang sudah dijelaskan pada subbab 2.5.

Terdapat 2 skenario yang akan dilakukan untuk uji coba, skenariotersebut ialah pengaruh jumlah vertex terhadap waktu dan pengaruhjumlah operasi pertambahan edge terhadap waktu. Untuk skenariopertama akan dibuat data generator dengan banyak jumlah operasitetap dan jumlah vertex dari 1.000 hingga 50.000 dengan rentang1.000. Pseudocode dari data generator untuk skenario pertama da-pat dilihat pada Gambar 2.26.

Untuk skenario kedua akan dibuat data generator dengan banyakjumlah vertex tetap dan jumlah operasi dari 2.000 hingga 100.000dengan rentang 2.000. Pseudocode dari data generator untuk ske-nario kedua dapat dilihat pada Gambar 2.27.

30

1 let used[0..MAXN][0..MAXN] be a new array2 A = 503 for a = 1 to A4 T = 105 for i = 0 toMAXN6 for j = 0 toMAXN7 used[i][j] = false8 N = a ∗ 10009 M = 100000 // constant M value10 for t = 1 to T11 writeToF ile(N)12 writeToF ile(M)13 for i = 1 toM14 u = rand()15 v = rand()16 while used[u][v] is true17 u = rand()18 v = rand()19 writeToFile(u)20 writeToFile(v)

Gambar 2.26: Pseudocode Fungsi Main Generator Skenario Uji 1

31

1 let used[0..MAXN][0..MAXN] be a new array2 A = 503 for a = 1 to A4 T = 105 for i = 0 toMAXN6 for j = 0 toMAXN7 used[i][j] = false8 N = 50000 // constant N value9 M = a ∗ 200010 for t = 1 to T11 writeToF ile(N)12 writeToF ile(M)13 for i = 1 toM14 u = rand()15 v = rand()16 while used[u][v] is true17 u = rand()18 v = rand()19 writeToFile(u)20 writeToFile(v)

Gambar 2.27: Pseudocode Fungsi Main Generator Skenario Uji 2

32


BAB 3

DESAIN

Pada bab ini akan dijelaskan desain sistem yang digunakan untukmenyelesaikan permasalahan pada Tugas Akhir ini.

3.1 Deskripsi Umum Sistem

Sistem akan menerima masukan jumlah kasus uji. Untuk setiapkasus uji, sistem akan menerima masukan jumlah vertex, jumlahedge dan rangkaian pasangan vertex yang mengalami penambahanedge.

1 let node[0..MAXN] be a new array2 T = Input() // Total testcase3 for t = 1 to T4 N = Input() // Total vertex in the graph5 M = Input() // Total add edge operation6 bridge = 07 for i = 0 to N − 18 Init(node[i])9 for i = 0 toM − 110 u = Input()11 v = Input()12 InsertEdge(u, v) // Edge added between u and v13 Print(bridge)

Gambar 3.1: Pseudocode Fungsi Main

33

34

Pada awalnya sistem akan menginisialisasi nilai dari kelas nodeyangmerupakan representasi vertex pada graf. Untuk setiap masuk-an penambahan edge terhadap pasangan vertex sistem akan menja-lankan fungsi InsertEdge(u, v) yang akan melakukan penambahanedge dan komputasi jumlah bridge lalu menampilkan luaran jum-lah bridge yang terdapat pada graf. Pseudocode Fungsi Main ditun-jukkan pada Gambar 3.1.

3.2 Desain Kelas Node dan Fungsi Init

KelasNodemerepresentasikan vertex pada graf. Nodememiliki po-inter yang akan merujuk pada parent dari vertex, pointer yang akanmerujuk pada himpunan bridge-block parent dari vertex dan poin-ter yang akan merujuk pada himpunan connected component darivertex. Node juga menyimpan nilai ukuran connected componentyang tergabung dengan vertex tersebut dan nilai counter yang ak-an digunakan untuk penomoran vertex ketika proses penggabung-an bridge-block. Pseudocode Fungsi Init ditunjukkan pada Gambar3.2

1 u.parent = NULL2 u.bParent = u3 u.cParent = u4 u.cSize = 15 u.counter = 0

Gambar 3.2: Pseudocode Fungsi Init

Fungsi Init akan mengatur nilai inisialisasi node. Pada tahap inisia-lisasi awal, nilai pointer parent akan merujuk pada NULL. Pointerbridge-block dan connected component akan merujuk pada node itusendiri yangmenandakan bahwa vertex tersebut merupakan root da-ri himpunan bridge-block dan connected component node tersebut.

35

Nilai ukuran connected component bernilai satu dan nilai counteruntuk inisialisasi bernilai nol.

3.3 Desain Fungsi InsertEdge

Fungsi InsertEdge menerima dua parameter u dan v yaitu vertexyang mengalami pertambahan edge. Fungsi InsertEdge akan me-lihat kondisi pasangan vertex u dan v sebelum mengalami pertam-bahan edge sesuai dengan kondisi yang telah dijelaskan pada subbab2.2 . Pseudocode dari Fungsi InsertEdge dijelaskan pada Gambar3.3.

1 bU = FindBridgeBlock(u)2 bV = FindBridgeBlock(v)3 if bU == bV4 return5 else cU = FindComponent(u)6 cV = FindComponent(v)7 if cU == cV8 MergeBridgeBlock(bU, bV )9 else bridge = bridge+ 110 if cU.cSize < cV.cSize11 SetRoot(bU)12 bU.parent = bV13 bU.cParent = bV14 cV.cSize = cV.cSize+ cU.cSize15 else SetRoot(bV)16 bV.parent = bU17 bV.cParent = bU18 cU.cSize = cU.cSize+ cV.cSize

Gambar 3.3: Pseudocode Fungsi InsertEdge

36

3.4 Desain Fungsi FindBridgeBlock

Fungsi FindBridgeBlock akan memberikan nilai kembali berupahimpunan bridge-block dari node. Himpunan bridge-block dida-patkan dengan cara menelusuri arah bridge-block parent dari nodehingga bridge-block parent dari sebuah node adalah node itu sendi-ri. Agar lebih optimal dilakukan juga path compresssion pada struk-tur data disjoint set yang merepresentasikan himpunan bridge-blockdengan cara menghubungkan langsung setiap node yang dikunjungidalam proses ini dengan root dari himpunan bridge-block. Pseudo-code Fungsi FindBridgeBlock ditunjukkan pada Gambar 3.4

1 if u == u.bParent2 return u3 else u.bParent = FindBridgeBlock(u.bParent)4 return u.bParent

Gambar 3.4: Pseudocode Fungsi FindBridgeBlock

3.5 Desain Fungsi FindComponent

Fungsi FindComponent akan memberikan nilai kembali berupahimpunan connected component dari node. Himpunan connectedcomponent didapatkan dengan cara menelusuri arah connectedcomponent parent dari node hingga bridge-block parent dari sebu-ah node adalah node itu sendiri. Pada fungsi ini juga dilakukan pathcompresssion pada struktur data disjoint set yang merepresentasik-an himpunan connected component, setiap node yang dilewati padaakhirnya akan merujuk ke root dari connected component. Pseudo-code Fungsi FindComponent ditunjukkan pada Gambar 3.5

37

1 uB = FindBridgeBlock(u)2 if uB == uB.cParent3 return uB4 else uB.cParent = FindBridgeBlock(uB.cParent)5 return uB.cParent

Gambar 3.5: Pseudocode Fungsi FindComponent

3.6 Desain Fungsi SetRoot

Fungsi SetRoot akan menjadikan node tersebut sebagai root darihimpunan connected component dengan cara mengubah arah par-ent pointer mengarah ke child berlaku untuk setiap node yang di-kunjungi antara path node tersebut dengan root. Pseudocode FungsiSetRoot ditunjukkan pada Gambar 3.6

1 now = FindBridgeBlock(u)2 root = u3 child = NULL4 while now ̸= NULL5 if now.parent ̸= NULL6 next = FindBridgeBlock(now.parent)7 else next = NULL8 now.parent = child9 now.cParent = root10 child = now11 now = next12 root.cSize = child.cSize

Gambar 3.6: Pseudocode Fungsi SetRoot

38

3.7 Desain Fungsi MergeBridgeBlock

Fungsi MergeBridgeBlock menerima dua parameter u dan v yangmerupakan vertex yang mengakibatkan terbentuknya cycle akibatpenambahan edge di antara kedua vertex tersebut. Fungsi Merge-BridgeBlock akan menggabungkan bridge-block yang terdapat da-lam path(u, v) menjadi satu bridge-block. Proses menggabungk-an bridge-block ini akan menghapus bridge yang berada di anta-ra path(u, v). Penggabungan bridge-block dilakukan dengan caramencari LCA dari bridge-block yang ada dalam path(u, v) dan se-luruh himpunan bridge-block yang dikunjungi pada akhirnya akanmerujuk pada LCA. Jumlah bridge pada proses ini akan berkurangsebanyak jumlah bridge-block yang dilewati dalam path(u, v) kecu-ali LCA. Pseudocode Fungsi MergeBridgeBlock ditunjukkan padaGambar 3.7

1 lca = LCA(u, v)2 for each node ∈ path(u, v)3 if node ̸= lca4 node.bParent = lca5 bridge = bridge− 1

Gambar 3.7: Pseudocode Fungsi MergeBridgeBlock

BAB 4

IMPLEMENTASI

Pada bab ini akan dijelaskan implementasi dari algoritma dan struk-tur data berdasarkan desain yang telah dilakukan.

4.1 Lingkungan Implementasi

Lingkungan implementasi dan pengembangan yang dilakukan ada-lah sebagai berikut:

1. Perangkat Keras• Processor Intel Core i3-2120 CPU @ 3.30GHz x 2.• Memory 7.7 GB.

2. Perangkat Lunak• Sistem operasi Linux Mint 17.3 Rosa Cinnamon 64-bit.• Integrated Development Environment Code::Blocks13.12.

4.2 Implementasi Fungsi Main

Fungsi Main diimplementasikan sesuai pseudocode subbab 3.1. Pa-da awalnya sistem akan mendeklarasikan variabel-variabel yang di-butuhkan dan melakukan inisialisasi nilai dari struct node yang me-rupakan representasi vertex pada graf. Untuk setiap masukan pe-nambahan edge terhadap pasangan vertex sistem akan menjalankanfungsi InsertEdge(u, v) yang akanmelakukan penambahan edge dankomputasi jumlah bridge lalu menampilkan luaran berupa jumlahbridge yang terdapat pada graf. Didefenisikan juga makro scanIntsebagai metode input yang lebih cepat dari scanf. Implementasi dariFungsi Main dapat dilihat pada Kode Sumber 4.1.

39

40

1 # de f i n e s c a n I n t ( a ) do c= g e t c h a r _ u n l o c k e d ( ) ; \2 whi le ( c <48 ) ; \3 f o r ( a =0; c >=48; c= g e t c h a r _ u n l o c k e d ( ) ) a=a *10+c−48;45 i n t main ( ) {6 i n t t , m, u , v ; char c ;7 l a b e l C o u n t e r = 0 ;8 s t r u c t Node node [ 5 0 0 0 0 ] ;9 s c a n I n t ( t ) ;10 whi le ( t−−) {11 b r i d g e = 0 ;12 s c a n I n t ( n ) ; s c a n I n t (m) ;13 f o r ( i n t i =0 ; i <=n−1; i ++) {14 node [ i ] . r e s e t ( ) ;15 }16 f o r ( i n t i =1 ; i <=m; i ++) {17 s c a n I n t ( u ) ; s c a n I n t ( v ) ;18 node [ u ] . i n s e r t E d g e (&node [ v ] ) ;19 p r i n t f ( ”%d \ n” , b r i d g e ) ;20 }21 }22 re turn 0 ;23 }

Kode Sumber 4.1: Implementasi Fungsi Main

4.3 Implementasi Variabel Global

1 i n t n , b r i dge , l a b e l C o u n t e r ;

Kode Sumber 4.2: Implementasi Variabel Global

Variabel dengan scope global dibutuhkan untuk kemudahan pe-ngaksesan sebuah variabel oleh setiap fungsi yang inginmengakses-nya. Penggunaan variabel global pada implementasi ini diterapkanpada variabel bridge yang merepresentasikan jumlah bridge graf,variabel n yang merepresentasikan jumlah vertex pada graf dan juga

41

variabel labelCounter yang akan digunakan untuk pelabelan vertexsaat mencari LCA dari dua bride-block dalam satu himpunan con-nected component. Implementasi dari variabel global dapat dilihatpada Kode Sumber 4.2.

4.4 Implementasi Struct Node

Struct Node merupakan implementasi dari desain Kelas Node pa-da subbab 3.2 dan merupakan representasi sebuah vertex v padagraf. Pada Struct Node juga terdapat implementasi algoritma yangdigunakan pada komputasi jumlah bridge. Implementasi dari StructNode dapat dilihat pada Kode Sumber 4.3.

1 s t r u c t Node {2 s t r u c t Node * pa r en t , * bPa ren t , * c P a r e n t ;3 i n t cS ize , l a b e l ;45 void r e s e t ( ) {6 p a r e n t = NULL;7 bPa r e n t = t h i s ;8 c P a r e n t = t h i s ;9 cS i z e = 1 ;10 l a b e l = −1;11 }12 }

Kode Sumber 4.3: Implementasi Struct Node

Pada line 2 dilakukan deklarasi tipe data pointer yang akan disimp-an pada struct node. Pointer Node *parent akan menyimpan nilaipointer dari parent node, pointer *bParent akan menyimpan alamatpointer bridge-block parent dari node dan pointer *cParent akanmenyimpan alamat pointer connected component parent dari node.Pada line 3 dilakukan deklarasi nilai cSize dan nilai label. NilaicSize adalah ukuran himpunan connected component tergabung de-ngan vertex. Sedangkan nilai label akan digunakan sebagai coun-ter saat penggabungan node ketika penambahan edgemenghasilkan

42

cycle.

4.5 Implementasi Fungsi InsertEdge

Fungsi InsertEdge melakukan proses penambahan edge(u, v) de-ngan memperhatikan beberapa kondisi seperti yang telah dijelaskanpada subbab 2.2. Implementasi dari Fungsi InsertEdge dapat dilihatpada Kode Sumber 4.4.

1 void i n s e r t E d g e ( s t r u c t Node *v ) {2 s t r u c t Node *bu = t h i s −>f i n dB r i d g eB l o ck ( ) ;3 s t r u c t Node *bv = v−>f i n dB r i d g eB l o ck ( ) ;4 i f ( bu != bv ) {5 s t r u c t Node *cu = bu−>findComponent ( ) ;6 s t r u c t Node *cv = bv−>findComponent ( ) ;7 i f ( cu == cv ) {8 bu−>mergeBr idgeBlock ( bv ) ;9 }10 e l s e {11 i f ( cu−>cS i z e < cv−>cS i z e ) {12 bu−>s e tRoo t ( ) ;13 bu−>p a r e n t = bv ;14 bu−>cP a r e n t = bv ;15 cv−>cS i z e += bu−>cS i z e ;16 }17 e l s e {18 bv−>s e tRoo t ( ) ;19 bv−>p a r e n t = bu ;20 bv−>cP a r e n t = bu ;21 cu−>cS i z e += bv−>cS i z e ;22 }23 b r i d g e ++;24 }25 }26 }

Kode Sumber 4.4: Implementasi Fungsi InsertEdge

Pada Kode Sumber 4.4 line 2-3 akan mendapatkan himpunan

43

bridge-block dari u dan v. Jika u dan v memiliki bridge-block yangsama maka tidak ada perubahan pada jumlah bridge maupun struk-tur data pada graf. Jika u dan v berada pada bridge-block yangberbeda maka akan dilihat nilai dari connected component masing-masing node u dan v seperti yang dijelaskan pada line 5-6. Jikau dan v terdapat pada himpunan connected component yang samamaka akan dipanggil fungsi mergeBridgeBlock. Jika u dan v bera-da pada himpunan connected component yang berbeda maka edgetersebut adalah bridge dan salah satu dari u atau v akan menjadiroot dari himpunan connected componentnya dan menjadi child da-ri yang lain seperti yang dijelaskan pada line 11-23.

4.6 Implementasi Fungsi FindBridgeBlock

Fungsi FindBridgeBlock memberikan nilai kembali berupa him-punan bridge-block dari vertex tersebut. Implementasi dari FungsiFindBridgeBlock dapat dilihat pada Kode Sumber 4.5.

1 s t r u c t Node* f i n dB r i d g eB l o ck ( ) {2 s t r u c t Node* bPa r e n t = t h i s −>bPa r e n t ;3 i f ( bP a r e n t == t h i s ) re turn t h i s ;4 e l s e {5 t h i s −>bPa r e n t = bPa ren t−>f i n dB r i d g eB l o c k ( ) ;6 re turn th i s −>bPa r e n t ;7 }8 }

Kode Sumber 4.5: Implementasi Fungsi FindBridgeBlock

Kode Sumber 4.5 merupakan implementasi dari path-compressiondisjoint-set pada bridge-block. Jika bParent dari struct node adalahstruct node itu sendiri maka fungsi akan memberikan nilai kemba-li node tersebut. Jika tidak maka fungsi akan mencari lagi secararekursif dan pointer bParent dari setiap node yang dikunjungi akanmengarah pada root dari bridge-block tersebut.

44

4.7 Implementasi Fungsi FindComponent

Fungsi FindComponent memberikan nilai kembali berupa himpun-an connected component dari vertex tersebut. Implementasi dariFungsi FindComponent dapat dilihat pada Kode Sumber 4.6.

1 s t r u c t Node* f indComponent ( ) {2 s t r u c t Node* b = t h i s −>f i n dB r i d g eB l o ck ( ) ;3 i f ( b == b−>cP a r e n t ) re turn b ;4 e l s e {5 b−>cP a r e n t = b−>cPa r en t−>findComponent ( ) ;6 re turn b−>cP a r e n t ;7 }8 }

Kode Sumber 4.6: Implementasi Fungsi FindComponent

4.8 Implementasi Fungsi SetRoot

Fungsi SetRoot akan menjadikan vertex tersebut sebagai root padahimpunan connected component. Implementasi dari Fungsi SetRo-ot dapat dilihat pada Kode Sumber 4.7.

1 void s e tRoo t ( ) {2 s t r u c t Node *now = t h i s −>f i n dB r i d g eB l o ck ( ) ;3 s t r u c t Node * r o o t = t h i s , * c h i l d = NULL;4 whi le ( now ) {5 s t r u c t Node *b ;6 i f ( now−>p a r e n t )7 b = now−>pa r en t−>f i n dB r i d g eB l o ck ( ) ;8 e l s e b = NULL;9 now−>p a r e n t = c h i l d ;10 now−>cP a r e n t = r o o t ;11 c h i l d = now ;12 now = b ;13 }14 roo t−>cS i z e = ch i l d −>cS i z e ;15 }

Kode Sumber 4.7: Implementasi Fungsi SetRoot

45

4.9 Implementasi Fungsi MergeBridgeBlock

Fungsi MergeBridgeBlock menggabungkan bridge-block yang adapada path(u, v) menjadi satu. Implementasi dari Fungsi MergeBri-dgeBlock dapat dilihat pada Kode Sumber 4.8.

1 void mergeBr idgeBlock ( s t r u c t Node *v ) {2 l a b e l C o u n t e r ++;3 s t r u c t Node *pathX [50000 ] , * pathY [ 5 0 0 0 0 ] ;4 i n t xEnd = 0 , yEnd = 0 ;5 s t r u c t Node * l c a = NULL, *x = t h i s , *y = v ;6 whi le ( t rue ) {7 i f ( x ) {8 x = x−>f i n dB r i d g eB l o c k ( ) ;9 pathX [ xEnd++] = x ;10 i f ( x−> l a b e l == l a b e l C o u n t e r ) {11 l c a = x ; break ;12 }13 x−> l a b e l = l a b e l C o u n t e r ;14 x = x−>p a r e n t ;15 }16 i f ( y ) {17 y = y−>f i n dB r i d g eB l o c k ( ) ;18 pathY [ yEnd++] = y ;19 i f ( y−> l a b e l == l a b e l C o u n t e r ) {20 l c a = y ; break ;21 }22 y−> l a b e l = l a b e l C o u n t e r ;23 y = y−>p a r e n t ;24 }25 }26 f o r ( i n t i =0 ; i <xEnd && pathX [ i ] != l c a ; i ++) {27 pathX [ i ]−>bPa r e n t = l c a ; b r i dge −−;28 }29 f o r ( i n t i =0 ; i <yEnd && pathY [ i ] != l c a ; i ++) {30 pathY [ i ]−>bPa r e n t = l c a ; b r i dge −−;31 }32 }

Kode Sumber 4.8: Implementasi Fungsi MergeBridgeBlock

46

Pada fungsi ini akan dilakukan pencarian LCA antara bridge-blockdari u dan v. Karena u dan v berada pada himpunan connected com-ponent yang sama sebelumnya, maka edge yang ditambahkan akanmembentuk cycle dan edge yang ada pada path(u, v) bukan lagi se-buah bridge. Untuk mendapatkan bridge yang ada pada path(u, v)ditelusuri bridge-block parent dimulai dari vertex u dan v. Penca-rian LCA dilakukan dengan cara memberi label setiap bridge-blockyang dikunjungi dan jika terdapat node yang menjadi titik pertemu-an dari penelusuran bridge-block vertex u dan v maka node tersebutadalah LCA, proses ini dijelaskan pada line 6-27. Line 28-39 akanmengarahkan bParent dari setiap node yang telah dikunjungi untukmengarah ke LCA yang telah didapatkan pada proses sebelumnya.Pada proses ini juga akan dilakukan pengurangan nilai bridge padagraf.

BAB 5

UJI COBA DAN EVALUASI

Pada bab ini akan dijelaskan tentang uji coba dan evaluasi dari im-plementasi sistem yang telah dilakukan pada bab 4.

5.1 Lingkungan Uji Coba

Lingkungan uji coba menggunakan sebuah komputer dengan spesi-fikasi perangkat lunak dan perangkat keras sebagai berikut:

• Perangkat Keras:– Processor Intel Core i3-2120 CPU @ 3.30GHz x 2.– Memory 7.7 GB.– 64-bit Operating System, x64 based processor.

• Perangkat Lunak:– Sistem operasi Linux Mint 17.3 Rosa Cinnamon 64-bit.– Integrated Development Environment Code::Blocks13.12.

5.2 Skenario Uji Coba

Pada subbab ini akan dijelaskan skenario uji coba yang dilakukan.Skenario uji coba terdiri dari uji coba kebenaran dan uji coba kiner-ja.

5.2.1 Uji Coba Kebenaran

Uji coba kebenaran dilakukan dengan analisis penyelesaian sebuahcontoh kasus dengan pendekatan penyelesaian yang telah dijelaskanpada subbab 2.2 dengan hasil dari luaran program dan pengumpulan

47

48

berkas kode sumber hasil implementasi ke situs sistem penilaiandaring SPOJ. Permasalahan yang diselesaikan adalahOnline BridgeSearching dengan kode ONBRIDGE.

Kasus yang akan digunakan sebagai bahan uji kebenaran dalam ana-lisis penyelesaian dengan hasil luaran program adalah data uji yangdihasilkan oleh data generator yang telah dijelaskan pada subbab2.6. Hasil data uji dari data generator dengan jumlah 1 kasus uji,jumlah vertex 6 dan jumlah operasi penambahan edge 8 dapat dili-hat pada Gambar 5.1.

16 85 35 41 42 54 23 25 11 3

Gambar 5.1: Contoh kasus uji hasil dari data generator.

Langkah pertama dilakukan inisialisasi node dari sejumlah vertexyang ada pada kasus uji. Tahap inisialisasi dapat dilihat pada Gam-bar 5.2.

Vertex yang mengalami pertambahan edge pada operasi pertamaadalah vertex 5 dan 3. Operasi ini membentuk bridge dan karena ke-dua vertex memiliki ukuran himpunan connected-component yangsama maka salah satu vertex (vertex 5) menjadi parent dari vertexlainnya (vertex 3) pada parent sets dan connected-component sets.Pada operasi ini jumlah bridge bertambah menjadi 1 sehingga pro-gram seharusnya mengeluarkan luaran 1 setelah operasi ini. Ilus-

49

Gambar 5.2: Inisialisasi contoh kasus uji.

trasi dari operasi penambahan edge(5, 3) dijelaskan pada Gambar5.3.

Gambar 5.3: Ilustrasi penambahan edge(5, 3) pada contoh kasus uji.

50

Operasi selanjutnya menambahkan edge antara vertex 5 dan vertex4. Ukuran himpunan connected-component dari vertex 5 saat inilebih besar daripada vertex 4. Sehingga vertex 4 akan menjadik-an dirinya root dari himpunan connected-componentnya dan par-ent dari vertex 4 selanjutnya adalah bridge-block root dari vertex 5yang mana merupakan vertex 5 itu sendiri. Setelah operasi ini jum-lah bridge pada graf bertambah menjadi 2. Operasi penambahanedge antara vertex 1 dan 4 juga membentuk bridge karena 1 memi-liki ukuran himpunan connected-component yang lebih kecil maka1 akan menjadi root dari himpunan connected-componentnya danparent dari 1 selanjutnya adalah vertex 4. Jumlah bridge setelahoperasi ini adalah 3. Penambahan edge antara vertex 2 dan 5 mem-bentuk bridge dan parent dari vertex 2 pada component-sets danparent-sets adalah vertex 5. Jumlah bridge setelah operasi ini men-jadi 4. Ilustrasi dari ketiga operasi di atas dijelaskan pada Gambar5.4, 5.5 dan 5.6.


51



Operasi penambahan edge antara vertex 4 dan 2 akan membentukcycle dikarenakan vertex 4 dan 2 berada pada himpunan connected-component yang sama namun dalam bridge-block yang berbeda.

52

Maka akan dicari LCA antara kedua vertex dengan cara masing-masing vertex mencari bridge-block root masing-masing dan ke-mudian menuju pada bridge-block selanjutnya dengan cara melihatparent dari vertex pada parent sets. Akhirnya didapatkan LCA an-tara kedua vertex tersebut adalah vertex 5 dan semua bridge-blockyang telah dilewati sebelumnya (vertex 4 dan vertex 2) akan meru-juk pada vertex 5 pada bridge-block sets. Edge yang dilewati selamaproses ini bukan lagi sebuah bridge-block sehingga jumlah bridgesetelah operasi ini adalah 2. Operasi penambahan edge antara ver-tex 3 dan 2 juga membentuk cycle. LCA antara kedua vertex iniadalah vertex 5. Karena bridge-block root dari vertex 2 adalah 5maka jumlah bridge yang berkurang pada operasi ini hanya 1 da-ri vertex 3 ke 5. Selanjutnya vertex 3 akan merujuk pada vertex 5pada bridge-block sets. Jumlah bridge setelah operasi ini adalah1. Kedua operasi ini diilustrasikan pada Gambar 5.7, 5.8, 5.9 dan5.10.

Gambar 5.7: Ilustrasi penambahan edge(4, 2) pada contoh kasus uji (1).

53



54


Operasi selanjutnya adalah operasi penambahan edge antara vertex5 dan 1. Operasi ini membentuk cyclemaka edge yang ada di antarapath(1, 5) bukan lagi sebuah bridge. Bridge-block dan edge yangberada di antara path(1, 5) bisa didapatkan dengan mencari LCAantara kedua vertex dengan cara melihat ke arah bridge-block rootdari vertex lalu melihat ke arah parent dari vertex pada himpunanparent sets dan berulang hingga mencapai titik temu antara keduavertex. LCA antara kedua vertex ini adalah vertex 5 dan jumlahbridge yang berkurang adalah 1 dari vertex 1 ke vertex 4. Selanjut-nya vertex 1 akan merujuk pada vertex 5 pada bridge-block sets danjumlah bridge setelah operasi ini adalah 0. Operasi ini digambarkanpada Gambar 5.11 dan 5.12.

Operasi terakhir yaitu penambahan edge antara vertex 1 dan 3 tidakmerubah apapun dari struktur data karena vertex 1 dan 3 sudah ber-ada pada bridge-block dan juga tidak merubah jumlah bridge padagraf. Operasi ini digambarkan pada Gambar 5.13 dan 5.14.

55



56



Dari hasil analisis di atas urutan jumlah bridge untuk setiap opera-si adalah 1, 2, 3 4, 2, 1, 0 dan 0. Kemudian sistem penyelesaiandijalankan dan diberi masukan sesuai dengan contoh kasus uji dari

57

analisis sebelumnya dan hasil dari luaran sistem adalah 1, 2, 3 ,4, 2,1, 0 dan 0 seperti yang terlihat pada Gambar 5.15.

Gambar 5.15: Hasil luaran program pada contoh kasus uji.

Selanjutnya dilakukan juga uji kebenaran dengan mengumpulkanberkas kode sumber ke situs SPOJ dapat dilihat umpan balik sis-tem. Hasil uji kebenaran dan peringkat waktu eksekusi program saatpengumpulan kasus uji pada situs SPOJ ditunjukkan pada Gambar5.16 dan 5.17.

Gambar 5.16: Hasil uji kebenaran pada situs SPOJ.

Dari hasil uji coba yang telah dilakukan kode sumber programmen-dapat umpan balik Accepted. Waktu yang dibutuhkan program ada-lah 0.02 detik danmemori yang dibutuhkan program adalah 3.9MB.

58

Gambar 5.17: Peringkat waktu eksekusi program Online Bridge Sear-ching pada situs SPOJ.

Hal itu membuktikkan bahwa implementasi yang dilakukan telahberhasil menyelesaikan permasalahan komputasi jumlah bridge se-suai dengan batasan-batasan yang telah ditetapkan. Setelah itu di-lakukan pengiriman kode sumber implementasi sebanyak 30 kaliuntuk melihat variasi waktu dan memori yang dibutuhkan program.Grafik hasil uji coba sebanyak 30 kali ditunjukkan dalam Gambar5.18.

Dari hasil pengumpulan kode sebanyak 30 kali, didapat waktu rata-rata program yaitu 0.031 detik dan penggunaan memori rata-ratayang dibutuhkan program yaitu 3.9MB.

5.2.2 Uji Coba Kinerja

Untuk n vertex dan m operasi penambahan edge, algoritma yangditawarkan memiliki kompleksitas waktu O(M(α(N))) Uji cobakinerja dilakukan dengan membuat operasi penambahan edge pa-da graf secara acak sesuai dengan batasan masalah pada subbab2.5. Setelah itu dilakukan komparasi kinerja untuk melihat penga-ruh jumlah vertex dan pengaruh operasi penambahan edge terhadappertumbuhan waktu.

59

5.2.2.1 Pengaruh Jumlah Vertex Terhadap Waktu

Jumlah vertex diatur bervariasi antara 1.000 hingga 50.000 vertexdengan rentang 1.000 dan banyak operasi penambahan edge dibu-at tetap yaitu 25.000, 50.000, 75.000 dan 100.000 untuk melihatperbandingan pengaruh jumlah vertex terhadap pertumbuhan wak-tu dengan jumlah operasi tetap. Hasil uji coba ditunjukkan padaGambar 5.19.

5.2.2.2 Pengaruh Jumlah Operasi Terhadap Waktu

Jumlah operasi penambahan edge diatur bervariasi antara 2.000hingga 100.000 vertex dengan rentang 2.000 dan banyak vertex di-buat tetap yaitu 12.500, 25.000, 37.500 dan 50.000 untuk melihatperbandingan pengaruh jumlah operasi penambahan edge terhadappertumbuhan waktu dengan jumlah vertex tetap. Hasil uji coba di-tunjukkan pada Gambar 5.20.

60

Gam

bar5.18:Grafik

Hasilujipada

situsSPOJsebanyak

30kali.

61

Gam

bar 5.19:Grafik

hasilujicoba

pengaruh

jumlahvertex

terhadap

pertumbuhanwaktu.

62

Gam

bar5.20:Grafik

hasilujicobapengaruh

jumlah

operasiterhadappertum

buhanwaktu.

BAB 6

KESIMPULAN

Pada bab ini akan dijelaskan kesimpulan dari hasil uji coba yangtelah dilakukan.

6.1 Kesimpulan

Dari hasil uji coba yang telah dilakukan terhadap implementasi so-lusi untuk permasalahan komputasi jumlah bridge pada graf dina-mis inkremental dapat diambil kesimpulan sebagai berikut:

1. Penyelesaian permasalahan komputasi jumlah bridge padagraf dinamis inkremental dengan memperhatikan kondisi pa-sangan vertex yang mengalami pertambahan edge denganbantuan struktur data disjoint set dan pendekatan heuristikunion by weight dan path-compression memiliki kompleksi-tas waktu amortized O(M(α(N))) dimana α(N) adalah in-vers dari fast-growing ackermann function dan bernilai ≤ 4untuk setiap N.

2. Informasi himpunan bridge-block dan connected-componentyang terkait pada sebuah vertex dapat dimanfaatkan untukkomputasi jumlah bridge secara online ketika ada modifikasipada graf karena pertambahan edge.

3. Implementasi dari solusi yang ditawarkan pada Tugas Akhirini telah berhasil menyelesaikan permasalahanOnline BridgeSearching sesuai dengan batasan yang telah ditentukan de-ngan cukup optimal.

4. Waktu dan penggunaan memori rata-rata yang diperlukan un-tuk menyelesaikan permasalahan Online Bridge Searching

63

64

dari 30 kali uji coba pada situs SPOJ adalah 0.031 detik danpenggunaan memori sebesar 3.9 MB.

DAFTAR PUSTAKA

[1] D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algo-rithms, CRC Press, 1997

[2] H. T. Cormen, E. C. Leiserson, L. R. Rivest and C. Stein, In-troduction to Algorithms Third Edition, Cambridge, Massa-chusetts: The MIT Press, 2009

[3] J. Westbrook, R. E. Tarjan. Maintaining Bridge-Connectedand Biconnected Components On-line, CRC Press, 1997

[4] Tarjan, Robert E. Efficiency of a Good But Not Linear SetUnion Algorithm, Journal of the ACM, 22(2):215–225, 1975

[5] M. A. Bender, M. Farach-Colton, G. Pemmasani, S. Skiena andP. Sumazin. Lowest Conommon Ancestors in Trees and Di-rected Acyclic Graphs, ACM Press, 2001

[6] SPOJ, ONBRIDGE - Online Bridge Searching, [Online],http://www.spoj.com/problems/ONBRIDGE/en/, diak-ses pada tanggal 22 Desember 2015

65

http://www.spoj.com/problems/ONBRIDGE/en/

66


LAMPIRAN A

HASIL UJI PADA SITUS SPOJ SEBANYAK 30 KALI

Berikut merupakan lampiran hasil uji coba pengumpulan berkas ko-de solusi pada situs SPOJ sebanyak 30 kali dari grafik yang ditam-pilkan pada Gambar 5.18.

Gambar A.1: Hasil uji pada situs SPOJ sebanyak 30 kali (1).

67

68


69


70


LAMPIRAN B

HASIL UJI KINERJA JUMLAH OPERASI M TETAP

Berikut merupakan lampiran hasil uji kinerja dengan nilai jumlahoperasi M tetap dari grafik pada Gambar 5.19.

Tabel B.1: Hasil uji dengan nilai jumlah operasi M tetap 25.000.

No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon1 1000 25000 0.052 2000 25000 0.0593 3000 25000 0.0664 4000 25000 0.0725 5000 25000 0.0786 6000 25000 0.0857 7000 25000 0.0918 8000 25000 0.0979 9000 25000 0.10210 10000 25000 0.10711 11000 25000 0.11112 12000 25000 0.11613 13000 25000 0.11914 14000 25000 0.12115 15000 25000 0.12316 16000 25000 0.12517 17000 25000 0.12518 18000 25000 0.12619 19000 25000 0.12420 20000 25000 0.12321 21000 25000 0.12

71

72

Tabel B.1: Hasil uji dengan nilai jumlah operasiM tetap 25.000 (lanjutan).

No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon22 22000 25000 0.11823 23000 25000 0.11724 24000 25000 0.11325 25000 25000 0.11126 26000 25000 0.10827 27000 25000 0.10428 28000 25000 0.10129 29000 25000 0.09930 30000 25000 0.09531 31000 25000 0.09332 32000 25000 0.08933 33000 25000 0.08734 34000 25000 0.08435 35000 25000 0.08136 36000 25000 0.0837 37000 25000 0.07738 38000 25000 0.07539 39000 25000 0.07340 40000 25000 0.07141 41000 25000 0.0742 42000 25000 0.06843 43000 25000 0.06744 44000 25000 0.06645 45000 25000 0.06646 46000 25000 0.06547 47000 25000 0.06548 48000 25000 0.06449 49000 25000 0.06450 50000 25000 0.064

73


No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon1 1000 50000 0.0922 2000 50000 0.1053 3000 50000 0.1124 4000 50000 0.1185 5000 50000 0.1246 6000 50000 0.1317 7000 50000 0.1378 8000 50000 0.1449 9000 50000 0.15110 10000 50000 0.15811 11000 50000 0.16512 12000 50000 0.17213 13000 50000 0.1814 14000 50000 0.18615 15000 50000 0.19316 16000 50000 0.20117 17000 50000 0.20718 18000 50000 0.21219 19000 50000 0.21720 20000 50000 0.22121 21000 50000 0.22622 22000 50000 0.22923 23000 50000 0.23424 24000 50000 0.23625 25000 50000 0.2426 26000 50000 0.24327 27000 50000 0.24328 28000 50000 0.24729 29000 50000 0.24730 30000 50000 0.249

74


No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon31 31000 50000 0.25132 32000 50000 0.25233 33000 50000 0.2534 34000 50000 0.25135 35000 50000 0.24936 36000 50000 0.2537 37000 50000 0.24938 38000 50000 0.24839 39000 50000 0.24740 40000 50000 0.24541 41000 50000 0.24642 42000 50000 0.24643 43000 50000 0.24244 44000 50000 0.23845 45000 50000 0.23546 46000 50000 0.23347 47000 50000 0.23148 48000 50000 0.22849 49000 50000 0.22650 50000 50000 0.226

75



76



77



78

Tabel B.4: Hasil uji dengan nilai jumlah operasi M tetap 100.000 (lanjut-an).


LAMPIRAN C

HASIL UJI KINERJA JUMLAH VERTEX N TETAP

Berikut merupakan lampiran hasil uji kinerja dengan nilai jumlahvertex N tetap dari grafik pada Gambar 5.20.

Tabel C.1: Hasil uji dengan nilai jumlah vertex N tetap 12.500.

No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon1 12500 2000 0.0052 12500 4000 0.013 12500 6000 0.0154 12500 8000 0.0235 12500 10000 0.0366 12500 12000 0.0517 12500 14000 0.0648 12500 16000 0.0779 12500 18000 0.08910 12500 20000 0.09911 12500 22000 0.10712 12500 24000 0.11513 12500 26000 0.12114 12500 28000 0.12915 12500 30000 0.13316 12500 32000 0.13817 12500 34000 0.14218 12500 36000 0.14919 12500 38000 0.15120 12500 40000 0.15721 12500 42000 0.161

79

80

Tabel C.1: Hasil uji dengan nilai jumlah vertex N tetap 12.500 (lanjutan).

No. Jumlah Vertex Jumlah Operasi Waktu dalam sekon22 12500 44000 0.16423 12500 46000 0.16924 12500 48000 0.17225 12500 50000 0.17726 12500 52000 0.18127 12500 54000 0.18528 12500 56000 0.18929 12500 58000 0.19430 12500 60000 0.19631 12500 62000 0.20232 12500 64000 0.20333 12500 66000 0.20834 12500 68000 0.21235 12500 70000 0.21536 12500 72000 0.2237 12500 74000 0.22338 12500 76000 0.22739 12500 78000 0.23140 12500 80000 0.23441 12500 82000 0.23842 12500 84000 0.24243 12500 86000 0.24644 12500 88000 0.25145 12500 90000 0.25446 12500 92000 0.25947 12500 94000 0.26248 12500 96000 0.26549 12500 98000 0.26950 12500 100000 0.274

81



82



83



84



85



86



BIODATA PENULIS

Yusro Tsaqova, lahir di Mataram tanggal 3Juni 1994. Penulis merupakan anak perta-ma dari 2 bersaudara. Penulis telah menem-puh pendidikan formal TK Perwanida I Am-penan, SD Negeri 37 Ampenan (2000-2006),SMP Negeri 2 Mataram (2006-2009) danSMA Negeri 1 Mataram (2009-2012). Penu-lis melanjutkan studi kuliah program sarjanadi Jurusan Teknik Informatika ITS. Selamamasa kuliah, penulis aktif dalam organisa-si Himpunan Mahasiswa Teknik Computer-Informatika (HMTC) ITS. Penulis juga aktif

dalam kegiatan kepanitiaan Schematics sebagai Staff National Pro-gramming Contest (NPC) Schematics 2013 dan Ketua NPC Sche-matics 2014. Selain itu penulis juga aktif menjadi administrator LabPemrograman (LP) Teknik Informatika ITS.

Selama kuliah di Teknik Informatika ITS, penulis mengambil bi-dang minat Dasar dan Terapan Komputasi (DTK). Penulis pernahmenjadi asisten dosen dan praktikum untuk mata kuliah Pemro-graman Terstruktur (2013 dan 2014), Algoritma dan Struktur data(2013), Struktur Data (2014) dan Dasar Pemrograman (2015). Se-lama menempuh perkuliahan penulis juga aktif mengikut kompetisipemrograman tingkat nasional dan menjadi finalis kategori pemro-graman pada lomba COMPFEST UI (2013, 2014 dan 2015), INCBina Nusantara (2013, 2014 dan 2015) dan ICPC Regional Asia-Jakarta (2013, 2014 dan 2015). Selain itu penulis juga pernah men-jadi asisten Pelatnas 2 TOKI (2015). Penulis dapat dihubungi me-lalui surel di [email protected].

87

desaindananalisisalgoritmakomputasijumlah...

Documents