Traversal Struktur Data Bipartite Graph dalam Graph Database menggunakan Depth-First Search

Abstract

Bipartite graph merupakan satu bentuk graph yang dapat digunakan dalam membentuk sebuah strukur data yang saling berelasi namun memiliki karakteristik dengan dua jenis node yang berbeda seperti data hubungan keluarga atau data pohon keluarga. Dalam menyimpan struktur data bipartite graph ke sebuah database dapat digunakan graph database dengan konsep dimana node saling saling terhubung dengan node lainnya. Bipartite graph yang dikombinasikan dengan graph database menghasilkan solusi yang tepat dalam menyimpan data berelasi dengan dua jenis node yang berbeda. Namun dalam solusi tersebut menimbulkan permasalahan baru mengenai pencarian atau penelusuran (traversal) terhadap data yang terdapat dalam struktur data tersebut. Tujuan dari penelitian ini adalah mengembangkan algoritma yang dapat digunakan dalam penelusuran (traversal) data pada struktur bipartite graph dalam graph database. Algoritma yang dikembangkan adalah terapan dari algoritma depth-first search (DFS) yang telah dimodifikasi sehingga dapat digunakan dalam penelusuran (traversal) data pada bipartite graph dalam graph database. Hasil pengujian terhadap algoritma tersebut yang telah diimplementasikan ke dalam program terhadap data yang ada pada satu garis ikatan keluarga besar yaitu keluarga “George Washington /CASSIDY/” pada 30 kali percobaan dengan satuan waktu nanosecond yaitu 10^-9 detik menunjukkan waktu maksimal yang didapat sebesar 42831 nanosecond, waktu minimal 5150 nanosecond, dan didapat rata-rata waktu penelusuran sebesar 9407,93 nanosecond.