Perpustakaan Digital ITB

Time-dependent graph adalah graf yang memodelkan objek yang berubah terhadap waktu. Pencarian shortest-path pada graf jenis ini harus mempertimbangkan kondisi graf pada time instance berbeda. Pembangunan path tidak hanya mencakup node tujuan penelusuran. Penentuan waktu penelusuran edge juga perlu dilakukan. Oleh karena itu, pencarian shortest-path pada time-dependent graph perlu penanganan khusus. Diperlukan sebuah perangkat lunak untuk memberikan penanganan khusus tersebut. Bentuk perangkat lunak berupa middleware dapat digunakan untuk hal ini. Bentuk ini memungkinkan penanganan berbagai jenis basis data. Selain itu bentuk ini juga dapat digunakan oleh berbagai aplikasi. Dalam tugas akhir ini, produk yang dihasilkan adalah middleware untuk melakukan pencarian shortest-path pada time-dependent graph. Permasalahan utama dalam membangun middleware ini adalah pemilihan model dan algoritma yang tepat untuk digunakan. Model yang digunakan pada middleware ada dua, yaitu time-expanded graph dan time-aggregated graph. Model time-expanded graph digunakan saat pembangunan path. Model time-aggregated graph digunakan saat pengiriman data dari basis data. Algoritma yang digunakan pada middleware adalah algoritma shortest-path untuk graf asiklik. Kinerja algoritma ini ditingkatkan lagi dengan memanfaatkan atribut waktu yang terdapat pada model time-expanded graph. Dari pengujian yang dilakukan, disimpulkan middleware memenuhi kebutuhan fungsional. Middleware bisa digunakan pada basis data Neo4j dan PostgreSQL. Middleware siap menerima tambahan dukungan untuk basis data lain. Middleware yang telah dibuat tidak terlalu terikat dengan aplikasi sehingga dapat digunakan oleh berbagai aplikasi berbeda.