10 Daftar Istilah Vertex
Vertex sebuah objek yang mepresentasikan informasi tertentu, tergantung konteks yang ingin dijadikan informasi Edge Edge merupakan penghubung antar vertex dalam Graf Graf Graf merupakan kumpulan dari vertex dan edge Graph pattern Graph Pattern merupakan penggambaran pola dari graf Query Query merupakan perintah yang dikirimkan oleh pengguna untuk mendapatkan hasil yang diinginkan
xv
1 Bab I Pendahuluan 1.1 Latar Belakang Perkembangan dari analisis pola saat ini tidak lepas dari peran graf. Data yang memiliki lebih dari banyak domain direpresentasikan ke dalam graf untuk mempermudah proses manipulasi data [5]. Senyawa kimia, peta geografik, jaringan komputer, dan database adalah beberapa contoh data yang telah direpresentasikan ke dalam bentuk graf. Graf merupakan kumpulan dari vertex dan edge. Vertex digambarkan sebagai sebuah titik atau objek. Sedangkan edge digambarkan sebagai sebuah sisi yang menghubungkan suatu vertex dengan vertex lain. Dari sudut pandang analisis pola pada graf, salah satu masalah yang penting adalah pencocokan subgraph atau pencocokan graph pattern pada graf untuk membandingkan keduanya[2]. Pertumbuhan keragaman dan ukuran data yang semakin mengacu pada data graf membuat model data, query language dan sistem database yang ada saat ini tidak mendukung pemodelan dan manajemen data tersebut[5]. Berbagai penelitian telah dilakukan untuk mengatasi masalah pencarian graph pattern pada graf yang besar dengan jumlah vertex diatas 100[2]. Kompleksitas komputasi algoritma menjadi pertimbangan dalam pencarian graph pattern pada graf. Pada graf yang besar memerlukan kompleksitas komputasi yang rendah untuk mempercepat proses pencarian graph pattern. Salah satu teknik yang digunakan adalah dengan melakukan pemangkasan vertex dan edge yang tidak memiliki keterkaitan dengan pola yang dicari. Pencarian juga tidak sebatas pada pencarian informasi vertex dan edge saja. Informasi struktural dari vertex dan edge pada objek yang dicari sangat diperlukan agar informasi yang didapatkan tidak ada yang hilang[5]. Oleh karena itu, diperlukan suatu metode pencarian graph pattern dalam graf yang memiliki kemampuan untuk memberikan hasil berupa graf atau kumpulan dari beberapa graf. Graph Query Language(GraphQL) merupakan salah satu metode yang dapat digunakan untuk mencari graph pattern dalam suatu graf. GraphQL dapat digunakan pada graf yang berukuran besar. Teknik yang digunakan dalam pencarian pola adalah melakukan pemangkasan terhadap vertex dan edge pada graf, yang tidak memiliki keterkaitan dengan pola yang terdapat pada graph pattern. Kelebihan dari pemangkasan yang dilakukan oleh algoritma ini adalah pemangkasan yang dilakukan dua kali yaitu pemangkasan lokal dan pemangkasan global[7]. Hasil yang didapatkan dari pencarian dengan algoritma GraphQL adalah kumpulan dari beberapa graf.
1.2 Perumusan Masalah Permasalahan yang diangkat dalam Tugas Akhir ini adalah: 1. Bagaimana menerapkan algoritma GraphQL (Graph Query language) dalam pencocokan graph database pada dataset? 2. Bagaimana performansi running time dan reduction ratio algoritma GraphQL (Graph Query Language)?
1
1.3 Tujuan Tujuan yang ingin dicapai dari Tugas Akhir ini adalah: 1. Melakukan penerapan algoritma GraphQL(Graph Query Language) dalam pencocokan graph database pada dataset 2. Melakukan analisis untuk mengetahui performansi running time dan reduction ratio algoritma GraphQL (Graph Query Language)
1.4 Batasan Masalah 1. 2. 3. 4.
Adapun batasan masalah dalam Tugas Akhir ini adalah: Data graph database sebagai data uji lebih dari satu label Graf yang dibangun berupa graf tidak berarah yang sederhana Graph pattern yang digunakan berupa lintasan dan clique Menggunakan bahasa pemrograman java.
1.5 Metodologi Penyelesaian Masalah Metodologi penyelesesaian masalah terbagi dalam beberapa tahapan, yaitu: 1. Studi Literatur Melakukan pengumpulan dan mempelajari data, informasi serta berbagai referensi yang berkaitan dengan pencocokan graf serta algoritma GraphQL sebagai konsep pengerjaan tugas akhir. 2. Pengumpulan dan Pengolahan Data Mencari studi kasus berupa dataset graph database yang digunakan untuk mengimplementasikan algoritma GraphQL dalam pencocokan graph pattern pada graph database. 3. Desain Sistem Melakukan perancangan serta pendefinisian masalah dan solusi yang diterapkan ke dalam implementasi sistem. 4. Implementasi Melakukan implementasi algoritma GraphQL untuk melakukan pencocokan graph pattern pada graph database. 5. Kesimpulan dan Laporan Hasil Analisis Dalam pengambilan kesimpulan, yang dianalisis adalah data yang didapat dari pengujian performansi running time dan reduction ratio dari algoritma GraphQL. Pengambilan kesimpulan menggunakan langkah-langkah seperti pada gambar 1-1. b. analisis performansi running time d. a. hasil Implementasi analisis algoritma GraphQL c. analisis performansi reduction ratio Gambar 1-1: Alur Pengambilan Keputusan
2
Pada gambar 1-1, implementasi terhadap algoritma GraphQL pada graph database dilakukan terlebih dahulu. Dalam proses implementasi tersebut dilakukan pengamatan terhadap performansi performansi reduction ratio pada tahapan pemangkasan dan running time setiap tahapan algoritma GraphQL. Analisis running time untuk mengetahui lama waktu setiap proses dari algoritma GraphQL dan analisis reduction ratio untuk mengetahui keefektifan setiap tahap pemangkasan algoritma GraphQL. 6. Dokumentasi Dari setiap tahapan yang dilakukan, dibuatkan dokumentasi agar setiap kegiatan dapat dipertanggungjawabkan secara jelas.
3
2 Bab II Tinjauan Pustaka 2.1 Graph query Language Graph quey language memiliki beragam definisi. Berikut ini adalah beberapa contoh definisi tentang graph query language[5]: 1. Data Model Data model pada GraphQL dapat digambarkan sebagai graf motif yang mempunyai atribut pada vertex atau edge. Contoh : Graph G{ Vertex v1
; Vertex v2 ; } 2. Graph pattern Graph pattern merupakan graf motif yang disertai dengan predikat pada atribut. Graph pattern dapat disebut juga sebagai graph query yang bertujuan untuk mencari pola tertentu pada graf. Graph pattern direpresentasikan sebagai berikut: = ( , ) M adalah graf motif dan F adalah predikat. Contoh 1 : Graph P { Vertex v1 where name =”A”; Vertex v2 where year>2000; }; Contoh 2: Graph P { Vertex v1; Vertex v2; } where v1.nama=”A” and v2.year>2000; 3. Graph pattern matching P (M,F) dikatakan sama dengan graf G jika terdapat pemetaan injektif 1 ke 1, ∅ :V(M) V(G) untuk ∀ e(u,v) ∈ E(M),( ∅(u), ∅(v)) merupakan edge dari G dan predikat F∅(G).Contoh pemetaan dari graph pattern pada graf G Mapping ∅: ∅( . 1) → . 2 ∅( . 2) → . 1
2.2 Graf Graf terbentuk atas dua komponen yaitu vertex dan edge yang direpresentasikan sebagai G=(V,E) dengan V adalah vertex sedangkan E adalah edge sebagai penghubung antar vertex. Berdasarkan orientasi arah, graf dapat 4
dibagi menjadi dua jenis yaitu graf berarah dan graf tidak berarah. Graf berarah merupakan graf yang mempunyai arah sehingga keterhubungan antar vertex hanya satu arah, sedangkan pada graf tidak berarah keterhubungan antar vertex dapat dua arah. Contoh : E = {{x,y}} dalam graf berarah menunjukkan bahwa relasi dari vertex tersebut hanya berasal dari vertex x ke y, dengan x adalah predecessor dan y adalah successor. Jika graf tidak berarah, maka kedua vertex tersebut saling berhubungan. Vertex x berelasi ke vertex y dan vertex y berelasi ke x. Berikut ini adalah macam-macam graf [6]: 1. Mixed Graph Mixed graph atau graf campuran merupakan gabungan dari graf berarah dan graf tidak berarah yang ditulis sebagai G = (V,E,A) dimana A adalah arah dari edge. 2. Multi Graph Multi graph memperbolehkan adanya loop. Loop adalah suatu edge yang mengarahkan vertex pada vertex yang sama. Dalam orientasi arah, multi graph dapat berupa graf berarah maupun graf tidak berarah. 3. Simple Graph Simple graph merupakan graf tidak berarah yang tidak mempunyai loop. Graph motif merupakan dasar dari stuktur data berbentuk graf. Berikut ini adalah beberapa jenis graph motif beserta representasi graf dalam bentuk gambar: 1. Simple graph motif Terdiri dari vertex dan edge Graph G1{ Vertex v1,v2,v3; Edge e1 (v1,v2); Edge e2 ( v2,v3); Edge e3 (v3,v1); } 2. Concatenation a. Concatenation berdasarkan edge Graph G2{ Graph G1 as X; Graph G1 as Y; Edge e4 (X.v1,Y.v1); Edge e5 (X.v3, Y.v2); }
V1 E V2
E3 E2
V3
Gambar 2-1: Simple Graph Motif[5]
E1
V1
V1
E3
V2 E2
V3
E3
E4 E1 E5 V2
V3 E2
Gambar 2-2: Concatenation berdasarkan Edge[5] b. Concatenation dari proses penggabungan V E3 E1 V1(V1) Graph G3{ Graph G1 as X; Graph G1 as Y; Unify X.v1, Y.v1; Unify X.v3, Y.v2;
E3
V2 E2
E1
V3(V2)
V3 E2
} Gambar 2-3: Concatenation dari Proses Penggabungan[5] 5
3. Disjunction Graph G4{ Vertex v1,v2; Edge e1(v1,v2); { Vertex v3; Edge e2(v1,v3); Edge e3(v2,v3); } |{ Vertex v3,v4; Edge e2(v1,v3); Edge e3(v2,v4); Edge e4(v3,v4); }; } 4. Path dan cycle Graph Path{ Graph path; Vertex v1; Edge e1(v1, Path.v1); Export Path.v2 as v2; }|{ Vertex v1,v2; Edge e1(v`,v2; } Graph cycle{ graph Path; Edge e1(Path.v1,Path.v2); } 5. Repetition Graph G5{ Graph G5; Graph G1; Export G5.vo as vo; Edge e1(vo,G1,v1); }|{vertex vo};
V1 E V2
E2 V3 E
Gambar 2-4: Disjuction(1)[5] V3 V1 E2 E1 E3 V4 V2 Gambar 2-5: Disjuction(2)[5]
Path V1
E1
E1
V1
V2
Gambar 2-6: Path dan Cycle[5]
V0 E3
V1 E1
V3 E2
V2
V1
E3 E1 V3 E2
V2
G Gambar 2-7: Repetition[5]
Graf Berbobot Graf dikatakan mempunyai bobot bila edge mempunyai atribut nilai seperti jarak atau kapasitas, dengan nilai tergantung dari masalah yang diangkat. Berikut ini merupakan contoh graf yang tidak berarah.
6
E
A E1
E3 E4
B
E2
C
D
E6
Gambar 2-8: Multigraph Tidak Berarah Gambar 2-8 merupakan contoh graf tidak berarah dengan V={A,B,C,D,E} dan E={{A,B},{B,C},{A,C},{C,D},{D,D}}. Vertex A dan vertex C merupakan tetangga dari vertex B, sehingga vertex B berderajat 2. Vertex D memiliki derajat 3 akibat dari adanya edge e6 yang merupakan sebuah loop yang dibaca dua arah. Vertex E adalah vertex terpencil karena vertex tersebut tidak memiliki tetangga ataupun derajat. Salah satu masalah dalam graf adalah pencocokan graf dengan subgraph atau graph subgraph isomorfis. Pencocokan graph subgraph merupakan proses menemukan korespondensi antara vertex dan edge suatu graf yang memastikan bahwa sub struktur serupa dapat dipetakkan ke sub struktur serupa yang lain[4]. Dalam proses tersebut bila G1 = (N1,B1) dan G2=(N2,B2), maka harus dilakukan penentuan pemetaan M yang berasosiasi vertex dari G1 ke vertex G2 begitu juga sebaliknya. Pemetaan M ⊂ N1 x N2 dikatakan isomorfis jika M merupakan fungsi bijektid yang mempertahankan struktur cabang dari kedua graf. Begitu juga untuk pemetaan M ⊂ N1 x N2 merupakan graph subgraph isomorfis jika M isomorfis antara graf G2 dan subgraph dari G1[2]. Subgraph (Graf Bagian) Sebuah graf g merupakan subgraph dari graf G jika semua sisi dan titik yang berhubungan dari graf g merupakan bagian dari graf G. Sifat-sifat hubungan graf dengan subgraph : 1. Setiap graf merupakan subgraph dari dirinya sendiri 2. Subgraph dari suatu subgraph dari G adalah subgraph dari G 3. Sebuah titik di graf G merupakan subgraph dari G 4. Sebuah sisi dengan kesamaan titik dari graf G merupakan subgraph dari G.
Gambar 2-9: graf G
Gambar 2-10: Subgraph g
Gambar 2-10 merupakan subgraph dari graf G pada gambar 2-9 karena subgraph g memiliki vertex dan edge yang merupakan bagian dari graf G.
7
Graf Bipartit Sebuah graf dikatakan bipartit jika vertex dalam graf dapat dibagi menjadi dua himpunan bagian, sedemikian hingga tidak ada vertex yang saling berhubungan dalam himpunan yang sama. Jika semua vertex pada suatu himpunan terhubung dengan vertex pada himpunan lain maka dapat disebut graph bipatit lengkap. Berikut ini merupakan graf bipartit lengkap.
Gambar 2-11: Graf Bipartit Lengkap Pada gambar 2-11, graf terbagi menjadi dua himpunan, yaitu himpunan {a,b} dan himpunan{c,d,e,f}. semua vertex pada himpunan {a,b} memiliki vertex yang terhubung ke vertex pada himpunan yang lain sehingga membentuk graf bipartit lengkap. Graph Matching Matching dalam suatu graf merupakan kumpulan dari edge dengan setiap vertex yang hanya terhubung dengan satu edge. Graph Matching ini dapat berupa maximum matching, maximal matching, perfect matching, dan semi perfect matching. Maximum matching merupakan kemungkinan edge terbanyak pada matching M suatu graf. Maximal matching merupakan suatu matching M dalam suatu graf yang jika ditambahkan edge yang bukan matching, maka tidak dapat disebut sebagai matching lagi. Perfect Matching merupakan matching dengan semua vertex yang memiliki edge matching. Semi perfect Matching merupakan graf yang mendekati perfect matching dikarenakan adanya satu vertex yang tidak matching dan hanya terjadi jika graf mempunyai jumlah vertex yang ganjil.
2.3 Representasi Graf Graf dapat direpresentasikan dengan dua cara yaitu matrik ketetanggaan dan multi linked list. Berikut ini adalah contoh graf G.
Gambar 2-12: Graf G Pada gambar 2-12, graf G terdiri dari empat buat vertex yaitu A, B,C, dan D dengan vertex A,B,C yang saling terhubung, dan vertex C yang mempunyai edge terhubung dengan vertex D.
8
Matrik Ketetanggaan Matrik ketetangaan dalam bahasa pemrograman berupa array dua dimensi. Isi dari matrik tersebut dapat berupa bobot yang menandakan keterhubungan antar vertex. Tabel 2-1 berikut ini adalah contoh representasi graf G pada gambar 2-12 dengan matrik ketetanggaan. Tabel 2-1: Representasi Matrix Graf G A B C D A 0 1 1 0 B 1 0 1 0 C 1 1 0 1 D 0 0 1 0 Multi Linked List List memiliki sifat yang dinamis, sehingga data dapat diolah secara dinamis juga. Gambar 2-13: merupakan representasi graf menggunakan multi linked list. Graph first Vertex Vertex Id
first edge
Next
Next
edge
Vertex next
Vertex next
Edge
Vertex Id
Vertex first
Edge
Vertex next
Edge
Gambar 2-13: Representasi List Graf Pada gambar 2-13, representasi vertex terdiri dari vertex id yang merupakan info dari vertex, first edge digunakan untuk menambahkan vertex asal dengan edge yang menghubungkan vertex tersebut dengan vertex lain, dan next merupakan index vertex pada array. Edge terdiri dari vertex yang menunjuk pada vertex tujuan dan next sebagai index edge pada array.
2.4 Metode Penelusuran Graf Metode penelusuran graph dapat menggunakan metode Breadth-First Search (BFS) dan Depth-First Search (DFS).
9
Breadth-First Search Metode pencarian BFS melakukan pencarian mulai dari awal vertex (root) di kedalaman 0 hingga kedalaman terakhir. Dalam implementasinya BFS menggunakan Queue atau antrian untuk mengunjungi semua vertex yang ada. Dari graf pada gambar 2-12, urutan pencarian algoritma BFS dengan vertex A sebagai root adalah A,B,C,D. Depth-First Search Metode pencarian DFS melakukan pencarian mulai dari awal vertex kemudian menelusuri subtree terlebih dahulu, hingga semua vertex selesai ditelusuri. Implementasi DFS menggunakan stack atau tumpukan untuk mempermudah pengecekan vertex yang dikunjungi. Dari graf pada gambar 2-12, urutan pencarian algoritma DFS dengan vertex A sebagai root adalah A,B ,C,D.
2.5 Graph Database Graph database merupakan salah satu kategori dari NoSQL yang memodelkan suatu database ke dalam bentuk graf. Sama seperti konsep graf, vertex merupakan data atau entitas sedangkan edge merupakan relasi atau hubungan antar vertex. Dalam memodelkan ke graph database menggunakan fungsi Create,Read, Update, dan Delete. Graph database dapat direpresentasikan menggunakan adjacency list atau mengimplementasikan ke bentuk array. Graph database terdiri dari [8]: 1. Graph Storage Graph storage merupakan tempat penyimpanan graph database. Untuk menyimpan graph database digunakan native graph storage, serialisasi data graf kedalam basisdata relasional, basisdata berbasis objek, dan lain-lain. 2. Graph Processing Engine Digunakan untuk membentuk suatu graph database dan mengatur pemrosesan data. Graph records data in records data Relationship Vertexs
organize have
have Properties Gambar 2-14 Graph Database 10
Ilustrasi pada gambar 2-14 menggambarkan konsep graph database yang terdiri atas vertex, relasi, dan edge. Vertex merupakan data sedangkan relasi untuk menghubungkan antar vertex. Setiap vertex dan relasi tersebut dapat memiliki property atau atribut.
2.6 Algoritma GraphQL Algoritma GraphQL merupakan salah satu algoritma pencocokan graph pattern pada graf yang mampu menangani graf berukuran kecil hingga besar. Inti dari algoritma GraphQL adalah persamaan dalam graf aljabar untuk proses seleksi dan komposisi. Operator seleksi untuk proses pemangkasan ruang pencarian graf, dan operator komposisi untuk membentuk graf baru dari ruang pencarian. Algoritma ini menggunakan 4 teknik untuk mencocokan graph pattern pada graf. Pertama, mencari jangkauan pencarian dengan cara pemangkasan berdasarkan profil. Kedua, mengurangi jangkauan pencarian secara keseluruhan menggunakan konsep pseudo isomorphism test. Ketiga, mengoptimalkan urutan pencarian berdasarkan model biaya. Terakhir, melakukan kombinasi seluruh anggota dari ruang pencarian dan mencari kombinasi vertex yang sesuai dengan graph pattern. Berikut ini adalah tahap-tahap yang dilakukan algoritma GraphQL: 1. Pasangan Kelayakan Pasangan kelayakan merupakan sekumpulan vertex dari graf G yang memenuhi predikat pada graph pattern. Φ ( ) = { | ∈ ( ), ( ) = } 2. Ruang Pencarian Ruang pencarian dari graph pattern matching merupakan sekumpulan dari pasangan kelayakan. Ruang Pencarian = Φ ( ) Φ ( ) Φ ( ) Φ ( ) Banyaknya ruang ruang pencarian didapatkan dari jumlah vertex pada graph pattern dikalikan hasil pasangan kelayakan tiap vertex. 3. Pemangkasan Lokal Hasil dari pasangan kelayakan perlu dilakukan pemangkasan untuk mendapatkan ruang pencarian yang sedikit dan sesuai dengan graph pattern. Ruang pencarian mempengaruhi waktu pencarian dari graph pattern matching. Semakin sedikit ruang pencarian mempercepat waktu pencarian graph pattern. Berikut ini adalah contoh dari graf G dan graph pattern P. B1
D2 A
A1
D1
C1
A2 B
B2
D
C
B3
Gambar 2-16: Graf G
Gambar 2-15: Graph Pattern P
11
Terdapat dua cara dalam pemangkasan lokal ruang pencarian, yaitu: a. Pemangkasan berdasarkan tetangga Pemangkasan berdasarkan tetangga melihat langsung segala informasi vertex v pada graph pattern P yang memiliki kesamaan dengan vertex u pada graf G. Hasil dari pasangan kelayakan merupakan hasil yang paling tepat dan hasil dari pemangkasan ini memangkas vertex lebih banyak. Namun untuk pemangkasan dengan cara ini membuat biaya komputasi menjadi tinggi[5]. Hasil pemangkasan graph pattern P dan graf G seperti yang terdapat pada gambar 2-15 dan gambar 2-16 adalah {A1}x{B1}x{C1}x{D1}. b. Pemangkasan berdasarkan profil Pemangkasan bedasarkan profil dilakukan dengan cara melihat adanya tetangga dari vertex v pada vertex u. Dengan cara ini ruang pencarian yang dihasilkan lebih banyak daripada pemangkasan berdasarkan tetangga, namun secara komputasi biaya yang digunakan lebih kecil daripada pemangkasan berdasarkan tetangga [5]. Hasil pemangkasan : {A1}x{B1}x{B1}x{C1}x{D1} 4. Pemangkasan global Pemangkasan ini dapat dapat disebut juga join reduction of search space. Pada tahap ini dilakukan pemangkasan menggunakan konsep pseudo isomorphism test. Teknik ini mengecek setiap vertex dan pasangan kelayakan dari Φ ( ) apakah subtree dari vertex di ( ) subisomorphic dengan vertex di ( ). Pengecekan dilakukan dengan menggunakan algoritma BFS untuk setiap dan pada kedalaman = 1. Jika pada tidak terdapat di , maka dihapus dari ruang pencarian. Langkah ini dilakukan sampai iterasi dari kedalaman sama dengan refinement level . Tiap level dari dibuat graf bipartit , dari vertex dan vertex beserta tetangga-tetangganya. Graf , dilakukan pengecekan semi-perfect matching untuk menentukan vertex yang tidak dipangkas. Graf memiliki , semi-perfect matching jika vertex yang terbentuk dari tetangga, atau terhubung dengan vertex v yang memiliki kesamaan predikat. Untuk mengecek apakah graf semi-perfect matching dapat menggunakan algoritma Hopcroft and Karp’s dengan kompleksitas (O(n2.5) . Untuk lebih jelasnya dapat dilihat contoh berikut : A
B
D
Gambar 2-17: Subtree yang Terbentuk dari u atau Vertex A Gambar 2-17 merupakan subtree dari vertex A yang diambil dari gambar 216. Vertex A tersebut hanya memiliki tetangga B dan D.
12
A2 C1
B3 Gambar 2-18: Subtree yang Terbentuk dari atau Vertex A2. Gambar 2-18 merupakan subtree dari vertex A2 yang diambil dari gambar 2-15. Vertex A2 tersebut hanya memiliki tetangga C1 dan B3. Dari kedua subgraf pada gambar 2-17 dan 2-18 dibuat graf bipartite , dari tiap subtree dan . Kemudian cek apakah ada vertex dari yang memiliki persamaan predikat dengan vertex di , jika sama hubungkan kedua vertex tersebut. Berikut ini adalah graf bipartit yang terbentuk.
Gambar 2-19: Graf B(A,A2) Dari graf bipartit pada gambar 2-19, cek apakah vertex dan semi-perfect matching. Jika semi-perfect matching maka vertex tetap disimpan, sedangkan jika tidak, dihapus dari ruang pencarian. Dari contoh diatas, dihapus karena vertex D tidak memiliki hubungan dengan vertex di . Berikut ini adalah contoh lain pada iterasi r kedua dengan cara pembentukan yang sama dengan iterasi sebelumnya. B A
D
Gambar 2-20: Subtree yang Terbentuk Dari
atau Vertex B
B3
C1
A2
Gambar 2-21: Subtree yang Terbentuk Dari
atau Vertex B3
13
B
B3
A
A2
D
C1
Gambar 2-22: Graf BB,B3 Pada graf bipartite , , vertex A tidak dihubungakan dengan vertex A2 karena vertex A2 telah dihapus dari ruang pencarian Φ ( ) saat iterasi pertama dilakukan. Sehingga graf bipartite tidak semi-perfect , matching, dan B3 dihapus dari ruang pencarian. 5. Optimasi ruang pencarian Optimasi ruang pencarian menggunakan konsep model biaya dan urutan pencarian. Untuk mendapatkan biaya dapat dicari dengan rumus berikut ()= (. ) (. ) Υ(i) i.kiri merupakan vertex sebelah kiri dan i.kanan adalah vertex sebelah kanan pada struktur tree yang telah dibangun. Bobot tiap vertex kiri atau kanan didapatkan dari jumlah anggota yang dimiliki pada ruang pencarian. Sedangkan Υ merupakan faktor reduksi. Faktor reduksi ini dapat menggunakan faktor reduksi konstan atau mencari faktor reduksi Υ(i) dengan cara mencari probilitas dari edge pada proses gabungan[5]. Υ(i) = ∏ ( , ) ( ) ( ( , )) P(e(u, v)) merupakan probilitas dari edge rumus berikut: ( , )
( , ) =
( ).
( )
(2.1) ( , ), yang dicari dengan (2.2)
Freq menandakan frekuensi dari edge pada graf. Biaya dari gabungan I dicari menggunakan rumus berikut ()= (. ) (. ) (2.3) Total Biaya dari urutan pencarian Γ adalah (Γ) =
∈
Biaya(i)
(2.4)
2.7 Algoritma Greedy Algoritma Greedy merupakan algoritma pencarian yang menggunakan pendekatan pencarian nilai maksimum di setiap langkahnya. Algoritma ini tidak akan memberikan hasil yang optimal namun dapat memberikan solusi yang mendekati optimal dengan pencarian yang cepat. Algoritma Greedy disusun oleh elemen-elemen seperti : 1. Himpunan kandidat sebagai elemen-elemen pembentuk solusi 2. Himpunan solusi, yaitu kadidat yang terpilih sebagai solusi persoalan 3. Fungsi seleksi, yaitu pemilihan kandidat yang paling memberikan solusi optimal 4. Fungsi Kelayakan, yaitu pemeriksaan terhadap kadidat yang dipilih tepat atau tidak 14
5. Fungsi Obyektif, yaitu memaksimumkan nilai solusi Secara umum, algoritma Greedy dapat mengikuti langkah-langkah berikut: 1. Mengunjungi salah satu titik awal, lalu mengambil seluruh titik yang dapat dikunjungi oleh titik sekarang 2. Mencari lokal maksimum ke titik selanjutnya 3. Tandai titik yang telah dikunjungi, lalu pindahkan ke lokal maksimum yang telah ditentukan 4. Kembali ke langkah 1 sampai titik tujuan ditemukan.
2.8 Algoritma Dijkstra Algoritma Dijkstra merupakan algoritma yang ditemukan oleh Edsger Wybe Dijkstra pada tahun 1959. Algoritma ini dapat memecahkan masalah pencarian lintasan terpendek pada graf berbobot. Langkah-langkah penentuan lintasan terpendek pada algoritma Dijkstra yaitu : 1. inisialisasi jarak semua vertex dengan nilai tidak terhingga dan melakukan inisialisasi jarak vertex sumber dengan nilai 0. 2. Tandai jarak vertex sumber sebagai jarak permanen dan jarak dari vertex lain sebagai jarak sementara 3. Set vertex sumber sebagai vertex terpilih. 4. Menghitung jarak sementara semua vertex dari tetangga vertex terpilih dengan menjumlahkan jarak vertex terpilih dengan jarak vertex tujuan. 5. Dari hasil perhitungan, ambil jarak terkecil dan jadikan vertex tujuan sebagai vertex terpilih berikutnya 6. Ulangi langkah 4 sampai 6 sampai tidak ada vertex lagi yang dapat diset sebagai jarak permanen dengan tetangga yang masih memiliki jarak sementara. Berdasarkan langkah-langkah tersebut, berikut ini adalah pseudocode dari algoritma Dijkstra. 1. function Dijkstra(Graph, source): 2. for each vertex v in Graph: 3. dist[v] := infinity 4. previous[v] := undefined 5. dist[source] := 0 6. Q := the set of all nodes in Graph 7. while Q is not empty: 8. u := node in Q with smallest dist[ ] 9. remove u from Q 10. for each neighbor v of u: 11. alt := dist[u] + dist_between(u, v) 12. if alt < dist[v] 13. dist[v] := alt 14. previous[v] := u 15. return previous[ ] Gambar 2-23: Pseudocode Algoritma Dijkstra
15
